__
Revision #1 to TR23-034 | 25th March 2023 10:59
__
#### On teaching the approximation method for circuit lower bounds

**Abstract:**
This 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.

**Changes to previous version:**
Added a clarification at the end of the introduction, which clearly states that

the main ideas presented in this text are well known and have been presented in many texts,

and that my main contribution is in providing a more detailed and more motivated exposition of these ideas.

__
TR23-034 | 24th March 2023 19:04
__

#### On teaching the approximation method for circuit lower bounds

**Abstract:**
This 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.