4 citations · 7 across the 10 of their papers we have counts for
14 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…
SAT-based Circuit Local Improvement
Alexander S. Kulikov, Danila Pechenev, Nikita Slezkin
Finding exact circuit size is a notorious optimization problem in practice. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in blink of an…
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…
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
Alexander S. Kulikov, Vladimir V. Podolskii
We study the following computational problem: for which values of , the majority of bits can be computed with a depth two formula whose each gate computes a m…
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…
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…
Parameterized Complexity of Superstring Problems
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach +3
In the Shortest Superstring problem we are given a set of strings and integer and the question is to decide whether there is a superstring of le…
Parameterized Complexity of Secluded Connectivity Problems
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov +1
The Secluded Path problem models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a…
Families with infants: speeding up algorithms for NP-hard problems using FFT
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
Assume that a group of people is going to an excursion and our task is to seat them into buses with several constraints each saying that a pair of people does not want to see each…
Families with infants: a general approach to solve hard partition problems
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin
We introduce a general approach for solving partition problems where the goal is to represent a given set as a union (either disjoint or not) of subsets satisfying certain properti…
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
Prahladh Harsha, Moses Charikar, Matthew Andrews +14
These are the lecture notes for the DIMACS Tutorial "Limits of Approximation Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building, Rutgers University on 20-2…