CMSC 39600: Circuit Complexity (Autumn 2024)

Full Course Title: "Topics in Theoretical Computer Science: Circuit Complexity"

Term: Autumn 2024 at the University of Chicago

Instructor: William Hoza (williamhoza@uchicago.edu)

Meetings: Tuesdays and Thursdays | 9:30am - 10:50am | RY 255

Office Hours: Tuesdays | 11am - 12:30pm | JCL 311

Course Description One of the most mathematically appealing ways to model computation is using Boolean circuits: networks of logic gates applied to Boolean variables. One can use counting arguments to show that there exist Boolean functions with exponential "circuit complexity," i.e., all circuits computing these functions have exponentially many gates. However, nobody knows how to prove that specific functions of interest have high circuit complexity. In this course, we will primarily study bounded-depth circuits, which can be considered a model of super-fast parallel algorithms. We will see that such circuits are powerful enough to perform many interesting computations, but we will also prove that they have severe limitations.

We won't follow any particular textbook, but I'll try to post some kind of notes or reference for each class. If you're an undergraduate student and you want to take this course, you'll need to discuss it with me and get approval. If you're a graduate student, there are no firm prerequisites, but it would be helpful to have some familiarity with computational complexity theory and probability theory.

Some possible topics: Advice, uniformity, and the complexity class $\mathsf{P}/\text{poly}$. Adleman's theorem. Shannon's counting argument. Lupanov's circuit construction. The Karp-Lipton theorem. The containments $\mathsf{AC}^0 \subseteq \mathsf{TC}^0 \subseteq \mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{AC}^1$. Approximating $\mathsf{AC}^0$ circuits using low-degree polynomials. Circuit depth reduction. Lower bounds on the size of $\mathsf{AC}^0$ circuits computing the parity and majority functions. The promise majority problem. Correlation bounds. Impagliazzo's hard-core lemma. Yao's XOR lemma. The Nisan-Wigderson pseudorandom generator. Spira's theorem. Barrington's theorem. Gate elimination. Random restrictions and switching lemmas. Fourier analysis and learnability of $\mathsf{AC}^0$. Braverman's theorem. Shrinkage and formula lower bounds. Natural proofs.

Course Timeline (The information below will be updated throughout the quarter.)

Project Study some topic in circuit complexity that we won't have time to discuss in class. Then write and submit an exposition. Your exposition should be in the ballpark of 5-10 pages, but there are no strict page limits. Think of your classmates as your target audience. Please submit your exposition via Gradescope by Wednesday, December 11 at 5pm.

I will need to approve your topic. I encourage you to pick a specific theorem (or two) to focus on. Your exposition should explain what the theorem says and why the theorem is important. Your exposition should also explain the proof of the theorem, but this explanation need not be complete. For example, you might choose to only explain part of the proof, or you might choose to prove a special case of the theorem. I encourage you to try to develop and explain a new way of thinking about the proof. The best case would be if you manage to genuinely prove something new, but this is not required.

