In certain complexity-theoretic settings, it is notoriously difficult to prove complexity
separations which hold almost everywhere, ie, for all but finitely many input lengths. For …

We prove that if every problem in NP has nk-size circuits for a fixed constant k, then for every
NP-verifier and every yes-instance x of length n for that verifier, the verifier's search space …

We consider the range avoidance problem (called Avoid): given the description of a circuit
with more output gates than input gates, find a string that is not in the range of the circuit …

For a matrix H over a field F, its rank-r rigidity, denoted by R_H(r), is the minimum Hamming
distance from H to a matrix of rank at most r over F. A central open challenge in complexity …

We prove that for all constants a, NQP= NTIME [n polylog (n)] cannot be (1/2+ 2− log an)-
approximated by 2log an-size ACC 0∘ THR circuits (ACC 0 circuits with a bottom layer of …

We introduce a variant of Probabilistically Checkable Proofs (PCPs) that we refer to as
rectangular PCPs, wherein proofs are thought of as square matrices, and the random coins …

The best known lower bounds for the circuit class TC 0 are only slightly super-linear.
Similarly, the best known algorithm for derandomization of this class is an algorithm for …

Following the seminal work of [RR Williams, J. ACM, 61 (2014)], in a recent
breakthrough,[CD Murray and RR Williams, STOC 2018] proved that (nondeterministic quasi …

We considerably sharpen the known connections between circuit-analysis algorithms and
circuit lower bounds, show intriguing equivalences between the analysis of weak circuits …

We reduce non-deterministic time T ≥ 2^ n T≥ 2 n to a 3SAT instance ϕ ϕ of quasilinear
size| ϕ|= T ⋅\log^ O (1) T| ϕ|= T· log O (1) T such that there is an explicit circuit C that on …