Emanuele Viola

FOCS Conference 2024 Conference Paper

Boosting Uniformity in Quasirandom Groups: Fast and Simple

• Harm Derksen
• Chin Ho Lee
• Emanuele Viola

We study the communication complexity of multiplying $k\times t$ elements from the group $H$ = SL $(2, q)$ in the number-on-forehead model with $k$ parties. We prove a lower bound of $(t\log H)/c^{k}$. This is an exponential improvement over previous work, and matches the state-of-the-art in the area. Relatedly, we show that the convolution of $k^{c}$ independent copies of a 3-uniform distribution over $H^{m}$ is close to a $k$ - uniform distribution. This is again an exponential improvement over previous work which needed $c^{k}$ copies. The proofs are remarkably simple; the results extend to other quasirandom groups. We also show that for any group $LI$, any distribution over $H^{m}$ whose weight-k Fourier coefficients are small is close to a k-uniform distribution. This generalizes previous work in the abelian setting, and the proof is simpler.

SODA Conference 2023 Conference Paper

Efficient resilient functions

• Peter Ivanov
• Raghu Meka
• Emanuele Viola

FOCS Conference 2022 Conference Paper

Fooling polynomials using invariant theory *

• Harm Derksen
• Emanuele Viola

We revisit the problem of constructing explicit pseudorandom generators that fool with error ϵ degree-d polynomials in n variables over the field F q, in the case of large q. Previous constructions either have seed length $\geq 2^{d}\log q$, and thus are only non-trivial when $d\lt \log n$, or else rely on a seminal reduction by Bogdanov (STOC 2005). This reduction yields seed length not less than $d^{4}\log n+\log q$ and requires fields of size $q\geq d^{6}/\epsilon^{2}$; and explicit generators meeting such bounds are known. Departing from Bogdanov’s reduction, we develop an algebraic analogue of the Bogdanov-Viola paradigm (FOCS 2007, SICOMP 2010) of summing generators for degree-one polynomials. Whereas previous analyses of the paradigm are restricted to degree $d\lt \log n$, we give a new analysis which handles large degrees. A main new idea is to show that the construction preserves indecomposability of polynomials. Apparently for the first time in the area, the proof uses invariant theory. Our approach in particular yields several new pseudorandom generators. In particular, for large enough fields we obtain seed length $O(d\log n+\log q)$ which is optimal up to constant factors. We also construct generators for fields of size as small as $O(d^{4})$. Further reducing the field size requires a significant change in techniques: Most or all generators for large-degree polynomials rely on Weil bounds; but such bounds are only applicable when $q\gt d^{4}$

SODA Conference 2020 Conference Paper

How to Store a Random Walk

• Emanuele Viola
• Omri Weinstein
• Huacheng Yu

Motivated by storage applications, we study the following data structure problem: an encoder wishes to store a collection of jointly-distributed files: = ( X 1, X 2, …, X n ) ∼ µ which are correlated ( H µ ( ) ≤ Σ i H µ ( X i )), using as little (expected) memory as possible, such that each individual file X i can be recovered quickly with few (ideally constant) memory accesses. In the case of independent random files, a dramatic result by Pǎtraşcu (FOCS’08) and subsequently by Dodis, Pǎtraşcu and Thorup (STOC’10) shows that it is possible to store using just a constant number of extra bits beyond the information-theoretic minimum space, while at the same time decoding each X i in constant time. However, in the (realistic) case where the files are correlated, much weaker results are known, requiring at least Ω( n /poly lg n ) extra bits for constant decoding time, even for “simple” joint distributions µ. We focus on the natural case of compressing Markov chains, i. e. , storing a length- n random walk on any (possibly directed) graph G. Denoting by κ ( G, n ) the number of length- n walks on G, we show that there is a succinct data structure storing a random walk using lg 2 κ ( G, n ) + O (lg n ) bits of space, such that any vertex along the walk can be decoded in O (1) time on a word-RAM. If the graph is strongly connected (e. g. , undirected), the space can be improved to only lg 2 k ( G, n ) + 5 extra bits. For the harder task of matching the point-wise optimal space of the walk, i. e. , the empirical entropy, we present a data structure with O (1) extra bits at the price of O (lg n ) decoding time, and show that any improvement on this would lead to an improved solution on the long-standing Dictionary problem. All of our data structures support the online version of the problem with constant update and query time.

FOCS Conference 2018 Conference Paper

Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs

• Aryeh Grinberg
• Ronen Shaltiel
• Emanuele Viola

