Spring 2016

Counting Program Seminar Series

Friday, April 22nd, 2016, 2:00 pm3:00 pm

Add to Calendar


Fedor Fomin (University of Bergen)


Calvin Lab Room 116

Lower Bounds on Graph Homomorphism

We discuss conditional (subject to Exponential Time Hypothesis) lower bound on solving Graph Homomorphism exactly. This bound can be used to obtain lower bounds for various graph embedding problems including Subgraph Isomorphism, Graph Minors, etc.
Based on a joint work with Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin and Marek Cygan, Jakub Pachocki, Arkadiusz Socala