Questions tagged [bounded-depth]
The bounded-depth tag has no usage guidance.
11 questions
5
votes
1
answer
173
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, ...
- 307
1
vote
1
answer
110
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,234
5
votes
0
answers
172
views
Height of AVL tree with random elements
I know that for an AVL tree of N nodes, the depth of the tree is bounded by
$$ \log_2(N + 1) -1 \leq height \leq c \log_2(N + 2) + b$$
where $c,b$ are taken from the golden ratio linked to the worst ...
- 171
2
votes
1
answer
118
views
Low-depth arithmetic complexity of the product of $k$ matrices
Is anything known about the size of $\Sigma\Pi\Sigma$ (or other constant depth) circuits for the product of $k$ matrices?
Trivial upper bounds (up to small factors) are:
if $k=2$, then there are $\...
- 901
5
votes
1
answer
132
views
Commitment schemes with verification in NC0
Is there any secure cryptographic commitment scheme, where the verification routine can be implemented in $NC^0$? If so, what is the minimum possible depth of the circuit for verification?
Applebaum ...
- 12.4k
9
votes
0
answers
173
views
Is nonuniform $\mathsf{TC^0}$ equal to the composition closure of $\mathsf{AC^0}$ and Majority?
D.A.M. Barrington, N. Immerman and H. Straubing show in their 1990 paper
"On Uniformity Within $\mathsf{NC^1}$" that
the uniform $\mathsf{TC^0}$ is equal to $\mathsf{FOM}$
($\mathsf{FO}$ ...
- 21.8k
9
votes
0
answers
206
views
Evaluation of bounded-depth circuits
Is the evaluation problem for $\mathsf{AC}^0_d$ circuits in $\mathsf{AC}^0_{d+1}$? What is the least depth $k(d)$ such that the evaluation of an $\mathsf{AC}^0_d$ circuits can be computed in $\mathsf{...
- 21.8k
11
votes
1
answer
242
views
$\mathsf{TC^0}$-completeness and reductions
AFAIU, we don't know any problem
which is complete for $\mathsf{TC^0}$ w.r.t.
many-one $\mathsf{AC^0}$ reductions ($\leq^\mathsf{AC^0}_m$).
On the other hand,
proving that they don't exist would ...
- 21.8k
13
votes
2
answers
591
views
Does the $\mathsf{TC^0}$ hierarchy collapse?
Do we know that the $\mathsf{TC^0}$ hierarchy does not collapse ($\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}$ for all $d$)?
The Zoo entry for $\mathsf{TC^0}$ only mentions the separation between ...
- 21.8k
22
votes
1
answer
612
views
Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?
Is there any plausible complexity/crypto hypothesis that rules out the possibility that polynomial size circuits have subexponential-size (i.e. $2^{O(n^\epsilon)}$ with $\epsilon<1$) bounded-depth (...
- 21.8k
11
votes
3
answers
1k
views
Practical consequences of $Parity \notin AC^0$
Background
Circuit complexity $AC^0$ is defined as the set of circuit families (i.e. sequences of circuits, one for each input size) of bounded depth and polynomial size built using unbounded fan-in ...
- 21.8k