Questions tagged [circuit-complexity]
Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.
333
questions
3
votes
0answers
93 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 ...
1
vote
0answers
58 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 ...
3
votes
1answer
126 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. ...
3
votes
0answers
88 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 ...
0
votes
0answers
47 views
Can we multiply two numbers more efficiently (using binary circuits) if one of the numbers is fixed? [duplicate]
Let $a_1, a_2 \dots$ be a sequence of natural numbers, where $a_i$ has bit length $i$. Consider a function $f_n : \{0, 1\}^n \to \{0, 1\}^{2n}$ defined as $f_n(x) = a_n \cdot x$ ($\cdot$ is ...
14
votes
1answer
323 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\{...
2
votes
1answer
164 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 ...
2
votes
0answers
120 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$...
4
votes
0answers
99 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 ...
5
votes
1answer
243 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 ...
-1
votes
1answer
167 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-...
15
votes
0answers
230 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)}$ ...
5
votes
0answers
279 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 ...
1
vote
0answers
89 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 ...
2
votes
0answers
98 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 ...
2
votes
1answer
97 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 ...
6
votes
2answers
252 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 ...
3
votes
2answers
244 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 ...
8
votes
1answer
298 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{...
4
votes
0answers
92 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 ...
1
vote
2answers
110 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, ...
9
votes
1answer
266 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 ...
7
votes
1answer
314 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,\...
2
votes
0answers
56 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)$...
11
votes
1answer
270 views
Reversible polynomial circuit iff polynomial reversible circuit?
My question is about efficiently computable bijective functions. Informally I'm interested in:
If a bijection is computable in polynomial time, can we compute it by a polynomial number of bijective ...
8
votes
0answers
98 views
Does ${\bf CFLPAD}={\bf PPAD}$?
What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a (non-)deterministic finite/push-down automaton encodes the problem?
I asked a similar ...
10
votes
1answer
213 views
Linear circuit complexity classes
The class $\textrm{NC}^i$ is the class functions computable by circuits families of bounded fan-in, $n^{O(1)}$ size and $O(\log^i(n))$ depth.
The $\textrm{NC}$-hierarchy is the union of those classes....
5
votes
1answer
212 views
Boolean circuits which correspond to L/poly
Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$.
Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\...
7
votes
0answers
220 views
How many different proofs are there of parity is not in AC0?
The theorem that Parity is not in $\mathsf{AC}^0$ is one of the gemstones of complexity theory. I wonder how many different proofs there are of this result? What constitutes "different" is also a part ...
2
votes
1answer
118 views
Circuit complexity of group actions
Suppose that $G$ is a group with $|G|=n$. Suppose that $G$ is generated by elements $g_{1},\dots,g_{k}$. Let $\iota:G\rightarrow S_{2^{N}}$ be an injective group homomorphism such that $\iota(g_{i}):\{...
3
votes
0answers
86 views
How many arithmetic and max operations does it take to compute Dynnikov's action of the braid groups on $\mathbb{Z}^{2n}$?
A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if
$$(f\times\textrm{Id}_{X})\circ(\textrm{Id}_{X}\times f)\circ(f\times\textrm{Id}_{X})=(\textrm{Id}_{X}\times f)\...
11
votes
1answer
291 views
How small can be a layered boolean circuit for a function with circuit complexity $s$?
Consider a function $f$ computed by a boolean circuit $C$ with $n$ inputs of size $s(n) = \mathsf{poly}(n)$ over the basis $\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$ (with indegree 2 for the $\...
4
votes
0answers
119 views
Asymptotic complexity of mass production
For a function $f:\{0,1\}^n \rightarrow \{0,1\}^m$, let $C(f)$ be the circuit complexity (for concreteness, constants and NOT gates are free, while 2-input AND gates cost 1).
Let $k{\times}f : \{0,1\}...
1
vote
0answers
227 views
Impagliazzo lemma, unclear detail in its proof
In Arora-Barak's book on page 378 in the proof of Impagliazzo's Hard Core lemma why did they choose the number 50 in this line: Set $t = \frac{50n}{\epsilon^2}$ ? How this choice then yields the size ...
9
votes
0answers
104 views
Expected value of the evaluation of Boolean circuits of depth $2n$
I am not an expert on circuits and I wonder whether the following problem was already studied (and possibly solved). Any reference or suitable method to solve this question would be welcome.
Let $C_{...
8
votes
1answer
295 views
Nondeterminism is on average useless for circuits?
Savický and Woods (The Number of Boolean Functions Computed by Formulas of a Given Size) prove the following result.
Theorem[SW98]: For every constant $k>1$, almost all boolean functions with ...
2
votes
0answers
46 views
Arithmetic circuits with restrictions on occurrence of pairs of variables
I am curious if the following model was studied or has some obvious lower bounds:
We want to compute a polynomial $P(x_1,x_2, \dots , x_n)$. Suppose we have a graph G on $n$ nodes that we are going ...
8
votes
0answers
149 views
Number of circuits computing a given function
Let's say we have some function that can be computed by a minimal circuit of size $m$ (using some metric, say, the number of gates). Other than this minimal circuit, there will be many other circuits ...
4
votes
0answers
77 views
Circuits computing functions of inputs smaller than $n$
The usual circuit complexity concerns circuits where circuit $C_n$ computes function $f_n$. I am interested in circuits such that $C_n$ can compute $f_i$ for all $i \leq n$. I am assuming that the ...
2
votes
0answers
214 views
Is there any NC-complete problem with respect to logspace reduction?
The question is on the title.
We all know that $\text{NL}$ and $\text{P}$ have such problems. So I wonder the same thing about $\text{NC}$. More interestingly, is there any $k \ge 2$ and any $\text{...
4
votes
0answers
65 views
Can an efficiently computable non-one way permutation be written as the composition of polynomially many easy to compute involutions?
Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ where if $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ is a bijection where both $f$ and $f^{-1}$ are computable by circuits with at ...
7
votes
0answers
196 views
Can every efficiently computable permutation be written as the composition of two efficiently computable involutions?
It is well-known that every permutation can be written as the composition of two involutions.
Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ such that if $f:\{0,1\}^{n}\...
9
votes
3answers
627 views
What are examples of how non-uniformity can be useful?
I'm curious about ways in which you have seen non-uniformity be useful in computation. One way is randomness, as in $BPP \subseteq P/poly$, and another is look-up tables which are used to show that ...
3
votes
3answers
828 views
Why is the circuit class AC0 unavoidable?
Take AC0.
What is a natural thought process that leads to the definition of AC0?
Does this class arise intrinsically anywhere?
My problem is that in the case of unbounded fan-in, AND and OR gates ...
3
votes
1answer
183 views
Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit
I was reading "Some properties of MOD m circuits computing simple functions" (Amano & Maruoka, 2003) where the authors prove that every Boolean function can be computed by depth $2$ by $(MOD_2-...
4
votes
0answers
156 views
Is $L\subset NC^1$
Arora and Barak's online book claims in exercise 6.11 that $NC^1=L$. While the $NC^1\subset L$ direction is relatively straightforward and explained in many other texts, I couldn't prove or find the $...
6
votes
0answers
139 views
Has what I am calling “helpfulness” here been studied?
We say that a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ is helpful for another Boolean function $g$ if $f(x)$ can be computed with a smaller circuit given $g(x)$ as an extra input bit. I'...
1
vote
2answers
229 views
Efficiently computable by a “simple” algorithm?
I am interested in the relation between "program complexity" and "computational complexity".
In particular, I was wondering
What is known about the minimal length a program must have to solve a ...
4
votes
1answer
126 views
Which $SIZE$-$DEPTH(s, d)$ classes with $log(s(n))^{d(n) - 1} = o(n)$ can we not separate by known methods?
Define $SIZE$-$DEPTH(s, d)$ to be the functions which are computed by circuit families of size $O(s(n))$ and less than depth $d(n)$.
We know from Boppana's 1997 paper on the average sensitivity of ...
2
votes
0answers
58 views
Which invertible linear transformations can be computed reversibly without ancilla/garbage bits just as easily as they can be computed irreversibly?
Suppose that $L:F_{2}^{n}\rightarrow F_{2}^{n}$ is an invertible linear transformation. Then define $w(L)$ to be the gate count of the smallest reversible circuit on $n$ bits without ancilla/garbage ...
