ECCC-Report TR13-054https://eccc.weizmann.ac.il/report/2013/054Comments and Revisions published for TR13-054en-usWed, 14 Aug 2013 21:29:49 +0300
Revision 1
| Average Case Lower Bounds for Monotone Switching Networks |
Yuval Filmus,
Toniann Pitassi,
Robert Robere,
Stephen A. Cook
https://eccc.weizmann.ac.il/report/2013/054#revision1An 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.Wed, 14 Aug 2013 21:29:49 +0300https://eccc.weizmann.ac.il/report/2013/054#revision1
Paper TR13-054
| Average Case Lower Bounds for Monotone Switching Networks |
Yuval Filmus,
Toniann Pitassi,
Robert Robere,
Stephen A. Cook
https://eccc.weizmann.ac.il/report/2013/054An 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.Fri, 05 Apr 2013 02:07:07 +0300https://eccc.weizmann.ac.il/report/2013/054