8 papers
CNF Encodings of Parity
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin +1
The minimum number of clauses in a CNF representation of the parity function is . One can obtain a more compact CNF encoding by u…
Complexity of Linear Operators
Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov +1
Let be a matrix with zeroes and ones and be an -dimensional vector of formal variables over a semigroup . How many semigroup…
Circuit Depth Reductions
Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams
The best known size lower bounds against unrestricted circuits have remained around for several decades. Moreover, the only known technique for proving lower bounds in this mo…
Collapsing Superstring Conjecture
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov +2
In the Shortest Common Superstring (SCS) problem, one is given a collection of strings, and needs to find a shortest string containing each of them as a substring. SCS admits $2\fr…
Tight Lower Bounds on Graph Embedding Problems
Marek Cygan, Fedor V. Fomin, Alexander Golovnev +4
We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph to graph cannot be done in time . We al…
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…