Class 11: Universal Circuits

We showed an efficient construction of universal circuits that is actually a generic way to build a circuit for a Python program (and more generally any program in the “random-access memory” model).

That concludes our discussion on circuits. We moved on to Deterministic Finite Automata. The slides are here.

Feb 18, 2025

Class 10: Circuit Size Hierarchy

We showed that for every size s, there exists a function that requires roughly circuit size s to compute. It is a cool proof although it is only existential. The slides are here.

Feb 13, 2025

Class 9: Lower Bound of Circuit Size

We proved a circuit-size lower bound by applying the representation length of circuits. The slides are here.

Feb 11, 2025

Class 8: Circuit Size, Representing Circuits

We went over Problem 1 of PS1. Then, we defined the circuit size classes and discussed the representation of circuits. The slides are here.

PRR4 is released on Gradescope, and you are asked to take a look at the History of Math course by Professor Alex Kontorovich. PS4 is a written assignment, given in PDF and Overleaf template.

Feb 6, 2025

Class 7: Universality and Circuit Size

We finished the universal ways to compute every finite function, and then we moved to circuit size, that is, complexity. The slides are here.

Feb 4, 2025

Class 6: Computation Models, Universality

We discuss what are computation models, how are different models compared, and using boolean circuits to compute any finite function. The slides are here.

PS3 and its template are posted. Also, please work on PRR3 before 10pm on the next Monday.

Jan 30, 2025