Unlocking the P vs NP Puzzle: Algebraic Complexity Theory Seminar 🧠

For more information on the seminar, see: https://pgadey.ca/seminar/.

Abstract: The question of P vs NP is of great interest to computer scientists, but it is hard to tackle given how unstructured the model of Turing machines is. In this talk, we will introduce a model for computing polynomials called arithmetic circuits, and show how its structured nature allows us to derive lower bounds for complexity, a rather difficult task in the general model. Moreover, we will go over some classical results and common proof techniques (combinatorical arguments and defining complexity measures) and transition into more recent breakthroughs. Finally, we conclude with how close we are to resolving P vs NP when restricted to that model. Familiarity with basic complexity theory is an asset.

#mtbos #algebra #seminar #polynomial #complexity