Ke Shi | (shǐ) ()

a photo

I am a Master's student at USTC, currently under the guidance of Shuai Shao.

Prior to this, I earned my Bachelor's degree in Computer Science from UESTC while conducting theoretical computer science (TCS) research under the guidance of Chao Xu.

My research interests revolve around algorithms and combinatorial optimization. Recently, my focus has been directed towards approximate counting algorithms and their correlations with the phenomenon of phase transitions in statistical physics.

You can contact me through email [email protected] or [email protected].

Selected Publications
See all publications.
Conference Publications
A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function

SODA .

In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f:2^V\to \R, computing a k-partition \{ V_1, \ldots, V_k \} of V with minimum \sum_{i=1}^k f(V_i). The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for k \leq 3. In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem.

Journal Publications
description airplay
A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function

Mathematical Programming .

In this paper, we study the minimum k-partition problem of submodular functions, i.e., given a finite set V and a submodular function f:2^V\to \R, computing a k-partition \{ V_1, \ldots, V_k \} of V with minimum \sum_{i=1}^k f(V_i). The problem is a natural generalization of the minimum k-cut problem in graphs and hypergraphs. It is known that the problem is NP-hard for general k, and solvable in polynomial time for k \leq 3. In this paper, we construct the first polynomial-time algorithm for the minimum 4-partition problem.

Manuscripts
Some manuscripts are available upon request.
description airplay
Almost optimum \ell-covering of \Z_n

, Submitted.

A subset B of ring \Z_n is called a \ell-covering set if \{ ab \pmod n \mid 0\leq a \leq \ell, b\in B\} = \Z_n. We show there exists a \ell-covering set of \Z_n of size O(\frac{n}{\ell}\log n) for all n and \ell, and how to construct such set. We also show examples where any \ell-covering set must have size \Omega(\frac{n}{\ell}\frac{\log n}{\log \log n}). The proof uses a refined bound for relative totient function obtained through sieve theory, and existence of a large divisor with linear divisor sum.