All reports by Author Russell Impagliazzo:

__
TR19-167
| 21st November 2019
__

Anant Dhayal, Russell Impagliazzo#### UTIME Easy-witness Lemma & Some Consequences

Revisions: 1

__
TR19-024
| 20th February 2019
__

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi#### The Surprising Power of Constant Depth Algebraic Proofs

Revisions: 2

__
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

__
TR19-009
| 16th January 2019
__

Jiawei Gao, Russell Impagliazzo#### The Fine-Grained Complexity of Strengthenings of First-Order Logic

Revisions: 1

__
TR18-095
| 11th May 2018
__

Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin#### Hardness Amplification for Non-Commutative Arithmetic Circuits

__
TR18-092
| 4th May 2018
__

Marco Carmosino, Russell Impagliazzo, Manuel Sabin#### Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

__
TR18-089
| 27th April 2018
__

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal#### Half-duplex communication complexity

Revisions: 5

__
TR17-151
| 8th October 2017
__

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere#### Stabbing Planes

__
TR17-109
| 22nd June 2017
__

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani#### Does Looking Inside a Circuit Help?

__
TR17-023
| 15th February 2017
__

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich#### The Power of Natural Properties as Oracles

__
TR16-053
| 6th April 2016
__

Jiawei Gao, Russell Impagliazzo#### Orthogonal Vectors is hard for first-order properties on sparse graphs

Revisions: 3

__
TR16-037
| 15th March 2016
__

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel#### Pseudorandomness when the odds are against you

__
TR16-008
| 26th January 2016
__

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova#### Algorithms from Natural Lower Bounds

__
TR15-148
| 9th September 2015
__

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider#### Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility

Revisions: 1

__
TR14-024
| 19th February 2014
__

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider#### 0-1 Integer Linear Programming with a Linear Number of Constraints

__
TR14-012
| 27th January 2014
__

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz#### AM with Multiple Merlins

Revisions: 1

__
TR13-163
| 28th November 2013
__

Russell Impagliazzo, Valentine Kabanets#### Fourier Concentration from Shrinkage

Revisions: 2

__
TR12-057
| 7th May 2012
__

Russell Impagliazzo, Raghu Meka, David Zuckerman#### Pseudorandomness from Shrinkage

Revisions: 2

__
TR12-042
| 17th April 2012
__

Chris Beck, Russell Impagliazzo, Shachar Lovett#### Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits

__
TR11-149
| 4th November 2011
__

Paul Beame, Chris Beck, Russell Impagliazzo#### Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space

__
TR10-072
| 19th April 2010
__

Russell Impagliazzo, Valentine Kabanets#### Constructive Proofs of Concentration Bounds

__
TR10-041
| 11th March 2010
__

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer#### Improved Algorithms for Unique Games via Divide and Conquer

__
TR09-090
| 6th October 2009
__

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson#### New Direct-Product Testers and 2-Query PCPs

__
TR09-038
| 14th April 2009
__

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen#### Toward a Model for Backtracking and Dynamic Programming

__
TR08-079
| 31st August 2008
__

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson#### Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized

__
TR06-140
| 8th November 2006
__

Paul Beame, Russell Impagliazzo, Nathan Segerlind#### Formula Caching in DPLL

__
TR06-051
| 8th April 2006
__

Alan Nash, Russell Impagliazzo, Jeff Remmel#### Infinitely-Often Universal Languages and Diagonalization

__
TR05-120
| 14th October 2005
__

Sashka Davis, Russell Impagliazzo#### Models of Greedy Algorithms for Graph Problems

__
TR04-001
| 11th December 2003
__

Lance Fortnow, Russell Impagliazzo, Chris Umans#### On the complexity of succinct zero-sum games

__
TR02-055
| 13th September 2002
__

Valentine Kabanets, Russell Impagliazzo#### Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

Revisions: 1

__
TR01-057
| 15th August 2001
__

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang#### On the (Im)possibility of Obfuscating Programs

