Past Events

Faculty Candidate Talk

Proof Complexity and Applications


Download as iCal file

Tuesday, February 23, 2021, 10:30am


Speaker: Marc Vinyals


Marc Vinyals is a visiting fellow at the Technion. He works on
computational complexity, and proof complexity in particular, hosted
by Yuval Filmus. His research interests include other areas of
computational complexity such as circuit complexity, communication
complexity, query complexity, and pebble games, as well as the theory
of satisfiability solving. Previously he was a graduate student at the
KTH Royal Institute of Technology, supervised by Jakob Nordström, and
a visiting fellow at the Tata Institute of Fundamental Research,
hosted by Arkadev Chattopadhyay.

Location : Via Zoom

Event Type: Faculty Candidate Talk

Abstract: Even though the origins of proof complexity are intimately tied to theP vs NP question, nowadays a significant part of the appeal ofresearch in this area is that new results readily apply to largeclasses of algorithms. In this talk we will discuss how recentdevelopments in proof complexity are impacting the design ofsatisfiability solvers, how fine-grained mathematical models can helpus smooth over discrepancies between theory and practice, and howquestions arising from implementation details end up as meaningfulmathematical problems with connections to other topics incomputational complexity.

Contact  Host: Dr. Martin Farach-Colton

Join the zoom:;