Jin-Yi Cai, W. H. J. Fuchs, Dexter Kozen, Zicheng Liu

The modular group occupies a central position in many branches of

mathematical sciences. In this paper we give average polynomial-time

algorithms for the unbounded and bounded membership problems for

finitely generated subgroups of the modular group. The latter result

affirms a conjecture of Gurevich.

Shuo Pang

We prove resolution lower bounds for $k$-Clique on the Erdos-Renyi random graph $G(n,n^{-{2\xi}\over{k-1}})$ (where $\xi>1$ is constant). First we show for $k=n^{c_0}$, $c_0\in(0,1/3)$, an $\exp({\Omega(n^{(1-\epsilon)c_0})})$ average lower bound on resolution where $\epsilon$ is arbitrary constant.

We then propose the model of $a$-irregular resolution. Extended from regular resolution, this model ... more >>>