Questions tagged [circuit-complexity]
Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.
327
questions
45
votes
0answers
1k views
Monotone complexity of s-t connectivity
In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide
whether there is a path between all $n^2$ pairs $...
40
votes
3answers
2k views
Circuit lower bounds over arbitrary sets of gates
In the 1980s, Razborov famously showed that there are explicit monotone Boolean functions (such as the CLIQUE function) that require exponentially many AND and OR gates to compute. However, the basis ...
40
votes
3answers
1k views
A fixed-depth characterization of $TC^0$? $NC^1$?
This is a question about circuit complexity. (Definitions are at the bottom.)
Yao and Beigel-Tarui showed that every $ACC^0$ circuit family of size $s$ has an equivalent circuit family of size $s^{...
39
votes
3answers
2k views
Why are mod_m gates interesting?
Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's.
What's so ...
35
votes
5answers
2k views
Integer multiplication when one integer is fixed
Let $A$ be a fixed positive integer of size $n$ bits.
One is allowed to pre-process this integer as appropriate.
Given another positive integer $B$ of size $m$ bits, what is the complexity of ...
33
votes
2answers
1k views
Cohomological approach to boolean complexity
A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this ...
31
votes
3answers
2k views
Is $AC^0/poly \cap NP$ contained in $P$?
I thought I would share this question as it might be interesting for other users here.
Assume that a function which is in a uniform class (like $NP$) is also in a small nonuniform class (like $AC^0/...
29
votes
1answer
2k views
Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates
Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free ...
29
votes
0answers
727 views
Is BPP= P known for ANY uniform model of computation?
Many believe that BPP $=$ P "should" hold for Turing machines. We even have some "witnesses" for this: otherwise some "strange" things would happen; see e.g. this paper by Implagliazzo and Wigderson.
...
28
votes
2answers
1k views
Kolmogorov's conjecture that $P$ has linear-size circuits
In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find ...
27
votes
1answer
685 views
Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation
What is the complexity of deciding whether an $\mathsf{NC}^0$ circuit
with $n$ input bits and $n$ output bits computes a permutation
of $\{0,1\}^n$? in the other words, whether every bit strings in
...
27
votes
3answers
983 views
A Notion of Monotone Quantum Circuits
In computational complexity there is an important distinction between monotone and general computations and a famous theorem by Razborov asserts that 3-SAT and even MATCHING are not polynomial in the ...
25
votes
4answers
906 views
What's the “smallest” complexity class for which a superlinear circuit bound is known?
Apologies for asking a question that must surely be in a lot of standard references. I'm curious about exactly the question in the title, in particular I am thinking of Boolean circuits, no depth ...
25
votes
3answers
855 views
Constructivity in Natural Proof and Geometric Complexity
Recently, Ryan Willams proved that Constructivity in Natural Proof is unavoidable to derive a separation of complexity classes : $\mathsf{NEXP}$ and $\mathsf{TC}^{0}$.
Constructivity in Natural ...
25
votes
2answers
2k views
Formula size lower bounds for AC0 functions
Question:
What is the best known formula size lower bound for an explicit function in AC0? Is there an explicit function with an $\Omega(n^2)$ lower bound?
Background:
Like most lower bounds, ...
24
votes
1answer
787 views
Approximate degree of $\textrm{AC}^0$
EDIT (v2): Added a section at the end on what I know about the problem.
EDIT (v3): Added discussion on threshold degree at the end.
Question
This question is mainly a reference request. I don't ...
23
votes
1answer
736 views
Is $AC^0$ with bounded fanout weaker than $AC^0$?
In the survey "Small Depth Quantum Circuits" by D. Bera, F. Green and S. Homer (p. 36 of ACM SIGACT News, June 2007 vol. 38, no. 2), I read the following sentence:
The classical version of $QAC^0$ (...
23
votes
1answer
869 views
Why is HAMILTONIAN CYCLE so different from PERMANENT?
A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a
polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment
$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such ...
22
votes
4answers
1k views
Monotone arithmetic circuits
The state of our knowledge about general arithmetic circuits seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have ...
22
votes
2answers
1k views
Lower bound for determinant and permanent
In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
21
votes
6answers
1k views
References on Circuit Lower Bounds
Preamble
Interactive proof systems and Arthur-Merlin protocols were introduced by Goldwasser, Micali and Rackoff and Babai back in 1985. At first, it was thought that the former is more powerful than ...
21
votes
2answers
740 views
What is the big version of NC?
$\mathsf{NC}$ captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time $O(\log^c n)$ using $O(n^k)$ parallel processors for some constants $c$...
21
votes
6answers
998 views
What is the best way to get a close-to-fair coin toss from identical biased coins?
(Von Neumann gave an algorithm that simulates a fair coin given access to identical biased coins. The algorithm potentially requires an infinite number of coins (although in expectation, finitely many ...
21
votes
4answers
957 views
What is the minimum size of a circuit that computes PARITY?
It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp.
(We define size as the number of AND and OR ...
21
votes
2answers
525 views
Lower bounds for constant-depth formulae?
We know a lot about the limitations of (polynomial size) constant-depth circuits. Since (polynomial size) constant-depth formulae are an even more restricted model of computation, all problems known ...
21
votes
2answers
1k views
Are AND&OR circuits P-complete?
The AND&OR gate is a gate which is given two inputs and returns their AND and their OR. Are circuits made only out of the AND&OR gate, without fanout, capable of doing arbitrary computations? ...
21
votes
2answers
992 views
Can addition be carried out in less than depth 5?
Using carry look ahead algorithm we can compute addition using a polynomial size depth 5 (or 4?) $AC^0$ circuit family. Is it possible to reduce the depth? Can we compute the addition of two binary ...
21
votes
3answers
913 views
Clique problem on fixed graphs
As we know, the $k$-clique function $CLIQUE(n,k)$ takes a (spanning) subgraph $G\subseteq K_n$ of a complete $n$-vertex graph $K_n$, and outputs $1$ iff $G$ contains a $k$-clique. Variables in this ...
21
votes
1answer
513 views
Arithmetic circuits with just one threshold gate
When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes some
function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a boolean function, we can just add
one fanin-1 ...
21
votes
2answers
805 views
Circuit lower bounds and kolmogorov complexity
Consider the following reasoning:
Let $K(x)$ denote the Kolmogorov complexity of the string $x$.
Chaitin's incompleteness theorem says that
for any consistent and sufficiently strong formal ...
21
votes
1answer
511 views
Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?
Is there any plausible complexity/crypto hypothesis that rules out the possibility that polynomial size circuits have subexponential-size (i.e. $2^{O(n^\epsilon)}$ with $\epsilon<1$) bounded-depth (...
20
votes
2answers
463 views
Relation between $AC^0$ and regular languages
Let $\mathsf{REG}$ be the class of all regular languages.
It is known $\mathsf{AC}^0 \not\subset \mathsf{REG}$ and $\mathsf{REG} \not\subset \mathsf{AC}^0$. But is there any characterization for ...
20
votes
2answers
614 views
Bounded depth probability distributions
Two related questions about bounded depth computing:
1) Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem ...
20
votes
2answers
818 views
Problems between NC and P: How many have been resolved from this list?
In the paper "A Compendium of Problems Complete for P" by Greenlaw, Hoover and Ruzzo (PS) (PDF), there is a list of problems in P that are not known to be in NC and not known to be P-complete either. (...
20
votes
0answers
530 views
What is the power of general poly-size permutation branching programs?
Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions ...
19
votes
4answers
878 views
Parity and $AC^0$
Parity and $AC^0$ are like inseparable twins. Or so it has seemed for the last 30 years. In the light of Ryan's result, there will be renewed interest in the small classes.
Furst Saxe Sipser to Yao ...
19
votes
2answers
523 views
Arguments for/against Kolmogorov's conjecture about the circuit complexity of P
According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question Kolmogorov's conjecture that $P$ has ...
19
votes
1answer
766 views
Is there a better than linear lower bound for factoring and discrete log?
Are there any references that provide details about circuit lower bounds for specific hard problems arising in cryptography such as integer factoring, prime/composite discrete logarithm problem and ...
19
votes
1answer
675 views
Can we count in depth $\frac{\lg n}{\lg \lg n}$?
Can we compute an $n$-bit threshold gate by polynomial size (unbounded fan-in) circuits of depth $\frac{\lg n}{\lg \lg n}$? Alternatively, can we count the number of 1s in the input bits using these ...
19
votes
0answers
492 views
Are monotone Boolean functions in P well-approximated by monotone polynomial-size circuits?
Question 1: Is it true that for every polynomial $p(n)$ and $\epsilon >0$ there is a polynomial $q(n)$ such that every monotone Boolean function on $n$ variables that can be expressed by a Boolean ...
18
votes
2answers
2k views
Hierarchy theorem for circuit size
I think that a size hierarchy theorem for circuit complexity can be a major breakthrough in the area.
Is it an interesting approach to class separation?
The motivation for the question is that we ...
18
votes
2answers
815 views
A Boolean function that is not constant on affine subspaces of large enough dimension
I'm interested in an explicit Boolean function $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ with the following property: if $f$ is constant on some affine subspace of $\\{0,1\\}^n$, then the dimension ...
18
votes
2answers
545 views
Proof that circuit upper bounds for $E$ imply $P \neq NP$
In the official Clay problem description for P versus NP it's stated that $P \neq NP$ would follow from showing that "every language in $E$ [the class of languages recognizable in exponential time ...
18
votes
2answers
865 views
Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?
Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?
18
votes
1answer
862 views
Most efficient way to convert an $\text{AC}^0$ circuit to a circuit (of any depth) with gate fanout 1
EDIT (Aug 22, 2011):
I am further simplifying the question and putting a bounty on the question. Perhaps this simpler question will have an easy answer. I'm also going to strikethrough all the parts ...
17
votes
2answers
793 views
Status on circuit lower bounds for polylog-bounded depth circuits
Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ ...
17
votes
2answers
598 views
Better lower bounds than 3n for non-boolean functions?
Blum's $3n-o(n)$ lower bound is the best known circuit lower bound over the complete basis for an explicit function $f : \{0,1\}^n \to \{0,1\}$, cf. Jukna's answer to this question for related results....
17
votes
2answers
367 views
Is PARITY in QAC_0 (if that even makes sense)
As is well known PARITY cannot be done in poly-sized constant-depth circuits, and in
fact const-dept circuits require EXP number of gates.
What about QUANTUM circuits?
a) Can PARITY be done with a ...
17
votes
1answer
650 views
Example demonstrating the power of non-deterministic circuits
A non-deterministic Boolean circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "non-deterministic" inputs $y=(y_1,\dots,y_m)$. A non-deterministic circuit $C$ accepts ...
17
votes
1answer
380 views
Lower bounds for the size of nondeterministic circuits
It is known that the minimum size of $U_2$-circuits computing the parity function exactly equals $3(n-1)$. The lower bound proof is based on the gate elimination method.
Recently, I noticed that the ...