Here are some papers you could look at. (I've linked to the most "official" versions available of the papers below, but you might want to also look for other versions, such as ECCC preprints.)

• Guy Blanc, Alexandre Hayderi, Caleb Koch, and Li-Yang Tan. The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem. FOCS 2024.
• Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, and Vladimir Podolskii. Towards Simpler Sorting Networks and Monotone Circuits for Majority. RANDOM 2024.
• Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael Saks, and Navid Talebanfard. Local Enumeration and Majority Lower Bounds. CCC 2024.
• Kuan Cheng and Yichuan Wang. $\mathsf{BPL} \subseteq \mathsf{L}\text{-}\mathsf{AC}^1$. CCC 2024.
• William M. Hoza. A Technique for Hardness Amplification Against $\mathsf{AC}^0$. CCC 2024.
• Mika Göös, Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov. Top-Down Lower Bounds for Depth-Four Circuits. FOCS 2023.
• Prahladh Harsha, Tulasimohan Molli, and Ashutosh Shankar. Criticality of $\mathsf{AC}^0$-Formulae. CCC 2023.
• Srikanth Srinivasan and Utkarsh Tripathi. Optimal Explicit Small-Depth Formulas for the Coin Problem. STOC 2023.
• Lijie Chen. New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method. ITCS 2023.
• Victor Lecomte, Prasanna Ramakrishnan, and Li-Yang Tan. The Composition Complexity of Majority. CCC 2022.
• Xin Lyu. Improved Pseudorandom Generators for $\mathsf{AC}^0$ Circuits. CCC 2022.
• Alexander A. Sherstov. The Approximate Degree of DNF and CNF Formulas. STOC 2022.
• Brynmor Chapman and R. Ryan Williams. Smaller ACC0 Circuits for Symmetric Functions. ITCS 2022.
• Victor Lecomte and Li-Yang Tan. Sharper Bounds on the Fourier Concentration of DNFs. FOCS 2021.
• Zander Kelley. An Improved Derandomization of the Switching Lemma. STOC 2021.
• Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. A Fixed-Depth Size-Hierarchy Theorem for $\mathsf{AC}^0[\oplus]$ via the Coin Problem. SICOMP 2021.
• Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Decision List Compression by Mild Random Restrictions. JACM 2021.
• Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan. Parity Helps to Compute Majority. CCC 2019.
• Ben Rossman and Srikanth Srinivasan. Separation of $\mathsf{AC}^0[\oplus]$ Formulas and Circuits. ToC 2019.
• Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan. Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. ToC 2018.
• Shiteng Chen and Periklis A. Papakonstantinou. Depth Reduction for Composites. SICOMP 2019.
• Avishay Tal. Formula lower bounds via the quantum method. STOC 2017.
• Johan Håstad, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. An Average-Case Depth Hierarchy Theorem for Boolean Circuits. JACM 2017.
• Prahladh Harsha and Srikanth Srinivasan. On Polynomial Approximations to $\mathsf{AC}^0$. RANDOM 2016.

Homework Exercises Exercises will be assigned throughout the quarter. Submit your solutions through Gradescope.

• Exercises 1 & 2, due October 9 at 5pm
• Exercises 3 & 4 [mistake corrected 2024-10-15], due October 16 at 5pm
• Exercises 5 & 6 [slightly edited 2024-10-22], due October 23 at 5pm
• Exercises 7-10, due November 6 at 5pm
• Exercises 11-14 [typo corrected 2024-11-19], due November 20 at 5pm
• Exercises 15 & 16 [typo corrected 2024-11-28], due December 4 at 5pm

Collaboration. You are encouraged to collaborate with your classmates on homework, but you must adhere to the following rules.

• Work on each exercise on your own for at least fifteen minutes before discussing it with your classmates.
• Feel free to explain your ideas to your classmates in person, and feel free to use whiteboards/chalkboards/etc. However, do not share any written/typeset solutions with your classmates for them to study on their own time. This includes partial solutions.
• Write your solutions on your own. While you are writing your solutions, do not consult any notes that you might have taken during discussions with classmates.
• In your write-up, list any classmates who helped you figure out the solution. The fact that student A contributed to student B's solution does not necessarily mean that student B contributed to student A's solution.

Permitted Resources for Full Credit. In addition to discussions with me and discussions with classmates as discussed above, you may also use any slides or notes posted in the "Course Timeline" section of this webpage, and you may also use Wikipedia. If you wish to receive full credit on an exercise, you may not use any other resources.

Outside Resources for Partial Credit. If you wish, you may use outside resources (ChatGPT, Stack Exchange, etc.) to solve an exercise for partial credit. If you decide to go this route, you must make a note of which outside resources you used when you were working on each exercise. You must disclose using a resource even if it was ultimately unhelpful for solving the exercise. Furthermore, if you consult an outside resource while working on an exercise, then you must not discuss that exercise with your classmates.

Grading Policies Your grade will be based on homework exercises (65%), the project (25%), and class participation (10%).

Late work. You are strongly encouraged to complete all the coursework within the allotted time. If you don't master the subject matter of a particular exercise by the time the exercise is due, then you might have trouble understanding the topics we discuss in the following classes. Furthermore, if you submit your work late, then it might not be possible to give you timely feedback. That being said, I understand that occasionally missing a deadline is inevitable. Late work will ordinarily receive partial credit based on the following principles.

• If you submit your solution to a homework exercise $x$ days late, where $0 < x < 9$, then your score will be multiplied by $\sqrt{1 - (x/9)^2}$. The value $x$ can be fractional; some rounding will occur in the calculation. Work turned in nine or more days late will ordinarily not receive any credit. Saturdays, Sundays, and university holidays are all excluded from the lateness calculation.
• Eventually, I will post official solutions. If you look at the official solutions, then from that point onward, you are not permitted to submit your own solutions for those exercises. Submitting solutions after looking at the official solutions would be an academic honesty violation.
• The principles described above might be ambiguous or problematic in some edge cases. Ultimately, I will decide how much credit to grant for late work.

Extensions. Please get in touch with me if you are having trouble keeping up with the course schedule for any reason. I may be willing to give you an extension, or I may be willing to give you partial credit for late work in excess of what the principles above stipulate. To highlight one example, I am happy to grant an extension for a religious holiday if you give me sufficiently early notice that you will be observing that holiday.

Regrade requests. If you think something was graded incorrectly, please submit a regrade request through Gradescope.

Academic Honesty Catch-All Policy Even if you have no intention of being dishonest, you might nevertheless find yourself in an "ethically problematic" situation at some point. For example, maybe you and a classmate work together to solve a homework exercise, and then afterward you remember that you were supposed to work on the problem on your own for at least fifteen minutes before collaborating. Or maybe you accidentally stumble upon the solution to a homework problem while reading the textbook for a different course.

In such circumstances, you should simply send me an email explaining what happened.

I encourage you to follow this simple protocol in every course you take. It is a surefire way to avoid getting in trouble for academic dishonesty. Depending on the circumstances, I might have to take some points off your score, but don't let this deter you. A clean conscience is worth more than any grade.

Inclusion and Accessibility This course, like every course you take, ought to be an enjoyable and enriching experience. You have a right to be treated with respect and a responsibility to treat others with respect. I want all students to be able to fully participate in this course. Let me know if you need an accommodation for any reason, so we can explore possible solutions together. If applicable, please follow the protocols established by UChicago Student Disability Services.

To highlight a few facets of these topics:

• You are encouraged to ask questions in class, and you should make your classmates feel comfortable asking questions in class. There is no shame in not knowing something or not understanding something. Questions make the course better for everyone.
• I am happy to work with any students who are pregnant/parenting to figure out the best way to make the course work for you.
• Computer scientists and mathematicians can come from many diverse backgrounds, and nobody should experience prejudice or discrimination in this course.