Questions tagged [circuit-complexity]
Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.
378
questions
2
votes
1
answer
89
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 ...
- 121
0
votes
1
answer
177
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
144
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
150
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,015
1
vote
0
answers
58
views
Are there polynomial time computable polynomials with circuits of size $s$ but no circuits of size $s-1$?
So I was wondering whether you could always have a multivariate polynomial $P$ over $\mathbb{Z}$ that ...
can be represented by arithmetic circuits of size $s$
has polynomial degree and exponentially ...
- 153
4
votes
0
answers
89
views
What are the implications if you could derandomize constant depth polynomial identity testing over $\mathbb{Z}$?
As far as it goes, I read that derandomizing depth-4-$PIT$ over finite fields is already a great achievement since it would mean a subexponential deterministic time algorithm for the general case and ...
- 153
3
votes
0
answers
38
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.3k
4
votes
1
answer
96
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
143
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
213
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 ...
- 153
2
votes
1
answer
170
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
95
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,416
5
votes
1
answer
287
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,416
0
votes
0
answers
40
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
117
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 ...
- 317
5
votes
0
answers
89
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 ...
- 557
0
votes
0
answers
91
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 \...
- 557
5
votes
1
answer
138
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
87
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
134
views
2
votes
0
answers
61
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
96
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
63
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
106
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 ...
- 163
5
votes
1
answer
153
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
165
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,015
8
votes
1
answer
135
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,015
3
votes
0
answers
103
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,562
2
votes
0
answers
94
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
223
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,015
-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
86
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
115
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
204
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.6k
8
votes
1
answer
196
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,223
3
votes
1
answer
155
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
5
votes
0
answers
132
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
87
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,015
7
votes
2
answers
777
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
324
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
96
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
131
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 ...
- 1,015
4
votes
0
answers
189
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,695
1
vote
0
answers
76
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
190
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. ...
- 852
3
votes
0
answers
105
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.6k
14
votes
1
answer
382
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
379
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 ...
- 5,025
2
votes
0
answers
135
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.6k