We study how well can q-query decision trees distinguish between the following two distributions: (i) R = (R 1, .. ., R N ) that are i. i. d. indicator random variables, (ii) X=(R|R ϵ A) where A is an event s. t. Pr[R ϵ A] ≥ 2 -a. We prove two lemmas: · Forbidden-set lemma: There exists B ⊆ [N] of size poly(a, q, 1/η) such that q-query trees that do not query variables in B cannot distinguish X from R with advantage η. · Fixed-set lemma: There exists B ⊆ [N] of size poly(a, q, 1/η) and v ϵ0, 1 B such that q-query trees do not distinguish (X|X B =v) from (R|R B =v) with advantage η. The first can be seen as an extension of past work by Edmonds, Impagliazzo, Rudich and Sgall (Computational Complexity 2001), Raz (SICOMP 1998), and Shaltiel and Viola (SICOMP 2010) to adaptive decision trees. It is independent of recent work by Meir and Wigderson (ECCC 2017) bounding the number of i ϵ [N] for which there exists a q-query tree that predicts X i from the other bits. We use the second, fixed-set lemma to prove lower bounds on black-box proofs for hardness amplification that amplify hardness from δ to 1/2-ϵ. Specifically: · Reductions must make q=Ω(log(1/δ)/ϵ 2 ) queries, implying a "size loss factor" of q. We also prove the lower bound q=Ω(log(1/δ)/ϵ) for "error-less" hardness amplification proofs, and for direct-product lemmas. These bounds are tight. · Reductions can be used to compute Majority on Ω(1/ϵ) bits, implying that black box proofs cannot amplify hardness of functions that are hard against constant depth circuits (unless they are allowed to use Majority gates). Both items extend to pseudorandom-generator constructions. These results prove 15-year-old conjectures by Viola, and improve on three incomparable previous works (Shaltiel and Viola, SICOMP 2010; Gutfreund and Rothblum, RANDOM 2008; Artemenko and Shaltiel, Computational Complexity 2014).

I&C Journal 2018 Journal Article

Local reduction

• Hamidreza Jahanjou
• Eric Miles
• Emanuele Viola

We reduce non-deterministic time T ≥ 2 n to a 3SAT instance ϕ of quasilinear size | ϕ | = T ⋅ log O ( 1 ) ⁡ T such that there is an explicit NC 0 circuit C that encodes ϕ in the following way: on input a ( log ⁡ | ϕ | ) -bit index i, C outputs the ith clause of ϕ. The previous best result was C in NC1. Even in the simpler setting of polynomial size ( | ϕ | = poly ( T ) ), the previous best result was C in AC0. More generally, for any time T ≥ n and parameter r ≤ n we obtain | ϕ | = max ⁡ ( T, 2 n / r ) ⋅ ( n log ⁡ T ) O ( 1 ), and each output bit of C is a decision tree of depth O ( log ⁡ r ). As an application, we tighten Williams' connection between satisfiability algorithms and circuit lower bounds (STOC 2010; SIAM J. Comput. 2013).

FOCS Conference 2016 Conference Paper

The Multiparty Communication Complexity of Interleaved Group Products

• Timothy Gowers
• Emanuele Viola

Party A i of k parties A 1, .. ., A k receives on its forehead a t-tuple (a i1, .. ., a it ) of elements from the group G = SL(2, q). The parties are promised that the interleaved product a 11. .. a k1 a 12. .. a k2. .. a 1t. .. a kt is equal either to the identity e or to some other fixed element g ∈ G. Their goal is to determine which of e and g the interleaved product is equal to, using the least amount of communication. We show that for all fixed k and all sufficiently large t the communication is Ω(t log |G|), which is tight. As an application, we establish the security of the leakage-resilient circuits studied by Miles and Viola (STOC 2013) in the "only computation leaks" model. Our main technical contribution is of independent interest. We show that if X is a probability distribution on G m such that any two coordinates are uniform in G 2, then a pointwise product of s independent copies of X is nearly uniform in G m, where s depends on m only.

STOC Conference 2015 Conference Paper

The communication complexity of interleaved group products

• Timothy Gowers
• Emanuele Viola

Alice receives a tuple (a 1 ,...,a t ) of t elements from the group G = SL(2,q). Bob similarly receives a tuple of t elements (b 1 ,...,b t ). They are promised that the interleaved product prod i ≤ t a i b i equals to either g and h, for two fixed elements g,h ∈ G. Their task is to decide which is the case.

SODA Conference 2013 Conference Paper

On the Complexity of Information Spreading in Dynamic Networks

