Name
Title | ||
|---|---|---|
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good. |
Abstract | ||
|---|---|---|
We show that if we can design poly($s$)-time hitting-sets for $Sigmawedge^aSigmaPi^{O(log s)}$ circuits of size $s$, where $a=omega(1)$ is arbitrarily small and the number of variables, or arity $n$, is $O(log s)$, then we can derandomize blackbox PIT for general circuits in quasipolynomial time. This also establishes that either E$notsubseteq$#P/poly or that VP$ne$VNP. In fact, we show that one only needs a poly($s$)-time hitting-set against individual-degree $au0027=omega(1)$ polynomials that are computable by a size-$s$ arity-$(log s)$ $SigmaPiSigma$ circuit (note: $Pi$ fanin may be $s$). Alternatively, we claim that, to understand VP one only needs to find hitting-sets, for depth-$3$, that have a small parameterized complexity. Another tiny family of interest is when we restrict the arity $n=omega(1)$ to be arbitrarily small. We show that if we can design poly($s,mu(n)$)-time hitting-sets for size-$s$ arity-$n$ $SigmaPiSigmawedge$ circuits (resp.~$Sigmawedge^aSigmaPi$), where function $mu$ is arbitrary, then we can solve PIT for VP in quasipoly-time, and prove the corresponding lower bounds. Our methods are strong enough to prove a surprising {em arity reduction} for PIT-- to solve the general problem completely it suffices to find a blackbox PIT with time-complexity $sd2^{O(n)}$. We give several examples of ($log s$)-variate circuits where a new measure (called cone-size) helps in devising poly-time hitting-sets, but the same question for their $s$-variate versions is open till date: For eg., diagonal depth-$3$ circuits, and in general, models that have a {em small} partial derivative space. We also introduce a new concept, called cone-closed basis isolation, and provide example models where it occurs, or can be achieved by a small shift. |
Year | Venue | DocType |
|---|---|---|
2017 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
abs/1702.07180 | 1 | 0.35 |
References | Authors | |
13 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manindra Agrawal | 1 | 581 | 45.56 |
| Michael A. Forbes | 2 | 31 | 3.27 |
| Sumanta Ghosh | 3 | 2 | 2.17 |
| Nitin Saxena | 4 | 280 | 26.72 |