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 ...
user avatar
21 votes
Accepted

How many negations do we need to compute monotone functions?

Markov proved that any function of $n$ inputs can be computed with only $\lceil \log (n+1)\rceil$ negations. An efficient constructive version was described by Fisher. See also an exposition of the ...
user avatar
  • 2,789
19 votes
Accepted

Boolean Functions Where Sensitivity Equals Block Sensitivity

Recently, I proved that s(f) = bs(f) for unate functions and read-once functions over the Boolean operators AND, OR and EXOR, and my paper including the results was accepted to TCS 2014. (http://dx....
user avatar
18 votes
Accepted

smallest circuit size using XOR gates

This is NP-hard. See: Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. http://link.springer.com/article/10.1007/s00145-012-9124-7 The ...
user avatar
18 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 ...
user avatar
  • 7,090
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}...
user avatar
  • 992
16 votes
Accepted

Arithmetic circuits with just one threshold gate

The answer is “yes” if $t=n^{O(1)}$. More generally, a threshold $\{+,\cdot\}$-circuit of size $s$ with threshold $t$ can be simulated by a $\{\lor,\land\}$-circuit of size $O(t^2s)$. First, observe ...
user avatar
16 votes
Accepted

For what c is division by c in AC0?

Addition and subtraction of binary numbers are in $\mathsf{AC^0}$. For any constant number $c$, $x \bmod c$ is $\mathsf{AC^0}$ reducible to division by $c$ ($\lfloor x/c \rfloor$): $$x \bmod c = x ...
user avatar
  • 3,236
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 ...
user avatar
15 votes
Accepted

What is an equivalent definition of mP/poly in terms of a Turing machine?

There is a notion of a monotone non-deterministic and, more generally, alternating Turing machine in the paper Monotone Complexity by Grigni and Sipser. Since polynomial time is the same as ...
user avatar
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 ...
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 ...
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 ...
user avatar
14 votes
Accepted

Why is HAMILTONIAN CYCLE so different from PERMANENT?

The following is a proof over any ring of characteristic zero that the Hamiltonian cycle polynomial is not a polynomial-size monotone projection of the permanent. The basic idea is that monotone ...
user avatar
14 votes

Scope of natural proofs barrier

Let $f: \{0,1\}^* \rightarrow \{0,1\}$ be a function, and let $C$ be a class of algorithms working on finite slices of $f$. Every circuit lower bound whatsoever is a proof that $f \notin C$, for some $...
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&...
user avatar
12 votes
Accepted

Oracular separations between poly- and log-depth quantum circuits

I apologize; I was too glib when I wrote that. While I believe it's possible to prove an oracle separation between $BQP$ and $BPP^{BQNC}$ using current techniques, it hasn't been done (12 years after ...
user avatar
11 votes

Can one prove $\mathsf{PARITY} \notin \mathsf{AC}^0$ using Linial-Mansour-Nisan theorem and the knowledge of fourier spectrum of $\mathsf{PARITY}$?

LMN theorem shows that if f is a boolean function$(f:\{-1,1\}^n \rightarrow \{-1,1\})$ computable by an $\text{AC}^0$ circuit of size M, $$\sum_{S:|S|> k} \hat f(S)^{2} \leq 2^{-\Omega(k/(\log M)^{...
user avatar
  • 193
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, ...
user avatar
  • 10.8k
11 votes
Accepted

Why is shifting bits different from shifting qubits?

It's complicated, and depends on whether you approach quantum computing as a technology or a model of computation; and whether you are interested in universal quantum computation, or a special ...
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).
user avatar
10 votes

What is the minimum size of a circuit that computes PARITY?

This gate-elimination lower bound does not match Marzio’s upper bound, but it’s a start. Proposition: Every unbounded fan-in AND/OR/NOT circuit computing parity on $n\ge2$ variables contains at ...
user avatar
10 votes
Accepted

Does ${\bf AC^0PAD} = {\bf PPAD}$?

$\def\ac{\mathrm{AC}^0}$Yes, $\ac\mathrm{PAD}=\mathrm{PPAD}$. (Here and below, I’m assuming $\ac$ is defined as a uniform class. Of course, with nonuniform $\ac$ we’d just get $\mathrm{PPAD/poly}$.) ...
user avatar
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 ...
user avatar
10 votes
Accepted

"Largest" class properly contained in PSPACE for a random oracle

Yes, because $PP^{PH}=PP$ relative to a random oracle. Follows from Toda-Ogihara
user avatar
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 ...
user avatar
10 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 ...
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 ...
user avatar
10 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$ ...
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, ...
user avatar
  • 1,733

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