• Chinmoy Dutta
• Gopal Pandurangan
• Rajmohan Rajaraman
• Zhifeng Sun
• Emanuele Viola

We study how to spread k tokens of information to every node on an n -node dynamic network, the edges of which are changing at each round. This basic gossip problem can be completed in O ( n + k ) rounds in any static network, and determining its complexity in dynamic networks is central to understanding the algorithmic limits and capabilities of various dynamic network models. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying and forwarding them. We first consider the strongly adaptive adversary model where in each round, each node first chooses a token to broadcast to all its neighbors (without knowing who they are), and then an adversary chooses an arbitrary connected communication network for that round with the knowledge of the tokens chosen by each node. We show that Ω( nk /log n + n ) rounds are needed for any randomized (centralized or distributed) token-forwarding algorithm to disseminate the k tokens, thus resolving an open problem raised in [KLO10]. The bound applies to a wide class of initial token distributions, including those in which each token is held by exactly one node and well-mixed ones in which each node has each token independently with a constant probability. Our result for the strongly adaptive adversary model motivates us to study the weakly adaptive adversary model where in each round, the adversary is required to lay down the network first, and then each node sends a possibly distinct token to each of its neighbors. We propose a simple randomized distributed algorithm where in each round, along every edge ( u, v ), a token sampled uniformly at random from the symmetric difference of the sets of tokens held by node u and node v is exchanged. We prove that starting from any well-mixed distribution of tokens where each node has each token independently with a constant probability, this algorithm solves the k -gossip problem in O (( n + k ) log n log k ) rounds with high probability over the initial token distribution and the randomness of the protocol. We then show how the above uniform sampling problem can be solved using Õ (log n ) bits of communication, making the overall algorithm communication-efficient. We next present a centralized algorithm that solves the gossip problem for every initial distribution in O (( n + k ) log 2 n ) rounds in the offline setting where the entire sequence of communication networks is known to the algorithm in advance. Finally, we present an -round centralized offline algorithm in which each node can only broadcast a single token to all of its neighbors in each round.

STOC Conference 2013 Conference Paper

Shielding circuits with groups

• Eric Miles
• Emanuele Viola

We show how to efficiently compile any given circuit C into a leakage-resistant circuit C' such that any function on the wires of C' that leaks information during a computation C'(x) yields advantage in computing the product of |C'| Ω(1) elements of the alternating group A u . In combination with new compression bounds for A u products, also obtained here, C' withstands leakage from virtually any class of functions against which average-case lower bounds are known. This includes communication protocols, and AC 0 circuits augmented with few arbitrary symmetric gates. If NC 1 ' TC 0 then then the construction resists TC 0 leakage as well. We also conjecture that our construction resists NC 1 leakage. In addition, we extend the construction to the multi-query setting by relying on a simple secure hardware component. We build on Barrington's theorem [JCSS '89] and on the previous leakage-resistant constructions by Ishai et al. [Crypto '03] and Faust et al. [Eurocrypt '10]. Our construction exploits properties of A u beyond what is sufficient for Barrington's theorem.

SODA Conference 2013 Conference Paper

The communication complexity of addition

• Emanuele Viola

Suppose each of k ≤ n o (1) players holds an n -bit number x i in its hand. The players wish to determine if σ i ≤ k x i = s. We give a public-coin protocol with error 1% and communication O ( k lg k ). The communication bound is independent of n, and for k ≥ 3 improves on the O ( k lg n ) bound by Nisan (Bolyai Soc. Math. Studies; 1993). Our protocol also applies to addition modulo m. In this case we give a matching (public-coin) Ω( k lg k ) lower bound for various m. We also obtain some lower bounds over the integers, including Ω( k lg lg k ) for protocols that are one-way, like ours. We give a protocol to determine if σ x i > s with error 1% and communication O ( k lg k )lgn. For k ≥ 3 this improves on Nisan's O ( k lg 2 n ) bound. A similar improvement holds for computing degree-( k − 1) polynomial-threshold functions in the number-on-forehead model. We give a (public-coin, 2-player, tight) Ω(lg n ) lower bound to determine if x 1 > x 2. This improves on the bound by Smirnov (1988). As an application, we show that polynomial-size AC 0 circuits augmented with O (1) threshold (or symmetric) gates cannot compute cryptographic pseudorandom functions, extending the result about AC 0 by Linial, Mansour, and Nisan (J. ACM; 1993).

STOC Conference 2012 Conference Paper

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

