Skip to main content
Share Your Experience: Take the 2024 Developer Survey
22 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 ...
usul's user avatar
  • 7,615
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 ...
Dylan McKay's user avatar
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 ...
Andrew Morgan's user avatar
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 ...
Emil Jeřábek's user avatar
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&...
Ryan Williams's user avatar
11 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 ...
Emil Jeřábek's user avatar
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 ...
Andrew Morgan's user avatar
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$ ...
Jan Johannsen's user avatar
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).
Emil Jeřábek's user avatar
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 ...
Emil Jeřábek's user avatar
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, ...
William Hoza's user avatar
  • 1,743
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 ...
Robert Andrews's user avatar
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 ...
Emil Jeřábek's user avatar
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} = \...
Joshua Grochow's user avatar
10 votes
Accepted

Trade-off for Barrington's theorem

Perhaps what you're looking for is theorem 2 in Cleve, R. Towards optimal simulations of formulas by bounded-width programs. I don't think the precise statement that you're asking about is known (note ...
Ryan Williams's user avatar
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 ...
Lance Fortnow's user avatar
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 ...
a3nm's user avatar
  • 9,449
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 ...
Joshua Grochow's user avatar
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 ...
Stasys's user avatar
  • 6,765
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-...
William Hoza's user avatar
  • 1,743
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, ...
Or Meir's user avatar
  • 5,615
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 ...
Alex Golovnev's user avatar
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}...
Alex Golovnev's user avatar
9 votes
Accepted

Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits

$\def\M#1{\mathrm{MOD}_{#1}}\def\F#1{\mathbb F_{#1}}$I don’t know of a reference, but here is one way how to prove the result. I’ll do it in three stages, each using one new idea: (1) multilinear ...
Emil Jeřábek's user avatar
8 votes
Accepted

Is SAT a context-free language?

Just an alternative proof using a mix of well known results. Suppose that: variables are expressed with the regular expression $d = (+|-)1(0|1)^*$ and that the (regular) language (over $\Sigma = \{0,...
Marzio De Biasi's user avatar
8 votes
Accepted

How powerful is $ACC^0$ circuit class in average case?

There seem to be typos in what you wrote; I take it you're asking: is there a function $f \in NEXP$ such that for all polynomials $p$ and infinitely many $n$, no ACC0 circuit of $p(n)$ size can ...
Ryan Williams's user avatar
8 votes
Accepted

Nondeterminism is on average useless for circuits?

1) Realize that nondeterminism is a red herring here. You could have used alternation or circuits that have gates that solve the halting problem. It boils down to a simple counting argument that once ...
Lance Fortnow's user avatar
8 votes
Accepted

Is there any quantum analog of the VP vs. VNP problem?

This is not quite an answer, but some observations that are too long for a comment. I've thought about this question before, but not being an expert in quantum I was never really able to resolve it. ...
Joshua Grochow's user avatar
8 votes

Does $NC=P$ imply the collapse of Polynomial Hierarchy?

It appears that nobody has provided an answer to this question. One reason may be that it's not clear what you mean by "the rest of the polynomial hierarchy". Indeed, it's not clear that P=...
Eric Allender's user avatar
8 votes
Accepted

Relation between ACC^0 and DTIME

Most people would believe that DTIME(n) contains problems that are not in non-uniform ACC^0 (poly size). One reason is that the containment of DTIME(n) in non-uniform ACC^0 implies P is contained in ...
Ryan Williams's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible