Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alexander Kulikov:

TR21-044 | 14th February 2021
Alexander Kulikov, Nikita Slezkin

SAT-based Circuit Local Improvement

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 eye, it may take more than a week to search for a circuit of size thirteen. One of the reasons of ... more >>>

TR19-002 | 31st December 2018
Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii

Complexity of Linear Operators

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 operations are required to compute the linear operator $Ax$?

As we observe in this paper, this problem contains ... more >>>

TR18-192 | 12th November 2018
Alexander Golovnev, Alexander Kulikov

Circuit Depth Reductions

Revisions: 3

The best known circuit lower bounds against unrestricted circuits remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than $5n$. In this work, we suggest a first non-gate-elimination approach for ... more >>>

TR16-158 | 9th October 2016
Alexander Kulikov, Vladimir Podolskii

Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

We study the following computational problem: for which values of $k$, the majority of $n$ bits $\text{MAJ}_n$ can be computed with a depth two formula whose each gate computes a majority function of at most $k$ bits? The corresponding computational model is denoted by $\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>>

TR16-119 | 1st August 2016
Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov

On the Limits of Gate Elimination

Revisions: 1

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There has been a (very slow) progress in proving linear lower bounds with the latest record of ... more >>>

TR16-022 | 22nd February 2016
Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki

Circuit size lower bounds and #SAT upper bounds through a general framework

Revisions: 2

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the ... more >>>

TR15-170 | 26th October 2015
Alexander Golovnev, Alexander Kulikov

Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds

In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An $(n,k,s)$-quadratic disperser is a function on $n$ variables that is not constant on any subset of $\mathbb{F}_2^n$ of size at least $s$ ... more >>>

TR15-166 | 17th October 2015
Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov

A better-than-$3n$ lower bound for the circuit complexity of an explicit function

Revisions: 1

We consider Boolean circuits over the full binary basis. We prove a $(3+\frac{1}{86})n-o(n)$ lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the $3n-o(n)$ bound of Norbert Blum (1984). The proof is based on the gate ... more >>>

TR11-026 | 27th February 2011
Evgeny Demenkov, Alexander Kulikov

An Elementary Proof of $3n-o(n)$ Lower Bound on the Circuit Complexity of Affine Dispersers

A Boolean function $f \colon \mathbb{F}^n_2 \rightarrow \mathbb{F}_2$ is called an affine disperser for sources of dimension $d$, if $f$ is not constant on any affine subspace of $\mathbb{F}^n_2$ of dimension at least $d$. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for $d=o(n)$. The main ... more >>>

TR09-040 | 20th April 2009
Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

On convex complexity measures

Khrapchenko's classical lower bound $n^2$ on the formula size of the
parity function~$f$ can be interpreted as designing a suitable
measure of subrectangles of the combinatorial rectangle
$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we
arrived at the concept of \emph{convex measures}. We prove the
more >>>

ISSN 1433-8092 | Imprint