• Anna Gál
• Kristoffer Arnsfelt Hansen
• Michal Koucký 0001
• Pavel Pudlák
• Emanuele Viola

We bound the minimum number w of wires needed to compute any (asymptotically good) error-correcting code C:{0,1} Ω(n) -> {0,1} n with minimum distance Ω(n), using unbounded fan-in circuits of depth d with arbitrary gates. Our main results are: (1) If d=2 then w = Θ(n ({log n/ log log n}) 2 ). (2) If d=3 then w = Θ(n lg lg n). (3) If d=2k or d=2k+1 for some integer k ≥ 2 then w = Θ(n λ k (n)), where λ 1 (n)=⌈ log n⌉, λ i+1 (n)= λ i *(n), and the * operation gives how many times one has to iterate the function λ i to reach a value at most 1 from the argument n. (4) If d=log* n then w=O(n).

FOCS Conference 2011 Conference Paper

Extractors for Circuit Sources

• Emanuele Viola

We obtain the first deterministic extractors for sources generated (or sampled) by small circuits of bounded depth. Our main results are: (1) We extract k(k/nd) O(1) bits with exponentially small error from n-bit sources of min-entropy k that are generated by functions f: {0, 1} → {0, 1} n where each output bit depends on ≤ d input bits. In particular, we extract from NC sources, corresponding to d = O(1). (2) We extract k(k/n 1+γ ) O(1) bits with super-polynomially small error from ri-bit sources of min-entropy k that are generated by poly(n)-size AC O circuits, for any γ >; 0. As our starting point, we revisit the connection by Trevisan and Vadhan (FOCS 2000) between circuit lower bounds and extractors for sources generated by circuits. We note that such extractors (with very weak parameters) are equivalent to lower bounds for generating distributions (FOCS 2010; with Lovett, CCC 2011). Building on those bounds, we prove that the sources in (1) and (2) are (close to) a convex combination of high-entropy "bit-block" sources. Introduced here, such sources are a special case of affine ones. As extractors for (1) and (2) one can use the extractor for low-weight affine sources by Rao (CCC 2009). Along the way, we exhibit an explicit boolean function b: {0, 1} n → {0, 1} such that poly(n)-size AC O circuits cannot generate the distribution (Y, b(Y)), solving a problem about the complexity of distributions. Independently, De and Watson (RANDOM 2011) obtain a result similar to (1) in the special case d = o(lg n).

FOCS Conference 2011 Conference Paper

Randomness Buys Depth for Approximate Counting

• Emanuele Viola

We show that the promise problem of distinguishing n-bit strings of hamming weights 1/2 + / - Ω(1/lg d-1 n) can be solved by explicit, randomized (unbounded-fan-in) poly(n)- size depth-d circuits with error ≤ 1/3, but cannot be solved by deterministic poly(n)-size depth-(d +1) circuits, for every d ≥ 2; and the depth of both is tight. Previous results bounded the depth to within at least an additive 2. Our sharper bounds match Ajtai's simulation of randomized depth-d circuits by deterministic depth-(d+2) circuits (Ann. Pure Appl. Logic; ' 83), and provide an example where randomization (provably) buys resources. Techniques: To rule out deterministic circuits we combine the switching lemma with an earlier depth-3 lower bound by the author (Comp. Complexity 2009). To exhibit randomized circuits we combine recent analyses by Amano (ICALP '09) and Brody and Verbin (FOCS '10) with derandomization. To make these circuits explicit which we find important for the main message of this paper we construct a new pseudorandom generator for certain combinatorial rectangle tests. Based on expander walks, the generator for example fools tests A 1 × A 2 ×. .. × A lg n for A i ⊆ [n], |A i | = n/2 with error 1/n and seed length O(lg n), improving on the seed length Ω(lg n lg lg n) of previous constructions.

SODA Conference 2010 Conference Paper

Cell-Probe Lower Bounds for Succinct Partial Sums

• Mihai Patrascu
• Emanuele Viola

