Laboratory of Mathematical Logic at PDMI

Cреда, 10 июля, 203. Начало в 12:00.

Докладчик: Navid Talebanfard (Institute of Mathematics CAS, Prague).

Тема: A separator theorem for hypergraphs and a CSP-SAT algorithm.

Abstract

I will show how to remove a small number of edges from a hypergraph of small degree to break it into small connected components. I will then use it to solve CSP-SAT instances in which no variable appears in too many constraints and to give refutations of Tseitin formulas in small degree graphs with savings independent of the degree.

Joint work with Michal Koucký and Vojtěch Rödl.