All Questions
Tagged with circuit-depth reference-request
3 questions
3
votes
0
answers
90
views
What is $\mathrm{NC}^0$-uniform reduction
I am interesting in strict and ``right'' formulations of results about $\mathrm{NC}^1$-completeness of some languages.
Consider for example Barrington's theorem about $\mathrm{NC}^1$-completeness of ...
- 2,023
5
votes
0
answers
105
views
Using epsilon biased sets for circuit lower bounds
I have seen instances of how the technique of epsilon biased sets can be used to construct hard functions against a circuit class - like how in the recent paper of Kane-Williams this was used to ...
- 1,453
10
votes
0
answers
278
views
Depth of bounded fan-in circuits for unbounded fan-in circuits
Assume that we have an unbounded fan-in circuit family of depth $d(n)$ and size $s(n)$.
What is the smallest depth (in terms of $d(n)$ and $n$ and $s(n)$) bounded fan-in circuit family of size $poly(...
- 21.8k