The partial sums problem in succinct data structures asks to preprocess an array A [1 ‥ n ] of bits into a data structure using as close to n bits as possible, and answer queries of the form. The problem has been intensely studied, and features as a subroutine in a number of succinct data structures. We show that, if we answer R ank ( k ) queries by probing t cells of w bits, then the space of the data structure must be at least n + n / w O ( t ) bits. This redundancy/probe trade-off is essentially optimal: Patrascu [FOCS'08] showed how to achieve n + n /( w/t ) Ω( t ) bits. We also extend our lower bound to the closely related Select queries, and to the case of sparse arrays.

FOCS Conference 2010 Conference Paper

The Complexity of Distributions

• Emanuele Viola

Complexity theory typically studies the complexity of computing a function h(x): {0, 1} m → {0, 1} n of a given input x. We advocate the study of the complexity of generating the distribution h(x) for uniform x, given random bits. Our main results are: (1) Any function f: {0, 1} ℓ → {0, 1} n such that (i) each output bit f i depends on o(log n) input bits, and (ii) ℓ ≤ log 2 ( αn n ) + n 0. 99, has output distribution f(U) at statistical distance ≥ 1 - 1/n 0. 49 from the uniform distribution over n-bit strings of hamming weight αn. We also prove lower bounds for generating (X, b(X)) for boolean b, and in the case in which each bit f i is a small-depth decision tree. These lower bounds seem to be the first of their kind; the proofs use anti-concentration results for the sum of random variables. (2) Lower bounds for generating distributions imply succinct data structures lower bounds. As a corollary of (1), we obtain the first lower bound for the membership problem of representing a set S ⊆ [n] of size αn, in the case where 1/α is a power of 2: If queries "i ∈ S? " are answered by non-adaptively probing o(log n) bits, then the representation uses ≥ log 2 ( αn 3) + Ω(log n) bits. (3) Upper bounds complementing the bounds in (1) for various settings of parameters. (4) Uniform randomized AC 0 circuits of poly(n) size and depth d = O(1) with error ϵ can be simulated by uniform randomized AC 0 circuits of poly(n) size and depth d + 1 with error ϵ + o(1) using ≤ (log n) O(log log n) random bits. Previous derandomizations [Ajtai and Wigderson '85; Nisan '91] increase the depth by a constant factor, or else have poor seed length.

STOC Conference 2009 Conference Paper

Bit-probe lower bounds for succinct data structures

• Emanuele Viola

We prove lower bounds on the redundancy necessary to represent a set S of objects using a number of bits close to the information-theoretic minimum log 2 |S|, while answering various queries by probing few bits. Our main results are: To represent n ternary values t ∈ {0,1,2} n in terms of u bits b ∈ {0,1} u while accessing a single value t i ∈ {0,1,2} by probing q bits of b, one needs u ≥ (log 2 3)n + n/2 O(q) . This matches an exciting representation by Patrascu (FOCS 2008), later refined with Thorup, where u ≤ (log_2 3)n + n/2 Ω(q) . We also note that results on logarithmic forms imply the lower bound u ≥ (log 2 3)n + n/log O(1) n if we access t i by probing one cell of log n bits. To represent sets of size n/3 from a universe of n elements in terms of u bits b ∈ {0,1} u while answering membership queries by probing q bits of b, one needs u ≥ log 2 n/(n/3) + n/2 O(q) - log n. Both results above hold even if the probe locations are determined adaptively. Ours are the first lower bounds for these fundamental problems; we obtain them drawing on ideas used in lower bounds for locally decodable codes.

FOCS Conference 2009 Conference Paper

Bounded Independence Fools Halfspaces

• Ilias Diakonikolas
• Parikshit Gopalan
• Ragesh Jaiswal
• Rocco A. Servedio
• Emanuele Viola

We show that any distribution on {-1, +1} n that is k-wise independent fools any halfspace (a. k. a. threshold) h: {-1, +1} n ¿ {-1, +1}, i. e. , any function of the form h(x) = sign(¿ i=1 n w i X i - ¿) where the w 1, .. ., w n, ¿ are arbitrary real numbers, with error ¿ for k = O(¿ -2 log 2 (1/¿)). Our result is tight up to log(1/¿) factors. Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators G: {-1, +1} s ¿ {-1, +1} n that fool halfspaces. Specifically, we fool halfspaces with error e and seed length s = k · log n = O(log n · ¿ -2 log 2 (1/¿)). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Comput. Complexity 2007).

STOC Conference 2008 Conference Paper

Hardness amplification proofs require majority

• Ronen Shaltiel
• Emanuele Viola

Hardness amplification is the fundamental task of converting a δ-hard function f : (0, 1) n -> (0, 1) into a (1/2-ε)-hard function Amp(f), where f is γ-hard if small circuits fail to compute f on at least a γ fraction of the inputs. Typically, ε,δ are small (and δ=2 -k captures the case where f is worst-case hard). Achieving ε = 1/n Ω(1) is a prerequisite for cryptography and most pseudorandom-generator constructions.

FOCS Conference 2007 Conference Paper

One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications

