Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory - Robert Robere

Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory - Robert Robere

Explore the intricate world of complexity theory in this comprehensive computer science seminar. Delve into proofs, circuits, communication, and lower bounds as presented by Robert Robere, a member of the School of Mathematics at the Institute for Advanced Study. Begin with an introduction and recap before diving into semantic proof systems and resolution proof systems. Examine resolution proofs in detail, followed by discussions on translation and coding properties. Investigate the limits of these concepts and conclude with an exploration of dream proofs. This nearly two-hour lecture offers a deep dive into advanced topics in discrete mathematics and theoretical computer science.