The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
64 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 ...
7
votes
0answers
110 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}$ plus ...
9
votes
0answers
156 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 ...
7
votes
0answers
108 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 ...
11
votes
2answers
383 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 ...
20
votes
1answer
415 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 ...
9
votes
3answers
561 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 ...