# Tag Info

### 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 ...
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 ...
Accepted

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

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

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

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

### 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, ...
### How small can be a layered boolean circuit for a function with circuit complexity $s$?
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}...