• Emanuele Viola
• Avi Wigderson

In this paper we study the one-way multi-party communication model, in which even party speaks exactly once in its turn. For every fixed k, we prove a tight lower hound of Omega (n 1/(k-1) ) on the probabilistic communication complexity of pointer jumping in a k-layered tree, where the pointers of the i-lh layer reside on the forehead of the i-th party to speak. The lower bound remains nontrivial even for k = (log n) 1/2-Omega(1) parties. Previous to our work a lower bound was known only for k = 3, and in very restricted models for k > 3. Our results have the following consequences to other models and problems, extending previous work in several directions. The one-way model is strong enough to capture general (non one-wav) multi-party protocols of bounded rounds. Thus we generalize to this multi-party model results on two directions studied in the classical 2-party model. The first is a mund hierarchy: We give an exponential separation between the power of r and 2r rounds in general probabilistic k-party protocols, for any fixed k and r. The second is the relative power of determinism and nondeterminism: We prove an exponential separation between nondeterministic and deterministic communication complexity for general k-party protocols with r rounds, for anvfixed k, r. The pointer jumping function is weak enough to be a special case of the well-studied disjointness function. Thus we obtain a lower bound of Omega (n 1/(k-1) ) on the probabilistic complexity of k-set disjointness in the oneway model, which was known only for k = 3 parties. Our result also extends a similar lower bound for the weaker simultaneous model, in which parties simultaneously send one message to a referee. Finally, we infer an exponential separation between the power of different orders in which parties send messages in the one-way model, for every fixed k. Previous to our work such a separation was only known for k = 3. Our lower bound technique, which handles functions of high discrepancy, may be of independent interest. It provides a "party-elimination " induction, based on a restricted form of a direct-product result, specific to the pointer jumping function.

FOCS Conference 2007 Conference Paper

Pseudorandom Bits for Polynomials

• Andrej Bogdanov
• Emanuele Viola

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators G: F s rarrF n that fool polynomials over a prime field F: (1) a generator that fools degree-2 (i. e. , quadratic) polynomials to within error 1/n, with seed length s = O(log n); (2) a generator that fools degree-3 (i. e. , cubic) polynomials to within error epsiv, with seed length s = O(Iog |F| n) + f(epsiv, F) where f depends only on epsiv and F (not on n), (3) assuming the "Gowers inverse conjecture, " for every d a generator that fools degree-d polynomials to within error epsiv, with seed length, s = O(dldrIog |F| n) + f(d, epsiv, F) where f depends only on d, epsiv, and F (not on n). We stress that the results in (1) and (2) are unconditional, i. e. do not rely on any unproven assumption. Moreover, the results in (3) rely on a special case of the conjecture which may be easier to prove. Our generator for degree-d polynomials is the component-wise sum of d generators for degree-l polynomials (on independent seeds). Prior to our work, generators with logarithmic seed length were only known for degree-1 (i. e. , linear) polynomials (Naor and Naor; SIAM J. Comput. , 1993). In fact, over small fields such as F 2 = {0, 1}, our results constitute the first progress on these problems since the long-standing generator by Luby, Velickovic and Wigderson (ISTCS1993), whose seed length is much bigger: s = exp (Omega(radiclogn)), even for the case of degree-2 polynomials over F 2.

STOC Conference 2004 Conference Paper

Using nondeterminism to amplify hardness

• Alexander Healy
• Salil P. Vadhan
• Emanuele Viola

We revisit the problem of hardness amplification in NP, as recently studied by O'Donnell (STOC '02). We prove that if NP has a balanced function f such that any circuit of size s ( n ) fails to compute f on a 1/poly( n ) fraction of inputs, then NP has a function f ′ such that any circuit of size s ′( n )= s (√ n ) Ω(1) fails to compute f ′ on a 1/2 - 1/ s ′( n ) fraction of inputs. In particular, 1. If s ( n )= n ω(1) , we amplify to hardness 1/2-1/n ω(1) . 2. If s ( n )=2 n ω(1) , we amplify to hardness 1/2-1/2 n Ω(1) . 3. If s ( n )=2 ( n ) , we amplify to hardness 1/2-1/2 Ω(sqrt n ) .These improve the results of O'Donnell, which only amplified to 1/2-1/√ n . O'Donnell also proved that no construction of a certain general form could amplify beyond 1/2-1/ n . We bypass this barrier by using both derandomization and nondeterminism in the construction of f ′.We also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that f is balanced are necessary for "black-box" hardness amplification procedures (such as ours).