The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
1answer
74 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 $\...
5
votes
1answer
86 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 ...
8
votes
0answers
135 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
170 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{...
8
votes
0answers
137 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 ...
12
votes
2answers
417 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
votes
1answer
453 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 (...
10
votes
3answers
634 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 ...