Questions tagged [circuit-complexity]
Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.
414 questions
1
vote
1
answer
112
views
Given a Boolean circuit with $n$ gates, can you find an equivalent Boolean formula in the full binary basis with a proportional size?
I am aware that when converting a Boolean circuit to a formula in the De Morgan basis, the increase in size is superlinear (a common example being the $n$-bit parity function), but what about ...
- 113
3
votes
1
answer
254
views
What lower bounds are known for matrix multiplication?
Raz gives a $\Omega(n^2 \log n) $ lower bound but only if the circuit is restricted to bounded coefficients arithmetic circuits, that is, you are only allowed to multiply by real numbers of magnitude ...
- 358
1
vote
0
answers
125
views
What is the smallest algebraic circuit to compute product of a vector by a fixed square matrix?
Given a fixed $n \times n $ square matrix $M$ over a field of size $ \Omega(n^2) $.
What is the size $s_M$ of the smallest circuit that computes the function $f(x)= Mx$ ?
What is the largest $s_M$ ...
- 358
0
votes
0
answers
68
views
Is lexicographically first topological order on DAG inputs in non-uniform $TC^0$?
I will mention that I am already pretty sure lexicographically first topological order is $NL$ complete (see here), so I think this question might be somewhat equivalent to $NL \subseteq TC^0$` but I ...
- 9
0
votes
0
answers
91
views
Isn't uniformity critical in defining $AC^0$?
In the paper »Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity« by Hao et al.[1] there are no uniformity restrictions imposed upon the definition of the ...
4
votes
1
answer
217
views
$\mathbf{P}$-uniform vs. $\mathbf{DLOGTIME}$-uniform $\mathbf{AC}^0$
I am interested in knowing what is the standard notion of uniformity for $\mathbf{AC}^0$. Wikipedia seems to suggest this should be $\mathbf{DLOGTIME}$-uniform, and this was also what I had in mind ...
- 1,398
3
votes
0
answers
167
views
Uniformity of threshold circuits for sorting $n$ bit numbers
I am new to circuit complexity theory. I came across the result that sorting
$n$ numbers with $n$ bits can be done using constant-depth threshold circuits (as discussed here: Complexity of sorting). I ...
9
votes
0
answers
113
views
Is Maximum Independet Set P-complete on perfect graphs?
Perfect graphs are a well-known class of graphs. A graph $G$ is perfect if $\omega(G)=\chi(G)$, and this also holds for all induced subgraphs of $G$. One of the main (famous) algorithmic results for ...
- 3,957
0
votes
0
answers
102
views
Division by constant power in $ACC^0$?
Multiplication and division of two $n$-bit integers is not known to be in $ACC^0$. By Multiplication by constant in $ACC^0$? we have
Multiplication by a constant is in $AC^0$
Division by a constant ...
- 13.7k
5
votes
0
answers
117
views
Natural problems complete for AC$^1$?
AC$^1$ is the class of problems we can decide with a (uniform) circuit that has size $n^{O(1)}$, depth $O(\log n)$ and unbounded fan-in. This seems like a fairly natural class, so I would expect a few ...
- 3,957
1
vote
1
answer
165
views
Question about Shannon's theorem on circuit lower bounds
My question relates to Theorem 1.47 and its proof in Vollmer's book on circuit complexity.
Say you have a circuit of size $q$ with $n$ inputs, where each (non-input) gate could be one among $B$ types ...
- 13
3
votes
0
answers
106
views
The Switching Lemma in Statistical Mechanics?
Håstad’s switching lemma is a well-known result in circuit theory:
Suppose $f$ is expressible as a $k$-DNF, and let $\rho$ denote a random restriction that assigns random
values to $t$ randomly ...
- 31
2
votes
0
answers
80
views
"Composition rank" over arbitrary binary functions
The majority of three Boolean variables $x,y,z$ can be expressed as
$$(x \wedge (y\vee z)) \vee (y \wedge z).$$
Thus we can express it as a composition of 4 binary functions.
As another example, the ...
- 4,605
5
votes
0
answers
90
views
Relationship between quantifier depth and AC^0 circuit size for fixed depth circuits
I am looking for results that relate the size of fixed depth $\text{AC}^0$ circuits to the quantifier depth of first-order logic formulae they can recognise. More formally:
For $\text{AC}^0$ circuits ...
- 51
4
votes
0
answers
168
views
How deep of a quantum (or classical) circuit from $n$ bits to $n$ bits is needed before it's computationally indistinguishable from a random oracle?
I am considering a simple test for quantumness relying on the coherent evaluation of a (classical) Boolean circuit with randomly chosen (classical) one, two, and three-qubit gates.
To wit, suppose I ...
- 1,267