ECCC-Report TR23-034https://eccc.weizmann.ac.il/report/2023/034Comments and Revisions published for TR23-034en-usSat, 25 Mar 2023 10:59:28 +0300
Revision 1
| On teaching the approximation method for circuit lower bounds |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2023/034#revision1This text provides a basic presentation of the the approximation method of Razborov (Matematicheskie Zametki, 1987) and its application by Smolensky (19th STOC, 1987) for proving lower bounds on the size of ${\cal AC}^0[p]$-circuits that compute sums mod~$q$ (for primes $q\neq p$).
The textbook presentations of the latter result concentrate on proving the special case of $q=2$, and do not provide details on the proof of the general case.
Furthermore, the presentations I have read tend to be too terse to my taste.
The current text provides a detailed exposition of both the special case and the general case.
Nevertheless, I agree with the common practice of covering only the case of $q=2$ in class, and suggest leaving the general case (i.e, $q>2$) for advanced reading.
Sat, 25 Mar 2023 10:59:28 +0300https://eccc.weizmann.ac.il/report/2023/034#revision1
Paper TR23-034
| On teaching the approximation method for circuit lower bounds |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2023/034This text provides a basic presentation of the the approximation method of Razborov (Matematicheskie Zametki, 1987) and its application by Smolensky (19th STOC, 1987) for proving lower bounds on the size of ${\cal AC}^0[p]$-circuits that compute sums mod~$q$ (for primes $q\neq p$).
The textbook presentations of the latter result concentrate on proving the special case of $q=2$, and do not provide details on the proof of the general case.
Furthermore, the presentations I have read tend to be too terse to my taste.
The current text provides a detailed exposition of both the special case and the general case.
Nevertheless, I agree with the common practice of covering only the case of $q=2$ in class, and suggest leaving the general case (i.e, $q>2$) for advanced reading.
Fri, 24 Mar 2023 19:05:02 +0300https://eccc.weizmann.ac.il/report/2023/034