Среда 10.07. Navid Talebanfard (Institute of Mathematics CAS, Prague): "A separator theorem for hypergraphs and a CSP-SAT algorithm"

[PDMI seminars]

Семинар по теории сложности вычислений

Тема: A separator theorem for hypergraphs and a CSP-SAT algorithm
Место: 203
Время: 10.07.2019, 12:00
Докладчик: Navid Talebanfard (Institute of Mathematics CAS, Prague)

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.