We formalize a combinatorial principle, called the 3XOR principle, due to Feige, Kim and Ofek (2006), as a family of unsatisfiable propositional formulas for which refutations of small size in any propositional proof system that possesses the feasible interpolation property imply an efficient *deterministic* refutation algorithm for random 3SAT with ... more >>>

The following two decision problems capture the complexity of
comparing integers or rationals that are succinctly represented in
product-of-exponentials notation, or equivalently, via arithmetic
circuits using only multiplication and division gates, and integer
inputs:

Input instance: four lists of positive integers:

$a_1, \ldots , a_n; \ b_1, \ldots ,b_n; \ ... more >>>

We study the class of homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuits, which are depth 4 homogenous circuits with top fanin bounded by $r$. We show that any homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuit computing the permanent of an $n\times n$ matrix must have size at least $\exp\left(n^{\Omega(1/r)}\right)$.

In a recent result, Gupta, Kamath, Kayal and ... more >>>