Talks
Spring 2021

Strict NP: Expressive Power, Structure, and Complexity
Thursday, Apr. 22, 2021 9:30 am – 10:30 am PDT
Speaker:
Phokion Kolaitis (UC Santa Cruz & IBM Research)
Location:
Zoom
Strict NP is a syntactic fragment of existential second-order logic that can express fundamental NP-complete problems, such as 3-SAT and 3-Colorability. The aim of this talk is to give an overview of some facets of Strict NP, including 0-1 laws and connections between Strict NP on one side and approximation algorithms, constraint satisfaction, and sub-exponential algorithms on the other side.