Pseudorandom Bits for Polynomials
By Frank McSherry, Kunal Talwar. 2007
1,931 citations recorded by the source corpus.
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 : FsrarrFn 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 F2 = {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 F2.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Jonathan Ullman
- Abhradeep Thakurta
- Vitaly Feldman
- Peter Kairouz
- Philip S. Yu
- Yu-Xiang Wang
- Daniel Kifer
- Adam D. Smith
In Computational Theory and Mathematics
- Jonathan Ullman
- Salil P. Vadhan
- Cynthia Dwork
- Adam D. Smith
- Aaron Roth
- Mark Bun
- Thomas Steinke
- Vitaly Feldman
In Discrete Mathematics and Combinatorics
- Jonathan Ullman
- Adam D. Smith
- Cynthia Dwork
- Aaron Roth
- Thomas Steinke
- Kobbi Nissim
- Kamalika Chaudhuri
- Salil P. Vadhan
In Algorithms & Complexity
- Jonathan Ullman
- Vitaly Feldman
- Ninghui Li
- Jayadev Acharya
- Ziteng Sun
- Uri Stemmer
- Kunal Talwar
- Thomas Steinke
Citations in the corpus
- Advances and Open Problems in Federated Learning (2019, background): “i-message Central Expected max. error O~( p n) (~ p n) O~(min( 4 p n; p B)) (min(~ 4 p n; p B)) (1)~ (1)~ Communication/user (1) any (1)~ any (1)~ (1)~ References [51] [50] [406, 157, 43] [178] [178] [291, 369] Table 10: Upper and lower bounds on the expected maximum error for frequency estimation o”
- Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “1) Discussion on the Convergence Rates: Most existing results in private empirical risk minimization (ERM) problems, such as the exponential mechanism [61] and DP-SGD [62], focus on central DP instead of local DP.”
- Federated Learning and Differential Privacy: Software tools analysis, the Sherpa.ai FL framework and methodological guidelines for preserving data privacy (2020, background): “• Exponential mechanism [20].”
- AdaCliP: Adaptive Clipping for Private SGD (2019, methodology): “2 Differential privacy for machine learning Differential privacy definition was originally used to provide strong privacy guarantees for database querying and since used in several applications [20, 21, 22].”
- Wireless Network Intelligence at the Edge (2018, background): “, the exponential mechanism [157], achieving the -DP.”
- Differentially Private Fair Learning (2018, methodology): “lowing denition. Let ‘be the sensitivity of the loss function ‘with respect to the database argument D. In other words, ‘max hPH max D;D1PDm DD1 ‘pD;hq ‘ D1;h Denition 2.5 (Exponential Mechansim [McSherry and Talwar, 2007]). Given a database DP Dmand a privacy parameter , output hPHwith probability ”
- The structure of optimal private tests for simple hypotheses (2018, methodology): “ =max(a,min(z,b))). Define the soft clamped log-likelihood test: scLLRa,b(x)= P with probability ∝exp(1 2 cLLRa,b(x)) Q with probability ∝1 ThetestscLLRisaninstanceoftheexponentialmechanism[MT07],andthusscLLRa,b satisfies ε-differential privacy for ε =b−a 2 . Similarly, define the noisy clamped lo”
- Distributed Differential Privacy via Shuffling (2018, background): “In the central model, this problem is solved by the exponential mechanism [24] with a dataset of size just n =O(ε logd), and this is optimal [2, 27].”
- Tight Lower Bounds for Locally Differentially Private Selection (2018, background): “ere are more powerful differentially private algorithms in the central model that seem to have no analogue in the local model, most notably the celebrated exponential mechanism of McSherry and Talwar [MT07]. The exponential mechanism is one of the most fundamental tools for analyzing high-dimensiona”
- BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, methodology): “The process of local privatization of each client’s value (Figure 6) follows the strategy of the Exponential mechanism introduced by [30].”
- Tight Lower Bounds for Differentially Private Selection (2017, methodology): “Specifically, we can use the exponential mechanism [19] to identify an approximate largest coordinate of p, and then repeat on the other coordinates.”
- RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response (2014, background): “It is natural to ask why we built our mechanisms upon randomized response, rather than upon two primitives most commonly used to achieve differential privacy: the Laplace and Exponential mechanisms [12, 21].”
- Extremal Mechanisms for Local Differential Privacy (2014, methodology): “The typical recipe is to propose a differentially private mechanism inspired by [11, 13, 26, 20], and then establish its near-optimality by comparing the achievable utility to a converse, for example in principal component analysis [8, 5, 19, 24], linear queries [21, 18], logistic regression [7] and”
- Scalable Private Learning with PATE (2018, background): “The most commonly used differentially private selection mechanisms are exponential mechanism (McSherry & Talwar, 2007) and LNMax (Bhaskar et al., 2010).”
- Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, methodology): “Earlier models of differential privacy [16], [17], [29] rely on a trusted data curator, who collects and manages the exact private information of individuals, and releases statistics derived from the data under differential privacy requirements.”