Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > AVERAGE CASEHARDNESS:
Reports tagged with average casehardness:
TR94-016 | 12th December 1994
Jin-Yi Cai, W. H. J. Fuchs, Dexter Kozen, Zicheng Liu

Efficient Average-Case Algorithms for the Modular Group


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.

more >>>

TR19-068 | 27th April 2019
Shuo Pang

LARGE CLIQUE IS HARD ON AVERAGE FOR RESOLUTION

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 >>>




ISSN 1433-8092 | Imprint