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

All scheduled dates:


No Upcoming activities yet