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 a constant ε d > 0 such that the Parity function on n bits has correlation at most n −εd with dept...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
University of Chicago, Department of Computer Science
2018
|