Talks
Spring 2021

Strict NP: Expressive Power, Structure, and Complexity

Thursday, Apr. 22, 2021 9:30 am10:30 am

Add to Calendar

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.