RIRussell Impagliazzo

Russell Impagliazzo

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Russell Impagliazzo has a total of 44 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • The Power of Natural Properties as Oracles

    by Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich


  • Open Access

    Comparing computational entropies below majority (or: When is the dense model theorem false?)

    by Russell Impagliazzo, Sam McGuire

    Computational pseudorandomness studies the extent to which a random variable $\bf{Z}$ looks like the uniform distribution according to a class of tests $\cal{F}$. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a \emph{high entropy} distribution. There are different formal definitions of computational entropy with different advantages for different applications. Because of this, it is of interest to understand when these definitions are equivalent. We consider three notions of computational entropy which are known to be equivalent when the test class $\cal{F}$ is closed under taking majorities. This equivalence constitutes (essentially) the so-called \emph{dense model theorem} of Green and Tao (and later made explicit by Tao-Zeigler, Reingold et al., and Gowers). The dense model theorem plays a key role in Green and Tao's proof that the primes contain arbitrarily long arithmetic progressions and has since been connected to a surprisingly wide range of topics in mathematics and computer science, including cryptography, computational complexity, combinatorics and machine learning. We show that, in different situations where $\cal{F}$ is \emph{not} closed under majority, this equivalence fails. This in turn provides examples where the dense model theorem is \emph{false}.

  • Simultaneous Secrecy and Reliability Amplification for a General Channel Model

    by Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Bruce M. Kapron, Valerie King, Stefano Tessaro

  • Fourier Concentration from Shrinkage

    by Russell Impagliazzo, Valentine Kabanets


  • Open Access

    0-1 Integer Linear Programming with a Linear Number of Constraints

    by 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 idea for the algorithm is a reduction to the Vector Domination problem and a new algorithm for that subproblem.

  • Open Access

    AM with Multiple Merlins

    by 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 analogies between it and the quantum complexity class QMA(k), but the AM(k) model is also natural in its own right. We illustrate the power of multiple Merlins by giving an AM(2) protocol for 3SAT, in which the Merlins' challenges and responses consist of only n^{1/2+o(1)} bits each. Our protocol has the consequence that, assuming the Exponential Time Hypothesis (ETH), any algorithm for approximating a dense CSP with a polynomial-size alphabet must take n^{(log n)^{1-o(1)}} time. Algorithms nearly matching this lower bound are known, but their running times had never been previously explained. Brandao and Harrow have also recently used our 3SAT protocol to show quasipolynomial hardness for approximating the values of certain entangled games. In the other direction, we give a simple quasipolynomial-time approximation algorithm for free games, and use it to prove that, assuming the ETH, our 3SAT protocol is essentially optimal. More generally, we show that multiple Merlins never provide more than a polynomial advantage over one: that is, AM(k)=AM for all k=poly(n). The key to this result is a subsampling theorem for free games, which follows from powerful results by Alon et al. and Barak et al. on subsampling dense CSPs, and which says that the value of any free game can be closely approximated by the value of a logarithmic-sized random subgame.

  • Open Access

    A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits

    by Russell Impagliazzo, Ramamohan Paturi, Stefan Schneider

    We give a nontrivial algorithm for the satisfiability problem for cn-wire threshold circuits of depth two which is better than exhaustive search by a factor 2^{sn} where s= 1/c^{O(c^2)}. We believe that this is the first nontrivial satisfiability algorithm for cn-wire threshold circuits of depth two. The independently interesting problem of the feasibility of sparse 0-1 integer linear programs is a special case. To our knowledge, our algorithm is the first to achieve constant savings even for the special case of Integer Linear Programming. The key idea is to reduce the satisfiability problem to the Vector Domination Problem, the problem of checking whether there are two vectors in a given collection of vectors such that one dominates the other component-wise. We also provide a satisfiability algorithm with constant savings for depth two circuits with symmetric gates where the total weighted fan-in is at most cn. One of our motivations is proving strong lower bounds for TC^0 circuits, exploiting the connection (established by Williams) between satisfiability algorithms and lower bounds. Our second motivation is to explore the connection between the expressive power of the circuits and the complexity of the corresponding circuit satisfiability problem.

  • Open Access

    An Entropic Proof of Chang's Inequality

    by Russell Impagliazzo, Cristopher Moore, Alexander Russell

    Chang's lemma is a useful tool in additive combinatorics and the analysis of Boolean functions. Here we give an elementary proof using entropy. The constant we obtain is tight, and we give a slight improvement in the case where the variables are highly biased.

  • Toward a Model for Backtracking and Dynamic Programming

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


  • Random Cnf’s are Hard for the Polynomial Calculus

    by Eli Ben-Sasson, Russell Impagliazzo