# Questions tagged [circuit-complexity]

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

398 questions
Filter by
Sorted by
Tagged with
101 views

• 13.1k
156 views

### Formula complexity of $n = 0 \pmod m$

Given two $k$-bits numbers $n$ and $m$, how large is a Boolean formula that computes whether $n = 0\pmod m$?
• 1,704
1 vote
153 views

### Use of transitive closure in proof of NC hierarchy collapse

Im looking at the proof of $NC^{i} = NC^{i+1} \implies NC = NC^i,\,i\geq 1$ in page 10 of the following article: https://www.cs.uoregon.edu/Reports/TR-1986-001.pdf I understand the general idea ...
• 11
79 views

### Is a problem, that is $L$-complete under non-uniform $AC^0$ reductions, necessarily outside of (non-uniform or uniform) $NC^1$?

I don't have much intuition about non-uniformity so the question may be quite naive.
• 43
141 views

• 197
247 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,214
141 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,214
106 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,582
109 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 ...
• 434
### 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 ...