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

Speaker: 
Navid Talebanfard (Institute of Mathematics CAS, Prague)
Date: 
Wednesday, July 10, 2019 - 12:00
Place: 
203
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.