Questions tagged [circuit-complexity]
Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.
398
questions
3
votes
0
answers
101
views
Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?
Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?
It is easy to show that the relaxed version ($\mathsf{E} \subset \mathsf{NP}$ and $\mathsf{P}^{\mathsf{NP}} \...
- 271
3
votes
1
answer
133
views
Given a directed graph with edge weights $0$ or $1$, is there a way to find an odd cycle in $\mathsf{NC}$?
Given a directed graph with edge weights $0$ or $1$, is there a way to find an odd weight cycle in $\mathsf{NC}$? I think the decision version is in $\mathsf{NC}$, but I am not sure about the search ...
- 43
0
votes
0
answers
33
views
Nonexistence of short integer program sequence which generates squares - II
Is there a way to show within a mixed integer linear program with constant number of integer variables, $poly(\log B)$ number of real variables and constraints of length $poly(\log B)$ (say length $\...
- 13.1k
6
votes
1
answer
156
views
Formula complexity of $n = 0 \pmod m$
Given two $k$-bits numbers $n$ and $m$, how large is a Boolean formula that computes whether $n = 0\pmod m$?
- 1,704
1
vote
2
answers
153
views
Use of transitive closure in proof of NC hierarchy collapse
Im looking at the proof of $NC^{i} = NC^{i+1} \implies NC = NC^i,\,i\geq 1$ in page 10 of the following article: https://www.cs.uoregon.edu/Reports/TR-1986-001.pdf
I understand the general idea ...
- 11
0
votes
0
answers
79
views
Is a problem, that is $L$-complete under non-uniform $AC^0$ reductions, necessarily outside of (non-uniform or uniform) $NC^1$?
I don't have much intuition about non-uniformity so the question may be quite naive.
- 43
4
votes
1
answer
141
views
Constructing vector valued boolean circuits from boolean circuits
This is a reference request. I'm
interested in the compositional construction of small boolean circuits
for vector-valued boolean functions $\phi : \mathbb{B}^m \rightarrow
\mathbb{B}^n$ for $n >...
- 11.5k
2
votes
1
answer
101
views
planar circuit logspace completeness
In https://dl.acm.org/doi/pdf/10.1145/1008354.1008356, a proof is given for PCV is log space complete. I do not understand the construction though, a circuit is given but it is not clear to me what is ...
- 21
3
votes
0
answers
79
views
What is the actual difference between uniformity conditions for NC¹
I want to know what the actual difference between the uniformity conditions for NC¹ is. I know that for $k\geq 2$ $NC^k$ the uniformity conditions are equivalent, but for NC¹ they are not.
I am ...
- 31
12
votes
1
answer
498
views
Trade-off for Barrington's theorem
Barrington's theorem states that any Boolean circuit made up of gates of fan-in $2$ and with depth $d$ can be transformed into an equivalent Branching Program of constant width (in particular, of ...
- 3,722
5
votes
0
answers
62
views
How to prove that all pairwise independent hashing circuits are superconcentrators?
It is mentioned in Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates, A. Gal et al. that "it is also not hard to show that (pairwise-independent) ...
- 161
3
votes
0
answers
80
views
What is $\mathrm{NC}^0$-uniform reduction
I am interesting in strict and ``right'' formulations of results about $\mathrm{NC}^1$-completeness of some languages.
Consider for example Barrington's theorem about $\mathrm{NC}^1$-completeness of ...
- 2,013
3
votes
1
answer
412
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
431
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
62
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 ...
- 280
3
votes
0
answers
79
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$ ...
- 161
0
votes
0
answers
87
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,704
5
votes
1
answer
77
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^...
- 161
10
votes
1
answer
334
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 ...
- 498
5
votes
0
answers
70
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
57
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,214
3
votes
0
answers
112
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
...
- 280
2
votes
1
answer
130
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
203
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
166
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
168
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,214
4
votes
0
answers
61
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 ...
- 37.8k
4
votes
1
answer
121
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
160
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
251
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
216
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
119
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,704
5
votes
1
answer
321
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,704
0
votes
0
answers
45
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
153
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
157
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 ...
- 1,029
0
votes
0
answers
103
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 \...
- 1,029
5
votes
1
answer
147
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
97
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
136
views
2
votes
0
answers
80
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
131
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
68
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
128
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 ...
- 193
5
votes
1
answer
169
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, ...
- 197
5
votes
2
answers
247
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,214
8
votes
1
answer
141
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,214
3
votes
0
answers
106
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,582
3
votes
0
answers
109
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 ...
- 434
10
votes
1
answer
236
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,214