All reports by Author Alexander Golovnev:

__
TR21-011
| 13th February 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy#### Classification of the streaming approximability of Boolean CSPs

Revisions: 2
,
Comments: 1

__
TR20-057
| 20th April 2020
__

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein#### Polynomial Data Structure Lower Bounds in the Group Model

__
TR19-018
| 18th February 2019
__

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal#### AC0[p] Lower Bounds against MCSP via the Coin Problem

__
TR18-192
| 12th November 2018
__

Alexander Golovnev, Alexander Kulikov#### Circuit Depth Reductions

Revisions: 3

__
TR18-188
| 7th November 2018
__

Zeev Dvir, Alexander Golovnev, Omri Weinstein#### Static Data Structure Lower Bounds Imply Rigidity

Revisions: 2

__
TR16-119
| 1st August 2016
__

Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov#### On the Limits of Gate Elimination

Revisions: 1

__
TR16-110
| 19th July 2016
__

Alexander Golovnev, Oded Regev, Omri Weinstein#### The Minrank of Random Graphs

Revisions: 1

__
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

__
TR15-170
| 26th October 2015
__

Alexander Golovnev, Alexander Kulikov#### Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds

__
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

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal ... more >>>

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein

Proving super-logarithmic data structure lower bounds in the static \emph{group model} has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\R^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic-complexity), against linear storage arithmetic ... more >>>

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, ... more >>>

Alexander Golovnev, Alexander Kulikov

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 >>>

Zeev Dvir, Alexander Golovnev, Omri Weinstein

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of $t \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>>

Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov

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 >>>

Alexander Golovnev, Oded Regev, Omri Weinstein

The minrank of a graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching ones to zeros (i.e., deleting edges) and setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of ... more >>>

Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki

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 >>>

Alexander Golovnev, Alexander Kulikov

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 >>>

Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov

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 >>>