4 citations · 5 across the 4 of their papers we have counts for
6 papers
Cirbo: A New Tool for Boolean Circuit Analysis and Synthesis
Daniil Averkov, Tatiana Belova, Gregory Emdin +8
We present an open-source tool for manipulating Boolean circuits. It implements efficient algorithms, both existing and novel, for a rich variety of frequently used circuit tasks s…
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin +3
The field of fine-grained complexity aims at proving conditional lower bounds on the time complexity of computational problems. One of the most popular assumptions, Strong Exponent…
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…
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…
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…