Questions tagged [circuit-complexity]
Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.
362
questions
3
votes
0
answers
82
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
127
views
2
votes
0
answers
59
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
82
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
59
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 ...
- 21
3
votes
1
answer
90
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 ...
- 153
0
votes
0
answers
61
views
Does every Boolean function of degree $n$ decompose as the (XOR) product of two functions of complementary degrees?
Say $f: \{-1,+1\}^n \rightarrow \{-1, +1\}$ is a Boolean function of (Fourier) degree $n$. Is it true that there exist non-constant Boolean functions $g$, $h$ of degrees $a$ and $b$ respectively such ...
- 226
5
votes
1
answer
145
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
3
votes
1
answer
146
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 ...
- 802
8
votes
1
answer
130
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 ...
- 802
0
votes
0
answers
26
views
Can we pick a basis for synchronous circuits which coarsens towards the target partition at every layer?
Given a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ and a Boolean basis for circuit gates $B$ (for instance $B = \{AND, OR\}$), we can construct the set of size optimal synchronous (Harper ...
- 1,552
3
votes
0
answers
98
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,552
2
votes
0
answers
89
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 ...
- 414
10
votes
1
answer
208
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 ...
- 802
-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
82
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,013
3
votes
0
answers
113
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 ...
- 322
4
votes
0
answers
197
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.5k
8
votes
1
answer
189
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 ...
- 7,485
3
votes
1
answer
151
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 ...
- 83
4
votes
0
answers
118
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 ...
- 213
0
votes
0
answers
56
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 ...
- 793
1
vote
1
answer
79
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, ...
- 802
7
votes
2
answers
728
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
321
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,052
1
vote
1
answer
93
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
9
votes
1
answer
126
views
Proof of $DLOGTIME-CC^0 = MOD[<,bit]$
Let $CC^0[m]$ be the class of constant-depth, polynomial-sized circuits consisting entirely of $MOD_m$ gates, which put out $1$ iff the sum of their inputs $\equiv 0~(\textrm{mod}~m)$. In the same way ...
- 802
4
votes
0
answers
178
views
On solving Planar Circuit SAT
This enquiry is three-sided.
Side 1 - State of the art
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$?
Which is the best known algorithm for $\text{PLANAR-CIRCUIT-SAT}$ assuming ...
- 6,625
1
vote
0
answers
72
views
Multiplicative-depth 1 composition of arithmetic circuits
I am trying to find information about the following problem. Let $C_1$ and $C_2$ be any two poly-size arithmetic circuits on input vectors x₁ and x₂ correspondingly. Assume that a third arithmetic ...
- 401
4
votes
1
answer
179
views
What is FO(REGULAR)? (The descriptive complexity equivalent of NC1)
According to Immerman's Descriptive Complexity diagram, there is a logic called $\mathsf{FO(REGULAR)}$ which captures $\mathsf{NC}^1$. However, I can't find the reference where this logic is defined. ...
- 842
3
votes
0
answers
104
views
Improving boolean circuits w.r.t. a probability distribution
This is a reference request. Consider the following problem on boolean circuits [ 1 ]:
Given: Boolean circuit $B$ and probability distribution $\mathbb{P}$ on inputs to $B$.
Task: Find one or more ...
- 10.4k
14
votes
1
answer
376
views
Universal Boolean Formulas
Fix $n\in\mathbb{N}$. Consider a rooted binary tree $T$ in which every non-leaf node contains either AND-gate or OR-gate. Let me say that $T$ is an universal formula if for every $f\colon\{0,1\}^n\to\{...
5
votes
2
answers
351
views
Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?
Background
It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$.
Although some natural problems are known to exist, many of them ...
- 4,910
2
votes
0
answers
131
views
Matrix multiplication when one matrix is fixed
Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry
One is allowed to pre-process this matrix as appropriate.
Given another positive integer entried $B$...
- 12.5k
4
votes
0
answers
109
views
Is the Complexity Zoo Inclusion Diagram exclusively about classes of decision problems?
The Complexity Zoo includes the class QNC$^0$, which does not seem to be a class of decision problems. When I chase the references of the link provided, they say
“To extend this definition from ...
- 4,400
5
votes
1
answer
257
views
What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?
What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?
What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates ...
- 529
-1
votes
1
answer
196
views
Evidence integer multiplication is in linear time?
After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-...
- 12.5k
15
votes
0
answers
262
views
Does small circuits for a NP-complete problem contradict ETH?
The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ ...
- 151
5
votes
0
answers
304
views
Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?
Depth-First-Search (DFS) has a quasilinear (i.e.,$\widetilde{O}(m+n)$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a $\widetilde{O}(m+n)$ time algorithm in ...
- 51
1
vote
0
answers
103
views
Switching lemma for polynomials over $\mathbb{F}_2$
Suppose $f$ is in $\mathbb{F}_2[x_1,...,x_n]$ with total degree $d$.
Q. Is there any kind of switching lemma or restriction lemma in which by applying the lemma on $f$ we can reduce the total ...
- 322
2
votes
0
answers
118
views
What is the communication complexity of approximating addition?
In my circuit complexity research, I came across the need to find the communication complexity of approximating addition. Specifically, the class of problems I am interested in is parametrized by four ...
- 633
2
votes
1
answer
128
views
Upper bounds on the circut depth
Suppose $f:\{0,1\}^n \to \{0,1\}$ is a function such that it can be computed by a circuit of size $n^c$ for some constant $c>0$.
Q. Is there any nontrivial upper bound on the depth of a circuit ...
- 322
7
votes
2
answers
420
views
Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power
It seems to be a folklore that we can "handle" $\textrm{ACC}[q]$ circuits not only for prime $q$ but prime power $q$.
For example, authors of this paper say that
... any constant
depth circuit ...
- 395
3
votes
2
answers
343
views
Is the unbounded fan-in model realistic?
Does the unbounded fan-in circuit model apply in "practical" settings? In other words, are there real-world realisable computers with unbounded fan-in gates?
As I understand, standard silicon ASICs ...
- 319
8
votes
1
answer
371
views
Is there any quantum analog of the VP vs. VNP problem?
From Wikipedia:
$\mathsf{VP}$: The class VP is the algebraic analog of P; it is the class of polynomials $f$ of polynomial degree that have polynomial size circuits over a fixed field $K$.
$\mathsf{...
- 307
5
votes
0
answers
134
views
Is there a universal gate set for classical probabilistic computing?
We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum ...
- 151
1
vote
2
answers
128
views
When is a problem specified on a TM contained in non-uniform classes such as P/poly? [closed]
In this paper by Gottesman and Irani: https://arxiv.org/abs/0905.2419 , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, ...
- 383
9
votes
1
answer
328
views
Depth reduction for Boolean circuits
This result by Tavenas, Koiran and others show that any polynomial computed by a circuit of size $s$ is computed by a depth-4 homogenous circuit of size $s^{\sqrt{d}}$.
Are there any similar results ...
- 91
7
votes
1
answer
347
views
Can reciprocal inputs speed up monotone computations?
A $(+,\times,1/x_i)$ circuit is a standard monotone arithmetic $(+,\times)$ circuit with the only difference that now besides the input variables $x_1,\ldots,x_n$, also their reciprocals $1/x_1,\...
- 6,635
2
votes
0
answers
69
views
How to improve this pseudorandom generator?
Let $f$ be a Boolean function and $\varepsilon > 0$.
There exists a pseudorandom generator $G_f: \{0,1 \}^{n^{\varepsilon}} \to \{0,1 \}^n$ with the following property.
Let $T$ be a set and $p(n)$...
- 1,695