Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > K-CLIQUE:
Reports tagged with k-clique:
TR16-002 | 18th January 2016
Ryan Williams

Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$,
$\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and ... more >>>


TR18-092 | 4th May 2018
Marco Carmosino, Russell Impagliazzo, Manuel Sabin

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires $n^{\epsilon k}$ time, for some constant $\epsilon > 1/2$, to count (note that these conjectures are significantly ... 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