25
votes
Proof that circuit upper bounds for $E$ imply $P \neq NP$
I don't think the paper in the other answer contains an answer to your question. Indeed I am not really sure a proof has been published, because the result follows from other well known results.
The ...
- 27.3k
20
votes
Accepted
Is BPP vs. P a real problem after we know BPP lies in P/poly?
Not sure how much of an answer this is, I'm just indulging in some rumination.
Question 1 could be equally asked about P $\neq$ NP and with a similar answer -- the techniques/ideas used to prove the ...
- 7,595
17
votes
Accepted
Regular versus TC0
Take $S_5$ as alphabet and
$$L= \{ \sigma_1\cdots \sigma_n \in S_5^*\mid \sigma_1\circ\cdots\circ\sigma_n = \text{Id}\}$$
Barrington proved in [2] that $L$ is $\textrm{NC}^1$-complete for $\textrm{AC}...
- 992
16
votes
Accepted
Small circuits for circuit evaluation problem
I have learned from talking to Ryan Williams (who deserves the credit for my being able to post this answer) that it is known from Paul and Pippenger that Circuit Eval can be decided by a quasilinear ...
- 548
15
votes
Regular versus TC0
Regular languages with unsolvable syntactic monoids are $\mathrm{NC}^1$-complete (due to Barrington; this is the underlying reason behind the more commonly quoted result that $\mathrm{NC}^1$ equals ...
- 16.9k
15
votes
Collapses under the assumption that $NEXP\subseteq P/Poly$
A whole lot of fun things happen. Most of the ones I know of start with the IKW paper. There, the collapse $\textrm{NEXP} = \textrm{MA}$ is shown, and (I think) is the strongest literal collapse of ...
- 1,429
15
votes
Accepted
Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings
Yes, any such pair can be separated by a formula of size $O(n)$. More generally, any disjoint pair $P,N\subseteq\{0,1\}^n$ of size $s=|P|+|N|$ can be separated by a decision tree of size $O(s)$, which ...
- 16.9k
13
votes
Accepted
Collapses under the assumption that $NEXP\subseteq P/Poly$
I believe the strongest is that $NEXP = MA$. This was proved by Impagliazzo Kabanets and Wigderson.
See https://scholar.google.com/scholar?cluster=17275091615053693892&hl=en&as_sdt=0,5&...
- 27.3k
11
votes
Better lower bounds than 3n for non-boolean functions?
here are new results on this said to be the 1st in ~3 decades and some brief commentary
A better-than-3n lower bound for the circuit complexity of an explicit function / Find, Golovnev, Hirsch, ...
- 11k
11
votes
Accepted
Evaluate boolean circuit on batch of similar inputs
I'd consider it unlikely that such a trick is easy to find and/or will give you significant gains, as it would give nontrivial satisfiability algorithms. Here's how:
First of all, while ostensibly ...
- 1,429
11
votes
Accepted
Why is the circuit class AC0 unavoidable?
The class $\mathbf{AC}^0$ arises very naturally as the circuit characterization of problems definable by formulas of first-order logic. A language over the alphabet $\{ 0,1 \}$ is in $\mathbf{AC}^0$ ...
- 4,631
11
votes
What are examples of how non-uniformity can be useful?
An example I like is the argument that $\mathrm{NE\subseteq coNE}/(n+1)$ by counting strings in the language (see e.g. https://blog.computationalcomplexity.org/2004/01/little-theorem.html).
- 16.9k
10
votes
Accepted
Consequences of $NP\subseteq P/poly$ to $BQP$
I'm not aware of any direct consequence of $NP\subset P/poly$ for $BQP$. Of course it might lessen the interest in quantum computing, since it would mean that we could do something far more ...
- 13.6k
10
votes
Accepted
What is the minimum size of a circuit that computes PARITY?
It is possible to compute parity using only 2.33n + C gates. The construction is quite simple and is given in this article.
http://link.springer.com/article/10.3103/S0027132215050083
Here is an ...
- 216
10
votes
Accepted
Randomness and small circuits complexity classes
Most nonuniform complexity classes—$\mathrm{NC^1}$ included—are closed under the $\mathrm{BP}$ operator by the same argument as $\mathrm{BPP\subseteq P/poly}$: using the Chernoff–Hoeffding bound, the ...
- 16.9k
10
votes
What are examples of how non-uniformity can be useful?
One example is $\mathbf{NL} \subseteq \mathbf{UL}/\text{poly}$. This theorem was proven by Reinhardt and Allender in their paper "Making Nondeterminism Unambiguous". Without going into the details, ...
- 1,733
10
votes
Accepted
Linear circuit complexity classes
It follows from work of Valiant [1, 2] that linear-size $\textrm{NC}^1$ can be simulated by $2^{O(n / \log \log n)}$-size circuits of depth three and unbounded fan-in.
For a nice exposition of this ...
- 743
10
votes
Accepted
$AC^0$[subexp] vs. NC
No, $\mathrm{AC}^0[2^{n^\delta}]$ is not included in NC; it is not even included in $\mathrm{SIZE}[2^{n^\epsilon}]$ for $\epsilon<\delta$. Indeed, any Boolean function on $n^\delta$ inputs, padded ...
- 16.9k
10
votes
Accepted
Is it $NP$-hard to check whether a given algebraic circuit computes permanent?
This is unlikely to be NP-complete, as it can be solved in coRP, using a few calls to PIT. (It follows that this problem is not NP-complete unless $\mathsf{NP} = \mathsf{RP}$ and $\mathsf{PH} = \...
- 36.9k
9
votes
Accepted
What are bounded-treewidth circuits good for?
We now understand that for any fixed bound $k \in \mathbb{N}$ on the treewidth, we can convert any Boolean circuit of treewidth less than $k$ to a so-called d-SDNNF circuit, in linear time and with ...
- 8,896
9
votes
What's the “smallest” complexity class for which an $\omega \hspace{.02 in}(n)$ circuit lower bound is known?
$S^p_2$ and $PP$ are both known not to have $n^k$-circuits for any fixed k and there is no known containment between them. Details in my blog post.
Update: As Rickey Demer points out, these results ...
- 8,616
9
votes
Accepted
Matrix vector multiplication algorithm using minimal number of additions
This is essentially the problem that motivated Valiant to introduce matrix rigidity into complexity (as far as I understand the history).
A linear circuit is an algebraic circuit whose only gates ...
- 36.9k
9
votes
Accepted
Are arithmetic circuits weaker than boolean?
The permanent would seem to qualify, at least conditionally (that is, assuming $\mathsf{VP}^0 \neq \mathsf{VNP}^0$). Note that the Boolean version of the permanent is just to decide whether a given ...
- 36.9k
9
votes
Consequences of $NP\subseteq P/poly$ to $BQP$
If $\mathsf{NP} \subseteq \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma_2 P}$ (Karp-Lipton), and in fact to $\mathsf{S_2 P}$ (attributed to Sengupta by Cai, FOCS 2001), and even to ...
- 36.9k
9
votes
P/Poly vs Uniform Complexity Classes
$\let\mr\mathrm$There are several results in the literature stating that a certain class $C$ satisfies $C\nsubseteq\mr{SIZE}(n^k)$ for any $k$, and usually it is straightforward to pad them to show ...
- 16.9k
9
votes
Accepted
VC dimension of polynomials over tropical semirings?
I've realized that the answer to my question is - yes: the VC dimension of degree $\leq d$ polynomials on $n$ variables over any tropical semiring is at most a constant times $n^2\log(n+d)$. This can ...
- 6,685
9
votes
Accepted
What are the consequences of $P \subseteq L/poly$?
One simple consequence is $\mathbf{P}/\text{poly} = \mathbf{L}/\text{poly}$. Proof: For any language $A \in \mathbf{P}/\text{poly}$, there is a language $B \in \mathbf{P}$ and a sequence of polynomial-...
- 1,733
9
votes
Why is the circuit class AC0 unavoidable?
First of all, would you agree that DNFs and CNFs are a natural object to study? At the very least, if you believe that decision trees are a natural object to study, then so should be DNFs and CNFs, ...
- 5,350
9
votes
Accepted
How small can be a layered boolean circuit for a function with circuit complexity $s$?
As far as I know, three classes of layered circuits have been studied. In all of these definitions arcs are allowed only between two adjacent layers.
A circuit is called synchronous (Harper 1977) if ...
- 2,247
9
votes
Depth reduction for Boolean circuits
Unfortunately, the best known depth reductions for Boolean circuits only work for very restricted classes of circuits. Valiant (Valiant; Viola) proved that a circuit of size $O(n)$ and depth $O(\log{n}...
- 2,247
Only top scored, non community-wiki answers of a minimum length are eligible