Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > RUIWEN CHEN:
All reports by Author Ruiwen Chen:

TR15-191 | 26th November 2015
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

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 circuits which have at most
n^{1+\epsilon_d} ... more >>>




ISSN 1433-8092 | Imprint