Complexity seminar

A separator theorem for hypergraphs and a CSP-SAT algorithm

Navid Talebanfard

IM

Friday, 12. April 2019 - 13:30 to 15:00

in IM, rear building, ground floor

I'll show how to remove a small number of edges from a uniform hypergraph of small vertex degree to break it

into small connected components. I'll use it to give a CSP-SAT algorithm for CSPs with small variable frequency.

This is joint work with Vojtěch Rödl.

into small connected components. I'll use it to give a CSP-SAT algorithm for CSPs with small variable frequency.

This is joint work with Vojtěch Rödl.