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 the P vs NP question, nowadays a significant part of the appeal of research in this area is that new results readily apply to large classes of algorithms. In this talk we will discuss how recent developments in proof complexity are impacting the design of satisfiability solvers, how fine-grained mathematical models can help us smooth over discrepancies between theory and practice, and how questions arising from implementation details end up as meaningful mathematical problems with connections to other topics in computational complexity.

Contact  Host: Dr. Martin Farach-Colton

Join the zoom:;