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

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

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

In a Merlin-Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin's proof plus the running time of Arthur. We ... more >>>