Arrow Research search

Author name cluster

Emanuele Viola

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
1 author row

Possible papers

21

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.

Details

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

Details

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

Details

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.

Details

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

Details

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.

Details

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.

Details

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.

Details

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

Details

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.

Details

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.

Details

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

Details