# Questions tagged [circuit-complexity]

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

313 questions
95 views

### Is unbounded quantum fanout operation experimentally feasible?

It is known that the "unbounded quantum fanout operation" is very powerful: (See, for example, Hoyer et al. : http://theoryofcomputing.org/articles/v001a005/v001a005.pdf). In particular, it is known ...
148 views

### The evaluation problem for AC$^0_d$ formulas is in FO

Let $d \in \mathbb{N}$ be arbitrary. Let $\mathsf{AC^0_d}$-Eval be the following promise problem: Input: A depth $d$ formula $\varphi(x)$ and a binary string $a$. Output: $\varphi(a)$ I am looking ...
185 views

### Circuit complexity lower bounds and uniformity

I have troubles to understand how lower bounds w.r.t. circuit complexity and upper bounds w.r.t. uniform machine models can be used to show completeness results. For example, the word problem for ...
176 views

### Linear Time Hierarchy and Circuit complexity

By Karp-Lipton Theorem we have: $$PH\subseteq P/poly\Rightarrow PH=\Sigma^p_2$$ So this theorem suggest it is unlikely that $PH\subseteq P/poly$. I want to know is there any similar conditional or ...
640 views

### Monotone arithmetic circuit complexity of elementary symmetric polynomials?

The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables. I am interested in the monotone arithmetic $(+,\times)$ circuit ...
546 views

136 views

### Shrinkage Exponent of Formulas over the Full Binary Basis

Håstad has shown that the shrinkage exponent of boolean formulas over the De Morgan basis is 2. In other words, if one keeps each variable of the formula alive with probability $p$ and restricts it ...
124 views

### Boolean functions computed approximately by k-CNFs and l-DNFs and the depth of trees

A well-known fact is that if a function f is computable by a k-CNF and an l-DNF then it can be computed by a tree of depth at most kl. Long time ago I heard the problem what happens if the CNF and DNF ...
222 views

### Complexity of a problem over acyclic context-free grammars

Let $G$ be an acyclic, context-free grammar over a fixed alphabet $\Sigma=\{a_1,\dots,a_k\}$ with the restriction (without loss of generality) that $|w|=2$ for each rule $A\to w$ in the grammar. ...
253 views

637 views

### How many negations do we need to compute monotone functions?

Razborov proved that the monotone function matching is not in mP. But can we compute matching using a polynomial size circuit with a few negations? Is there a P/poly circuit with $O(n^\epsilon)$ ...
342 views

### smallest circuit size using XOR gates

Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables. The goal is to compute the minimum ...
282 views

### Complexity of multi-linear polynomial computing Boolean function

Let $f:\{0,1\}^{n}\longmapsto\{0,1\}$ be a Boolean function. As usual, let $C(f)$ denote circuit complexity of $f$, i.e, the size of the smallest Boolean circuit computing $f$. As we know that every ...
195 views

84 views

### size bounds for circuits recognizing graph properties (reachability, cyclicity, …)

I am interested in the following. Let the inputs of the circuit correspond to the arcs of a directed graph. The circuit has to output 1 iff there is a directed path from a given node S to a given node ...
468 views

### For what c is division by c in AC0?

Suppose that our input is a binary $x$ and we have to output $\lfloor x/c \rfloor$, where $c$ is some constant integer. This is just a shift if $c$ is a power of two, but what about other numbers? Can ...
815 views

### Why is HAMILTONIAN CYCLE so different from PERMANENT?

A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment $\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such ...
103 views

### What is the strongest known lower bound against SIZE(n)?

What is the best known lower bound against (nonuniform) circuits of size $O(n)$? I understand that we don't know of any explicit functions that need circuits of size more than something like $5n$. But ...
483 views

### Arithmetic circuits with just one threshold gate

When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes some function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a boolean function, we can just add one fanin-1 ...
176 views

### “Largest” class properly contained in PSPACE for a random oracle

Green [1] showed that $PP^{PH}$ is properly contained in $PSPACE$ relative to some oracle. Around the same time, in the famous "voting polynomials" paper [2], it was shown that $PP$ is properly ...
483 views

### Any polynomial which is hard to count but easy to decide?

Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial $f(x_1,\ldots,x_n)$...
210 views

### Why is shifting bits different from shifting qubits?

In classical circuit complexity, shifting bits is considered gratis; all you have to do is reorganizing wires between corresponding gates. By contrast, shifting qubits is typically done by using a ...
208 views

### Does ${\bf AC^0PAD} = {\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem? Recently giving ...
It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp. (We define size as the number of AND and OR ...
What is the minimum tree-width of a circuit over $\{\wedge,\vee,\neg\}$ for computing MAJ? Here MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ outputs 1 iff at least half of its inputs are $1$. I care only ...