A. Kulikov

activity

20102022

most citedLimits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

4 citations · 7 across the 10 of their papers we have counts for

collaborators

Showing cs.CCShow all

5 papers · 1 filter

cs.CC2022

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 $x_{1} \oplus x_{2} \oplus \dots \oplus x_{n}$ is $2^{n - 1}$ . One can obtain a more compact CNF encoding by u…

cs.CC2019

Complexity of Linear Operators

Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov +1

Let $A \in {0, 1}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$ -dimensional vector of formal variables over a semigroup $(S, \circ)$ . How many semigroup…

cs.CC2018

Circuit Depth Reductions

Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams

The best known size lower bounds against unrestricted circuits have remained around $3 n$ for several decades. Moreover, the only known technique for proving lower bounds in this mo…

cs.CC2016★ 1 cited

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 $k$ , the majority of $n$ bits $MAJ_{n}$ can be computed with a depth two formula whose each gate computes a m…

cs.CC2010★ 4 cited

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…