3 citations · 15 across the 20 of their papers we have counts for
3 papers · 1 filter
Tight Bounds for Subgraph Isomorphism and Graph Homomorphism
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov +1
We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph to graph cannot be done in time . Combined…
Condensed Unpredictability
Maciej Skorski, Alexander Golovnev, Krzysztof Pietrzak
We consider the task of deriving a key with high HILL entropy from an unpredictable source. Previous to this work, the only known way to transform unpredictability into a key that…
Lower Bounds for the Graph Homomorphism Problem
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov +1
The graph homomorphism problem (HOM) asks whether the vertices of a given -vertex graph can be mapped to the vertices of a given -vertex graph such that each edge of…