Questions tagged [circuit-complexity]
Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.
386
questions
3
votes
1
answer
344
views
Intuition on Lupanov's Upper Bound on Circuit Size
The following result, by Lupanov, is a classic in the theory of Boolean function complexity:
Theorem: For every boolean function $f$ of $n$ variables:
$$C(f) \leq (1 + \alpha_n)\frac{2^n}{n}, \text{ ...
- 133
5
votes
1
answer
386
views
Relation between ACC^0 and DTIME
In a breakthrough Ryan Williams (STOC13/14) showed that $\mathsf{NEXP} \nsubseteq \text{non-uniform } \mathsf{ACC}^0$.
How far can we potentially push this result?
In other words, what is the largest $...
- 223
1
vote
0
answers
51
views
Pfaffian orientation algorithm for planar graphs
I was studying finding a pfaffian orientation of a planar graph in $NC$. In Vazirani's Paper on NC Algorithms for Computing the Number of Perfect Matchings in $K_{3,3}$-Free Graphs and Related ...
- 288
2
votes
0
answers
71
views
On the multiplicative overhead 2 in the construction of pairwise independent hashing from ERCs
A standard method of constructing pairwise independent hash function from error-correcting code is as follows:
Given a generator matrix $G$ of a distance-$d$ linear error-correcting code mapping $m$ ...
0
votes
0
answers
75
views
Original references for Karp-Lipton theorem improvement by Sipser
The Wikipedia article about the Karp-Lipton theorem ($NP\subseteq P/poly$ implies $\Sigma_2=\Pi_2$), says the following:
The Karp–Lipton theorem is named after Richard M. Karp and Richard J.
Lipton, ...
- 1,588
4
votes
1
answer
69
views
Does there exist constant overhead reduction between common cryptographic primitives?
I have proved that there exist such reduction between error-correcting codes and exposure resilient functions, which is because that the transpose of a generator matrix for a ERC mapping $\mathbb{F}_2^...
10
votes
1
answer
299
views
Does $NC=P$ imply the collapse of Polynomial Hierarchy?
If $NC=P$ (with a constructive polynomial time algorithm that converts any $P$ time circuit to a $NC$ circuit), what impact would it have on the rest of the Polynomial Hierarchy?
Couldn't find much in ...
- 468
5
votes
0
answers
59
views
W[t]-containment of partial covering problems
I would like to know more about the W[t]-containment of partial covering problems. Especially, I am interested in the question whether Partial Set Cover (Problem Definition at the end of the question) ...
- 81
2
votes
0
answers
54
views
Intermediate problems between $CC^0$ and $ACC^0$
Definitions
$CC^0[m]$ is the set of languages decidable by constant-depth polynomial-size circuits consisting only of unbounded-fanin $MOD_m$ gates. We write $CC^0$ to mean the union over all $m$. $...
- 1,204
3
votes
0
answers
91
views
Reference Request: Circuit Complexity Theory Course
I want to learn circuit complexity theory. I have found this book "Introduction to Circuit Complexity
A Uniform Approach" by Heribert Vollmer. I have also found lecture notes of one course
...
- 288
2
votes
1
answer
115
views
doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing
In the survey see section 5.3.2 : Depth reduction for arithmetic circuits for notations.
I follow the proof of the following two identities :
$[u]=\Sigma_{w\in \cal{F}_m}[u:w].[w]$ where $deg(u)\geq ...
- 123
0
votes
1
answer
197
views
Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties
Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define
$$
f_{\mathfrak S}(z) := \sum_{\...
- 291
3
votes
2
answers
160
views
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
Let $n$ be a large positive integer. Give a nonempty collection $\mathcal S$ of subsets of $[n] := \{1,2,\ldots,n\}$, define an inner-product on $\mathbb R^n$ by
\begin{eqnarray}
\langle x,y\rangle_{\...
- 291
6
votes
0
answers
161
views
Are exponential lower bounds known against $MOD_6 \circ MOD_3$ circuits computing $OR$?
Background
What is currently known for depth-2 $CC^0$ circuits with restricted gate types:
In [1] it is shown that $(MOD_p)^k \circ MOD_m$ circuits (that is, $k$ layers of $MOD_p$ gates at the output)...
- 1,204
4
votes
0
answers
53
views
Quantum circuits vs quantum circuits w/ only local interactions?
If we restrict a quantum circuit to only have interactions between "nearby" qubits (for some connection topology that defines "nearby", as is the case in several actual quantum ...
- 36.9k
4
votes
1
answer
109
views
NC0 randomnes vs. non-uniformity
In
Ajtai and Ben-Or. A theorem on probabilistic constant depth
Computations. STOC '84, 1984
Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.
Is there a similar relation known for ...
- 41
0
votes
1
answer
152
views
What is the simplest one-way function (in terms of boolean circuit complexity)?
What is the simplest known one-way function?
By simplest, I mean, when implemented as boolean logic, the number of AND/OR/NOT gates needed is minimal (smallest circuit complexity).
(I'm trying to find ...
8
votes
1
answer
230
views
Is it $NP$-hard to check whether a given algebraic circuit computes permanent?
Given are a natural number $n\in\mathbb{N}$ and a polynomial $P$ in the form of an arithmetic circuit $C$ over $\mathbb{Z}$ (a circuit which only uses $+$ and $\times$ gates and integer constants as ...
user67795
2
votes
1
answer
184
views
Value of studying boolean function complexity through circuits complexity nowadays
Apparently boolean function complexity analysis through circuit complexity has a limit (as they are natural proofs), and this means it is not possible to proof $P \not= NP$ unless there are no one-way ...
1
vote
0
answers
106
views
Boolean formula complexity of arithmetic expressions
This is a followup question to this other question, where I was told that multiplication is in $NC^1$ so can be computed with a circuit of polynomial size and logarithmic depth, hence also with a ...
- 1,588
5
votes
1
answer
306
views
Formula complexity of arithmetic multiplication
I'd need some bounds on the size of Boolean formulas (over $\land$, $\lor$ and $\neg$) computing the multiplication of two integers.
I'm not an expert in circuit complexity and I'm crawling through ...
- 1,588
0
votes
0
answers
44
views
Do uniformity lower than DLOGTIME rlead to same result?
Maybe an answer to this
Here input of length and position is binary rather than unary, so traditional "DLOGTIME-uniform" is now "O(n)-uniform". (If traditional "DLOGTIME-...
- 111
2
votes
1
answer
134
views
Counting argument for LTF circuits
In Boolean circuit complexity, Shanon's counting argument shows that a random Boolean function on $n$-input bits requires a circuit of size $\Omega(2^n/n)$ to be computed by a circuit made of AND, OR ...
- 327
8
votes
1
answer
145
views
Reductions and projections in circuit complexity
I'm struggling to find a good reference that defines the difference between projection and monotone projection in the context of Boolean functions and circuit complexity.
My understanding is that a ...
- 851
0
votes
0
answers
96
views
Non-uniformity assumptions in circuit complexity
I recently came accross the following standard inclusion of complexity classes:
$$\textbf{NC}^0 \subseteq \textbf{AC}^0 \subseteq \textbf{NC}^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \...
- 851
5
votes
1
answer
143
views
Can a sum of polynomially many determinants be expressed as a single determinant of a poly-size matrix?
(copied from a mathoverflow question because I realized this may be more appropriate for it) Let $A_1,A_2,...,A_k$ be $N$-by-$N$ matrices, with indeterminate entries in some field (say real or complex ...
- 225
3
votes
0
answers
89
views
Sparsity Bounds for Probabilistic Polynomials
Has there been any research done on proving sparsity lower bounds for probabilistic polynomials (over the Reals) for Majority?
A probabilistic polynomial is a distribution of polynomials $D$ such that ...
- 71
1
vote
0
answers
135
views
2
votes
0
answers
74
views
Pebble games and conversions to bounded width circuits
Questions: Are there references which mention the relation between pebble games and conversions to bounded width circuits?
Here, "conversions to bounded width circuits" means that circuits ...
- 689
5
votes
0
answers
112
views
Complexity of approximating boolean functions with circuits
Let $f$ be a boolean function on $n$ variables - say we want to find the smallest circuit $C$ where $C(x)=f(x)$ for all but an $\epsilon$ fraction of inputs $x \in \{0,1\}^n$. What is known about the ...
- 51
2
votes
0
answers
67
views
Does advice reduce depth?
Specifically I'm thinking about NC$^1$/poly and NC$^1$/rpoly (randomized advice). Are there any statements like
"If $\{C_n\}$ is a family of NC$^1$/(r)poly circuits with depth $C\log n$, then ...
- 121
3
votes
1
answer
117
views
$\mathrm{AC}^0$ upper bound for Hamming weight
Consider Theorem 11 of this paper (S. Aaronson, BQP and the Polynomial Hierarchy), which says:
Any depth $d$ circuit that accepts all $n$ bit strings of Hamming
weight $\frac{n}{2} + 1$ and rejects ...
- 173
5
votes
1
answer
163
views
$AC^0$[subexp] vs. NC
My question is about the possibility of trading size for depth in circuits.
Under what conditions is it true (or, plausible) that $AC^0[2^{n^\delta}] \subseteq NC^i$ for some constants $\delta < 1, ...
- 187
5
votes
2
answers
211
views
Circuit uniformities more restrictive than $DLOGTIME$
Definitions:
The "direct connection language" of a circuit family is the set of tuples $\langle t, a, b, y \rangle$, where $a$ and $b$ are node/gate numbers in the $n$th circuit in the ...
- 1,204
8
votes
1
answer
138
views
Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits
It is mentioned in multiple papers [1], [2] that $MODp \circ MODq$ circuits for two distinct primes $p, q$ can compute arbitrary functions in exponential size. However, [1] provides no citation for ...
- 1,204
3
votes
0
answers
105
views
Do random functions have synchronous, alternating circuits with non-injective first layers?
After discussing in the comments, I think a clearer definition of the question is as follows: for a random function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, what is the probability that there exists a ...
- 1,572
2
votes
0
answers
101
views
Recovering the inputs to Boolean circuits after partial evaluation
This question discusses Boolean Circuits and Boolean functions from $n>1$ inputs to one Boolean output. Notation: $\textit{arity}(\mathcal{C})=n$ if $\mathcal{C}$ takes $n$ inputs, similarly for ...
- 424
10
votes
1
answer
231
views
Can exponential-size depth-2 $CC^0[m]$ circuits with generalized $MOD_m$ gates compute arbitrary functions from $Z/mZ$ to $Z/2Z$?
Terminology
$CC^0[m]$ is the set of polynomial-sized, constant depth circuits consisting entirely of $MOD_m$ gates for some $m \geq 2$, where a $MOD_m$ gate outputs a 1 if and only if the sum of its ...
- 1,204
-1
votes
1
answer
88
views
Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?
I understand the logic minimization problem is NP-hard when given the onset, since the last step is equivalent to set cover optimization.
If instead we are given a partial truth table, and we just ...
- 203
0
votes
0
answers
89
views
Useful primitives CPUs could provide, from TC0 (or NC1)
I just listened to XYZ talking about "How Universal Is the Idea of Numbers?", and bashing the concept as an accidental historical artifact. He suggested that totally different computational ...
- 3,033
3
votes
0
answers
118
views
Complete problems for $(NP\cap CoNP)/poly$ class and universal representations
It is conjectured that $NP\cap CoNP$ does not have a complete problem with respect to the polynomial-time many-to-one reductions. I would like to know the current knowledge about the nonuniform ...
- 332
4
votes
0
answers
207
views
What does width $4$ permutation branching program correspond to?
$L$ can be computed by a family of programs over $S_3$
of polynomial length if and only if $L$ can be computed by a family of $MOD3 ◦ MOD2$ circuits of
polynomial size.
$L$ can be computed by a family ...
- 12.8k
8
votes
1
answer
223
views
Monotone circuit representations of paths in a graph?
Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every ...
- 8,896
3
votes
1
answer
158
views
$ACC^0$ implementation of a boolean function
Consider the symmetric boolean function
$$F(x_1,\dots,x_n)=1\iff\sum_{i=1}^nx_i\mbox{ is a square}.$$
It is implementable in $TC^0$.
Is there an $ACC^0$ implementation?
The reason I ask is there seems ...
- 93
5
votes
0
answers
162
views
Trading treewidth for depth in Boolean circuits
We know that languages defined by (poly-sized) Boolean formulae equals $\mathbf{NC}^1$: that Boolean formulae can be simulated in $\mathbf{NC}^1$ was shown by Brent/Spira [B,S], and the converse is ...
- 223
0
votes
0
answers
60
views
Is anything known about NC$^1$ with NP oracle
A few things are known about the class $\textsf{L}$ provided with an $\textsf{NP}$ oracle ($\textsf{L}^\textsf{NP} = \Theta_2^\textsf{P}$ has attracted a bit of attention, for instance [1]) On the ...
- 803
1
vote
1
answer
96
views
Variable wire weights in DLOGTIME-uniform circuits
The definition of a $DLOGTIME$-uniform circuit family is based on a Turing machine that accepts the language $\langle t, a, b \rangle$, where gate $a$ is of type $t$ and has gate $b$ as a child, ...
- 1,204
7
votes
2
answers
849
views
Why should we believe that $NEXP \not \subset P/poly$
I am sorry if this is not an advanced question. Most computer scientists believed that $NEXP \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used ...
- 327
12
votes
2
answers
326
views
Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings
We say that a pair $(P,N)$ of subsets of strings from $\{0,1\}^n$ is an $n$-pair if $|P|=|N|=n$. Intuitively, sucha a pair consists of a set $P$ with $n$ positive $n$-bit strings, and a set $N$ with $...
- 1,062
1
vote
1
answer
100
views
Composition theorem for randomized communication complexity
I am currently organizing the literature of composition theorem, and I found the paper by https://www.research.cs.rutgers.edu/~troyjlee/Composition.pdf, in their theorem 5, I find
$$ R_{1/4} (f \circ ...
- 113