Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ALEXANDER GOLOVNEV:
All reports by Author Alexander Golovnev:

TR24-054 | 13th March 2024
Karthik Gajulapalli, Alexander Golovnev, Samuel King

On the Power of Adaptivity for Function Inversion

We study the problem of function inversion with preprocessing where, given a function $f : [N] \to [N]$ and a point $y$ in its image, the goal is to find an $x$ such that $f(x) = y$ using at most $T$ oracle queries to $f$ and $S$ bits of preprocessed ... more >>>


TR23-193 | 3rd December 2023
Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz

On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in ... more >>>


TR23-021 | 9th March 2023
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi

Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms

Revisions: 2

Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit $C\colon\{0,1\}^n\to\{0,1\}^m$, $m>n$, the task is to find a $y\in\{0,1\}^m$ outside the range of $C$. For an integer $k\geq 2$, $NC^0_k$-AVOID is a special case of AVOID where each output bit of $C$ depends on at most $k$ ... more >>>


TR22-177 | 7th December 2022
Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian

Quantum Worst-Case to Average-Case Reductions for All Linear Problems

We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands ... more >>>


TR22-145 | 4th November 2022
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

Revisiting Time-Space Tradeoffs for Function Inversion

Revisions: 1

We study the black-box function inversion problem, which is the problem of finding $x \in [N]$ such that $f(x) = y$, given as input some challenge point $y$ in the image of a function $f : [N] \to [N]$, using $T$ oracle queries to $f$ and preprocessed advice $\sigma \in ... more >>>


TR22-068 | 5th May 2022
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy

Sketching Approximability of (Weak) Monarchy Predicates

Revisions: 1

We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first ... more >>>


TR22-020 | 18th February 2022
Vahid Reza Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar

Worst-Case to Average-Case Reductions via Additive Combinatorics

We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time $T$ that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time $\widetilde{O}(T)$ that are correct on ... more >>>


TR21-141 | 28th September 2021
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization

Revisions: 1

We study a natural and quite general model of branch-and-bound algorithms. In this model, an algorithm attempts to minimize (or maximize) a function $f : D \to \mathbb{R}_{\geq 0}$ by making oracle queries to a heuristic $h_f$ satisfying
\[
\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot ... more >>>


TR21-086 | 22nd June 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

Linear Space Streaming Lower Bounds for Approximating CSPs

Revisions: 1

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints. We also identify ... more >>>


TR21-063 | 3rd May 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Approximability of all finite CSPs in the dynamic streaming setting

Revisions: 3

A constraint satisfaction problem (CSP), Max-CSP$({\cal F})$, is specified by a finite set of constraints ${\cal F} \subseteq \{[q]^k \to \{0,1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from ${\cal F}$ to subsequences of the $n$ ... more >>>


TR21-011 | 13th February 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

Classification of the streaming approximability of Boolean CSPs

Revisions: 4 , Comments: 1

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


TR20-057 | 20th April 2020
Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein

Polynomial Data Structure Lower Bounds in the Group Model

Revisions: 1

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


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

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


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


TR18-188 | 7th November 2018
Zeev Dvir, Alexander Golovnev, Omri Weinstein

Static Data Structure Lower Bounds Imply Rigidity

Revisions: 2

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


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-110 | 19th July 2016
Alexander Golovnev, Oded Regev, Omri Weinstein

The Minrank of Random Graphs

Revisions: 1

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


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

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




ISSN 1433-8092 | Imprint