Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-054 | 14th August 2013 21:29

Average Case Lower Bounds for Monotone Switching Networks

RSS-Feed




Revision #1
Authors: Stephen A. Cook, Yuval Filmus, Toniann Pitassi, Robert Robere
Accepted on: 14th August 2013 21:29
Downloads: 766
Keywords: 


Abstract:

An approximate computation of a Boolean function by a circuit or switching network is a computation which computes the function correctly on the majority of the inputs (rather than on all inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many subareas of complexity theory, such as cryptography and derandomization. Lower bounds for approximate computation are also known as correlation bounds or average case hardness. In this paper, we obtain the first average case monotone depth lower bounds for a function in monotone $P$. We tolerate errors that are asymptotically the best possible for monotone circuits. Specifically, we prove average case exponential lower bounds on the size of monotone switching networks for the GEN function. As a corollary, we establish that for every $i$, there are functions computed with no error in monotone $NC^{i+1}$, but that cannot be computed without large error by monotone circuits in $NC^i$. Our proof extends and simplifies the Fourier analytic technique due to Potechin, and further developed by Chan and Potechin. As a corollary of our main lower bound, we prove that the communication complexity approach for monotone depth lower bounds does not naturally generalize to the average case setting.



Changes to previous version:

Fixed a calculation in the main theorems. Reworded statement of results.


Paper:

TR13-054 | 4th April 2013 16:10

Average Case Lower Bounds for Monotone Switching Networks





TR13-054
Authors: Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook
Publication: 5th April 2013 02:07
Downloads: 1426
Keywords: 


Abstract:

An approximate computation of a Boolean function by a circuit or switching network is a computation which computes the function correctly on the majority of the inputs (rather than on all inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many subareas of complexity theory, such as cryptography and derandomization. Lower bounds for approximate computation are also known as correlation bounds or average case hardness. In this paper, we obtain the first average case monotone depth lower bounds for a function in monotone $P$. We tolerate errors that are asymptotically the best possible for monotone circuits. Specifically, we prove average case exponential lower bounds on the size of monotone switching networks for the GEN function. As a corollary, we establish that for every $i$, there are functions computed with no error in monotone $NC^{i+1}$, but that cannot be computed without large error by monotone circuits in $NC^i$. Our proof extends and simplifies the Fourier analytic technique due to Potechin, and further developed by Chan and Potechin. As a corollary of our main lower bound, we prove that the communication complexity approach for monotone depth lower bounds does not naturally generalize to the average case setting.



ISSN 1433-8092 | Imprint