Average-case lower bounds and satisfiability algorithms for small threshold circuits
We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is epsilon_d > 0 such that Parity has correlation at most 1/n^{Omega(1)} with depth-d threshold circu...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl
2016
|