Questions tagged [circuit-complexity]
Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.
363
questions
50
votes
0
answers
2k
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 $...
- 6,615
41
votes
3
answers
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^{...
- 26.4k
40
votes
3
answers
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 ...
- 13.4k
39
votes
3
answers
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 ...
- 10.9k
36
votes
5
answers
2k
views
Integer multiplication when one integer is fixed
$n$ is a parameter in the problem.
For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$.
Problem: Given $n$ what is the complexity of ...
- 12.5k
34
votes
3
answers
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/...
- 21.3k
33
votes
2
answers
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 ...
- 2,786
33
votes
0
answers
1k
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.
...
- 6,615
29
votes
1
answer
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 ...
- 5,983
28
votes
2
answers
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 ...
- 381
28
votes
3
answers
1k
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 ...
- 5,983
27
votes
1
answer
724
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
...
- 443
25
votes
4
answers
997
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 ...
- 959
25
votes
3
answers
922
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 ...
- 251
25
votes
2
answers
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, ...
- 13.3k
25
votes
1
answer
800
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$ (...
- 3,860
25
votes
1
answer
1k
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 ...
- 6,615
25
votes
1
answer
895
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 ...
- 13.3k
23
votes
4
answers
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 ...
- 21.3k
23
votes
2
answers
923
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 ...
- 845
22
votes
6
answers
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 ...
- 16.3k
22
votes
2
answers
575
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 ...
- 13.3k
22
votes
2
answers
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? ...
- 537
22
votes
2
answers
2k
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 ...
- 1,334
22
votes
1
answer
563
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 (...
- 21.3k
22
votes
0
answers
717
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 ...
- 4,823
21
votes
2
answers
961
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$...
- 10.1k
21
votes
6
answers
1k
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 ...
- 376
21
votes
2
answers
588
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 ...
- 544
21
votes
4
answers
1k
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 ...
- 13.5k
21
votes
2
answers
1k
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 ...
- 3,993
21
votes
3
answers
1k
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 ...
- 6,615
21
votes
1
answer
589
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 ...
- 6,615
20
votes
4
answers
1k
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 ...
- 3,823
20
votes
1
answer
986
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 ...
- 2,198
20
votes
2
answers
638
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 ...
- 5,983
20
votes
2
answers
891
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. (...
- 13.3k
20
votes
1
answer
3k
views
Is BPP vs. P a real problem after we know BPP lies in P/poly?
We know (for now about 40 years, thank Adleman, Bennet and Gill) that the inclusion BPP $\subseteq$ P/poly, and an even stronger BPP/poly $\subseteq$ P/poly hold.
The "/poly" means that we work non-...
- 6,615
19
votes
2
answers
608
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 ...
- 10.7k
19
votes
2
answers
947
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 ?
- 523
19
votes
1
answer
735
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 ...
- 21.3k
19
votes
1
answer
950
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 ...
- 13.3k
18
votes
2
answers
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 ...
- 445
18
votes
2
answers
858
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
2
answers
634
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 ...
- 181
18
votes
2
answers
991
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$ ...
- 279
18
votes
1
answer
433
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 ...
- 689
18
votes
0
answers
509
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 ...
- 5,983
17
votes
5
answers
398
views
Stronger notions of uniformizations?
One gap that I was always aware that I don't really understand is between non uniform and uniform computational complexity where the circuit complexity represents the non uniform version and Turing ...
- 5,983
17
votes
2
answers
724
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....
- 7,479