Faculty Recruiting Support CICS

Unique Games And Inapproximability: A Logic Perspective

31 Mar
Wednesday, 03/31/2021 12:15pm to 1:15pm
Virtual via Zoom
Theory Seminar

Abstract: Descriptive complexity provides an alternative perspective on computation, in which a problem is characterized not by the computational resources required to solve it, but by the logical constructs required to define it. This viewpoint has enabled proofs of unconditional lower bounds for important restricted classes of algorithms, holding without the assumption that P != NP. In this talk, I will explain this approach, and use it to establish new lower bounds on approximation algorithms that are definable over Fixed-Point Logic with Counting (FPC). I will discuss a logical analogue of Raghavendra's characterization of the optimal approximability of constraint satisfaction problems, in which the Unique Games problem plays a central role. I will also present a novel construction establishing a nontrivial inapproximability gap for Unique Games over FPC. No prior knowledge of logic, approximability, or Unique Games should be necessary to understand this talk.

Bio: Jamie Tucker-Foltz is a PhD student at Harvard, with research interests in complexity theory and algorithmic game theory. He earned an undergraduate degree at Amherst College, where he was a regular attendant of the UMass Theory Seminar, and a Master's at the University of Cambridge, UK.

Join the Zoom meeting

The CICS Theory Seminar is online, free and open to the public. If you are interested in giving a talk, please email Professor Immerman or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.