# Questions tagged [circuit-complexity]

Circuit complexity is the study of resource-bounded circuits and the functions computed by such circuits.

325 questions
Filter by
Sorted by
Tagged with
80 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 ...
200 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 ...
146 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-...
211 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)}$ ...
262 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 ...
83 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 ...
84 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 ...
87 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 ...
236 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 ...
212 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 ...
265 views

54 views

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 $... 1answer 247 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 ... 0answers 96 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 ... 1answer 188 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.... 1answer 191 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}/\...
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 ...