__
TR00-009
| 21st February 2000
__

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson#### Extractors and pseudo-random generators with optimal seed length

__
TR00-005
| 17th January 2000
__

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson#### Near-Optimal Separation of Treelike and General Resolution

__
TR97-042
| 22nd September 1997
__

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall#### Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

Anant Dhayal, Russell Impagliazzo

We prove an easy-witness lemma ($\ewl$) for unambiguous non-deterministic verfiers. We show that if $\utime(t)\subset\mathcal{C}$, then for every $L\in\utime(t)$, for every $\utime(t)$ verifier $V$ for $L$, and for every $x\in L$, there is a certificate $y$ satisfing $V(x,y)=1$, that can be encoded as a truth-table of a $\mathcal{C}$ circuit. Our ... more >>>

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

A major open problem in proof complexity is to prove super-polynomial lower bounds for AC^0[p]-Frege proofs. This system is the analog of AC^0[p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years (Razborov, '86 and Smolensky, '87), ... 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 >>>

Jiawei Gao, Russell Impagliazzo

The class of model checking for first-order formulas on sparse graphs has a complete problem with respect to fine-grained reductions, Orthogonal Vectors (OV) [GIKW17]. This paper studies extensions of this class or more lenient parameterizations. We consider classes obtained by allowing function symbols;

first-order on ordered structures; adding various notions ...
more >>>

Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.

This is part of a recent ... more >>>

Marco Carmosino, Russell Impagliazzo, Manuel Sabin

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires $n^{\epsilon k}$ time, for some constant $\epsilon > 1/2$, to count (note that these conjectures are significantly ... more >>>

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

Suppose Alice and Bob are communicating bits to each other in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends bit and the other ... more >>>

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by

branching on an inequality and its "integer negation.'' That is, we can (nondeterministically ...
more >>>

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

The Black-Box Hypothesis, introduced by Barak et al. (JACM, 2012), states that any property of boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an ... more >>>

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP).

We obtain new circuit lower bounds, as well as some hardness results for the relativized version ...
more >>>

Jiawei Gao, Russell Impagliazzo

Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until ... more >>>

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Impagliazzo and Wigderson showed that if $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits, then

every time $T$ constant-error randomized algorithm can be simulated deterministically in time $\poly(T)$. However, such polynomial slowdown is a deal breaker when $T=2^{\alpha \cdot n}$, for a constant $\alpha>0$, as is the case for some randomized algorithms for ...
more >>>

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization ... more >>>

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

We introduce the Nondeterministic Strong Exponential Time Hypothesis

(NSETH) as a natural extension of the Strong Exponential Time

Hypothesis (SETH). We show that both refuting and proving

NSETH would have interesting consequences.

In particular we show that disproving NSETH would ...
more >>>

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time $2^{(1-\text{poly}(1/c))n}$ where $n$ is the

number of variables and $cn$ is the number of constraints. The key ...
more >>>

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close ... more >>>

Russell Impagliazzo, Valentine Kabanets

For Boolean functions computed by de Morgan formulas of subquadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on ``small-degree'' coefficients. For a Boolean function $f:\{0,1\}^n\to\{1,-1\}$ computable by a de Morgan formula of size $s$, we show that

\[

\sum_{A\subseteq [n]\; :\; |A|>s^{1/\Gamma ...
more >>>

Russell Impagliazzo, Raghu Meka, David Zuckerman

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models ... more >>>

Chris Beck, Russell Impagliazzo, Shachar Lovett

There has been considerable interest lately in the complexity of distributions. Recently, Lovett and Viola (CCC 2011) showed that the statistical distance between a uniform distribution over a good code, and any distribution which can be efficiently sampled by a small bounded-depth AC0 circuit, is inverse-polynomially close to one. That ... more >>>

Paul Beame, Chris Beck, Russell Impagliazzo

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have Resolution refutations of space and size each roughly $N^{\log_2 N}$ (and like all formulas have Resolution refutations of space $N$) for ... more >>>

Russell Impagliazzo, Valentine Kabanets

We give a simple combinatorial proof of the Chernoff-Hoeffding concentration bound~\cite{Chernoff, Hof63}, which says that the sum of independent $\{0,1\}$-valued random variables is highly concentrated around the expected value. Unlike the standard proofs,

our proof does not use the method of higher moments, but rather uses a simple ...
more >>>

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

We present two new approximation algorithms for Unique Games. The first generalizes the results of Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi who give polynomial time approximation algorithms for graphs with high conductance. We give a polynomial time algorithm assuming only good local conductance, i.e. high conductance for small subgraphs. ... more >>>

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)).

This basic construct underlies “hardness amplification” in cryptography, circuit complexity and

PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent

result by Dinur and ...
more >>>

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen

We propose a model called priority branching trees (pBT ) for backtracking and dynamic

programming algorithms. Our model generalizes both the priority model of Borodin, Nielson

and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence

spans a wide spectrum of algorithms. After witnessing the ...
more >>>

Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson

The classical Direct-Product Theorem for circuits says

that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard

to compute on average by small circuits, then the corresponding

$k$-wise direct product function

$f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each

$x_i\in\{0,1\}^n$) is significantly harder to compute on average by

slightly smaller ...
more >>>

Paul Beame, Russell Impagliazzo, Nathan Segerlind

We consider extensions of the DPLL approach to satisfiability testing that add a version of memoization, in which formulas that the algorithm has previously shown to be unsatisfiable are remembered for later use. Such formula caching algorithms have been suggested for satisfiability and stochastic satisfiability. We formalize these methods by ... more >>>

Alan Nash, Russell Impagliazzo, Jeff Remmel

Diagonalization is a powerful technique in recursion theory and in

computational complexity \cite{For00}. The limits of this technique are

not clear. On the one hand, many people argue that conflicting

relativizations mean a complexity question cannot be resolved using only

diagonalization. On the other hand, it is not clear that ...
more >>>

Sashka Davis, Russell Impagliazzo

Borodin, Nielsen, and Rackoff gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin extended their work to facility location and set cover problems. We generalize their notion to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an ... more >>>

Lance Fortnow, Russell Impagliazzo, Chris Umans

We study the complexity of solving succinct zero-sum games,

i.e., the

games whose payoff matrix $M$ is given implicitly by a Boolean circuit

$C$ such that $M(i,j)=C(i,j)$. We complement the known $\EXP$-hardness

of computing the \emph{exact} value of a succinct zero-sum game by

several results on \emph{approximating} the value. (1) ...
more >>>

Valentine Kabanets, Russell Impagliazzo

We show that derandomizing Polynomial Identity Testing is,

essentially, equivalent to proving circuit lower bounds for

NEXP. More precisely, we prove that if one can test in polynomial

time (or, even, nondeterministic subexponential time, infinitely

often) whether a given arithmetic circuit over integers computes an

identically zero polynomial, then either ...
more >>>

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)

"compiler" that takes as input a program (or circuit) <b>P</b> and

produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>

yet is "unintelligible" in some sense. Obfuscators, if they exist,

would have a wide variety of cryptographic ...
more >>>

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

We give the first construction of a pseudo-random generator with

optimal seed length that uses (essentially) arbitrary hardness.

It builds on the novel recursive use of the NW-generator in

a previous paper by the same authors, which produced many optimal

generators one of which was pseudo-random. This is achieved ...
more >>>

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

We present the best known separation

between tree-like and general resolution, improving

on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}.

This is done by constructing a natural family of contradictions, of

size $n$, that have $O(n)$-size resolution

refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations.

This result ...
more >>>

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

Razborov~\cite{Razborov96} recently proved that polynomial

calculus proofs of the pigeonhole principle $PHP_n^m$ must have

degree at least $\ceiling{n/2}+1$ over any field. We present a

simplified proof of the same result. The main

idea of our proof is the same as in the original proof

of Razborov: we want to describe ...
more >>>