PaperlayerView exact revision on arXiv

Source-linked AI summary

Bounded Independence Fools Degree-2 Threshold Functions

Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson

arXiv:0911.3389v2cs.CC

TL;DR

The paper asks how much independence is needed to fool degree-2 polynomial threshold functions, a question previously open beyond degree one. It uses multivariate FT-mollification and proves that ˜Ω(ε^-9)-wise independence suffices, with extensions to Gaussian inputs and constant-size intersections.

  • Problem

    Before this work, it was unknown whether o(n)-wise independence could fool degree-2 PTFs for constant ε, and no nontrivial result was known for degrees above one.

    Source: §1 · p. 2

  • Method

    The proof combines multivariate FT-mollification with a decomposition of quadratic forms and reduces general PTFs to regular ones.

    Source: §3.1 · p. 4, §3.2 · p. 5

  • Results

    Any ˜Ω(ε^-9)-wise independent distribution ε-fools all degree-2 PTFs; the result also extends to Gaussian inputs and constant-size intersections.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Known k-wise independent constructions give degree-2 PTF generators with seed length log(n) · eO(ε^-9).

    Source: §1 · p. 2

    The direct univariate approximation approach fails for regular degree-2 PTFs, even if its degree is increased.

    Source: §3 · p. 4

Abstract

from arXiv · show

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of k-wise independent distributions, we obtain a broad class of explicit generators that epsilon-fool the class of degree-2 threshold functions with seed length log(n)*poly(1/epsilon). Our approach is quite robust: it easily extends to yield that the intersection of any constant number of degree-2 threshold functions is epsilon-fooled by poly(1/epsilon)-wise independence. Our results also hold if the entries of x are k-wise independent standard normals, implying for example that bounded independence derandomizes the Goemans-Williamson hyperplane rounding scheme. To achieve our results, we introduce a technique we dub multivariate FT-mollification, a generalization of the univariate form introduced by Kane et al. (SODA 2010) in the context of streaming algorithms. Along the way we prove a generalized hypercontractive inequality for quadratic forms which takes the operator norm of the associated matrix into account. These techniques may be of independent interest.

1 Introduction

The paper addresses whether bounded independence can fool degree-2 polynomial threshold functions, answering an open question with a poly(1/ε)-wise-independence bound. It also gives generator and robustness consequences, including Gaussian inputs and intersections of a constant number of threshold functions.

Our Results

  • Any ˜Ω(ε^-9)-wise independent distribution on {−1, 1}^n ε-fools all degree-2 PTFs, making progress toward identifying k(n, d, ε) for degree d ≥ 2.Source: §1 · p. 2
  • Known constructions of k-wise independent distributions yield degree-2 PTF generators with seed length log(n) · eO(ε^-9).The paper describes this as a large class of pseudorandom generators.Source: §1 · p. 2
  • The result extends to k-wise independent standard Gaussians and to intersections of any constant number of degree-2 threshold functions, on both the hypercube and Gaussian space.The paper also states that O(1/ε²)-wise independence suffices for Goemans–Williamson hyperplane rounding.Source: §1 · p. 2
  • Bounded independence suffices for the degree-2, low-influence case of the invariance principle, without requiring full independence of the inputs.The principle concerns the distribution of a polynomial under uniform hypercube inputs versus standard Gaussian inputs.Source: §1 · p. 2
  • Other known Goemans–Williamson rounding derandomizations have better ε dependence, but do not rely solely on k-wise independence.For intersections of m halfspaces, cited generators have different dependence on m and are not both based solely on bounded independence [20] [23].Source: §1 · pp. 2–3

Motivation and Related Work

  • The work builds on interest in broad, natural pseudorandom-generator families, including bounded-independence constructions for AC0 and depth-2 circuits.Meka and Zuckerman [30] independently gave degree-d PTF generators; their degree-2 seed length is similar but worse by a poly(1/ε) factor, and their generator is not based on k-wise independence alone.Source: §1 · p. 3

2 Notation

This section sets notation for polynomial expansions, influence and regularity, and two conventions used in the proofs. It also relates fooling a polynomial’s sign to fooling its nonnegative region.

2 Notation

  • A polynomial is represented by its Fourier–Walsh expansion, and variable influence is defined from its coefficients.A polynomial is τ-regular when every variable’s influence is at most τ times its total influence; its sign function is then a τ-regular PTF.Source: §2 · p. 3
  • Fooling the expectation of sgn(p(x)) is equivalent, up to changing ε by a factor of 2, to fooling the indicator of p(x) ≥ 0.The section uses the latter formulation in some proofs.Source: §2 · p. 3
  • The notation A ≈ε B means |A − B| = O(ε), while d2(x, R) denotes the L2 distance from x to region R.Source: §2 · p. 3

3 Overview of our proof of Theorem 1.1

The proof first handles regular degree-2 PTFs and then reduces the general case to the regular one. Its main technical step combines multivariate FT-mollification with a low-dimensional representation and a decomposition of the quadratic form.

3 Overview of our proof of Theorem 1.1

  • The proof handles regular degree-2 PTFs first, then reduces general PTFs to the regular case using an adaptation of prior random-restriction results [15].The regular case contains the main technical contribution.Source: §3 · p. 3
  • Fooling is characterized using degree-k upper and lower sandwiching polynomials, reducing the task to constructing approximants that exploit the function’s structure.The approach seeks to turn the n-dimensional approximation into a lower-dimensional problem.Source: §3 · p. 3

3.1 FT-mollification

  • The univariate FT-mollification approach smooths a function by convolution with a scaled Fourier transform, giving better control of high-order derivatives than Friedrichs mollification.The proof outline uses closeness away from a small region, anti-concentration, and derivative bounds in a Taylor argument; this univariate approach fails for degree-2 PTFs.Source: §3.1 · p. 4
  • Multivariate FT-mollification is applied to an indicator of a region representing the threshold event, but dimension-dependent error bounds motivate finding a low-dimensional representation.Fooling the sign function and fooling the indicator of a containing region are equivalent in this setup.Source: §3.1 · p. 5

3.2 Our Approach

  • The quadratic form is decomposed as p1 − p2 + p3, with p1 and p2 positive semidefinite and p3 indefinite with small-magnitude eigenvalues.Positive semidefiniteness supports sharper Taylor bounds, while the small eigenvalues enable stronger moment bounds for p3; p1 and p2 also have no small nonzero eigenvalues for improved tail bounds.Source: §3.2 · p. 5
  • The proof represents the threshold event as a region in three dimensions and preserves its probability under bounded independence using FT-mollification.The analysis combines tail bounds for p1 and p2, a new moment bound for p3, and anti-concentration and invariance-principle tools.Source: §3.2 · p. 5

4 Multivariate FT-mollification

Multivariate FT-mollification smooths bounded functions while controlling mixed derivatives, and approximates them at points where the original function is locally continuous. Applied to region indicators, it provides bounds based on distance from the region’s boundary.

4 Multivariate FT-mollification

  • Theorem 4.8 gives a smooth approximation with bounded mixed derivatives and guarantees closeness wherever the original function changes by at most ε within distance δ.The derivative bounds scale with the smoothing parameter and the order of differentiation.Source: §4 · pp. 8–9
  • The authors use a simpler derivative-bound proof because their main result needs mollification only in dimensions d ≤ 4.Sharper bounds are available and are useful when mollifying in higher dimensions.Source: §4 · p. 9
  • For a region indicator, the mollified function stays between 0 and 1 and agrees with the indicator away from the boundary up to a bound governed by boundary distance.The region boundary is the set whose every neighborhood intersects both the region and its complement.Source: §4 · p. 10

5 A spectral moment bound for quadratic forms

This section bounds moments of quadratic forms using both the matrix’s Frobenius norm and its largest eigenvalue. The resulting bound generalizes the degree-2 hypercontractive inequality when the operator norm is at most 1.

5 A spectral moment bound for quadratic forms

  • The matrix associated with a quadratic polynomial places its diagonal coefficients on the diagonal and half of each off-diagonal coefficient in the corresponding symmetric entries.This representation gives p(x) = xT Apx.Source: §5 · p. 10
  • Theorem 5.1 bounds quadratic-form moments using both the Frobenius norm and the largest-magnitude eigenvalue of the associated symmetric matrix.The theorem applies to symmetric A and random x in {−1, 1}^n for k ≥ 2; its constant is absolute.Source: §5 · p. 10
  • When the matrix operator norm is at most 1, the moment bound recovers a similar bound to hypercontractivity and generalizes that inequality for degree-2 polynomials.The passage also identifies the result as a generalization of Whittle’s inequality.Source: §5 · p. 10

6 Fooling regular degree-2 threshold functions

For regular degree-2 threshold functions, the proof compares expectations under fully independent and bounded-independent Bernoulli inputs. It combines a decomposition of the polynomial, multivariate smoothing, and anticoncentration; the result also extends to standard normal inputs.

6 Fooling regular degree-2 threshold functions

  • Theorem 6.1 assumes 0 < ε < 1, independent Bernoulli inputs X1,...,Xn, and 2k-wise independent Bernoulli inputs Y1,...,Yn, with k a sufficiently large multiple of 1/ε8, for multilinear degree-2 p.Source: §6 · p. 12
  • The proof decomposes the quadratic part into positive-semidefinite forms with no small nonzero eigenvalues and an indefinite form with small eigenvalues, then represents the polynomial through a map into R^4.The decomposition also includes a linear form and constant; the first two mapped coordinates are real because their forms are positive semidefinite.Source: §6 · p. 12
  • Bounded-independence anticoncentration is established for k-wise independent Bernoulli inputs when k is at least a sufficiently large constant times 1/(ε′)^4.The lemma applies at an arbitrary threshold t.Source: §6 · p. 13
  • The theorem also holds for standard normal inputs, without an error term depending on the maximum influence τ.The proof reduces this case to the Bernoulli case.Source: §6 · p. 16

7 Reduction to the regular case

The paper reduces fooling arbitrary degree-d polynomial threshold functions to fooling regular ones, with an additional independence cost. For degree 2, the regular-case result and a choice of regularity parameter yield polynomial dependence on 1/ε.

7 Reduction to the regular case

  • If Kd-wise independence ε-fools τ-regular degree-d threshold functions, then (Kd + Ld)-wise independence ε-fools all degree-d threshold functions.The theorem gives Ld as a function of 1/τ and d.Source: §7 · p. 17
  • For degree 2, τ = O(ε^9) gives a regular-case independence requirement K2 = O(ε^-8), and substituting this τ into the reduction yields the main theorem.The stated regular-case guarantee is for τ-regular degree-2 threshold functions.Source: §7 · p. 17
  • The reduction uses a decision tree whose typical leaves are either regular threshold functions or functions τ-close to constant; bounded independence preserves leaf probabilities and supports the leafwise analysis.The tree has depth at most Ld, and the close-to-constant claim is extended to distributions with O(d · log(1/τ))-wise independence.Source: §7 · p. 17

8 Fooling intersections of threshold functions

The section establishes that bounded independence fools intersections of halfspaces under Gaussian inputs and connects this result to Goemans–Williamson rounding. It also records supporting tools and explains why earlier approximation approaches do not extend directly to degree-2 PTFs.

8 Fooling intersections of threshold functions

  • To achieve expected MaxCut value within a factor .878...−ε of optimal, Gaussian entries with Ω(1/ε²)-wise independence suffice.The proof reduces each edge's cut event to a union of intersections of two halfspaces.Source: §8 · p. 18
  • For two Gaussian halfspaces, Ω(1/ε²)-wise independence changes their intersection probability by less than ε.The section also uses this result to obtain a bounded-independence guarantee for Goemans–Williamson rounding.Source: §8 · pp. 17–18
  • FT-mollifying the indicator of a two-dimensional quadrant proves the two-halfspace result and extends to constant-size intersections with polynomial dependence on their number.The stated extensions include intersections of degree-2 threshold functions and Bernoulli inputs.Source: §8 · p. 18

A Basic linear algebra facts

  • The spectral theorem diagonalizes symmetric matrices, and the appendix defines eigenvalue-based quantities used in the quadratic-form arguments.For a real symmetric matrix, the eigenvalues are real; λmin is the smallest magnitude of a nonzero eigenvalue, and ∥A∥∞ is the largest eigenvalue magnitude.Source: A Basic linear algebra facts · p. 22

B.1 Facts about low-degree polynomials.

  • The bounded-independence tail-bound proof uses the fact that an even moment of a polynomial is determined by sufficiently many independent coordinates.The supplied proof states that bounding E[|f(X)|^k] requires only dk-wise independence.Source: §B.1 · p. 23

B.2 Facts about quadratic forms.

  • A quadratic form decomposes as f1 − f2 + f3, with f1 and f2 positive semidefinite and f3 containing the remaining small-magnitude eigenvalues.The construction uses spectral decomposition and does not increase the component matrices' Frobenius norms.Source: §B.2 · p. 24

C.1 Why the approximation theory approach failed

  • For degree-2 PTFs, hypercontractive concentration alone cannot control the approximation error, even as the approximating polynomial's degree increases.The text also notes that the available anticoncentration is too weak to bound the error where the approximation is pointwise accurate.Source: §C.1 · p. 25

C.2 Why the analysis for univariate FT-mollification failed

The earlier univariate FT-mollification analysis fails for degree-2 PTFs because its Taylor remainder need not shrink with increasing independence. In the Boolean setting, the proof uses bounded-independence tail and anticoncentration arguments.

C.2 Why the analysis for univariate FT-mollification failed

  • The Taylor-remainder bound does not vanish as k increases for degree d ≥2, because the moment bound grows faster than the factorial denominator.The text says increasing the independence parameter can worsen this bound.Source: §C.2 · p. 25

D.1 Boolean setting.

  • The Boolean proof's anticoncentration step remains available under k-wise independence, provided k is sufficient for the cited anticoncentration lemma.The proof identifies this as the second independence-sensitive step after applying the quadratic-form tail bound.Source: §D.1 · p. 26

D.2 Gaussian Setting

The Gaussian-setting argument reduces independent normal inputs to a Bernoulli polynomial and applies the Boolean result. The section states that the conclusion of Theorem 6.1 extends to Gaussian measure, with a quantitative independence requirement in Theorem D.1.

D.2 Gaussian Setting

  • Theorem D.1 uses 2k-wise independent standard normals, with k a sufficiently large multiple of ε^-8, for the Gaussian extension of Theorem 6.1.The supplied theorem statement is truncated, while the surrounding text explicitly says its conclusion holds under Gaussian measure.Source: §D.2 · p. 26
  • The proof replaces each Gaussian coordinate by a sum of Bernoulli variables, preserving the polynomial through a quantile-based construction.It defines thresholds from the standard normal CDF and selects the Bernoulli signs according to the threshold bin.Source: §D.2 · p. 26
  • After discretization makes the maximum influence small, the proof applies Theorem 6.1 and uses anticoncentration to control sign disagreements.The argument separately invokes anticoncentration for the independent and k-wise independent inputs.Source: §D.2 · p. 27
  • For central quantile bins, neighboring thresholds differ by o(1), supporting the coupling between the discretized and Gaussian inputs.The proof considers bin indices within a fixed relative range around N/2.Source: §D.2 · pp. 27–28

E Proofs from Section 7

The appendix proves the Section 7 result using random restrictions and a decision-tree decomposition. Its leaves are regular PTFs or functions close to constant, allowing bounded-independence arguments to handle the restricted functions.

E Proofs from Section 7

  • A decision tree of bounded depth reaches, with probability at least 1−τ, a leaf that is either a τ-regular PTF or close to constant under sufficiently independent distributions.The stated depth is (1/τ) · (d log(1/τ))^O(d).Source: E Proofs from Section 7 · p. 28
  • Lemma E.6 gives restriction alternatives: the restricted function becomes close to constant with probability at least 1/2^O(d), or the restricted polynomial becomes τ′′-regular with that probability.For the close-to-constant case, the lemma also gives a bound under O(d log(1/β))-wise independent distributions.Source: E Proofs from Section 7 · p. 30
  • When the critical index is large, a random restriction can create a large constant term and leave small nonconstant coefficients, making the restricted function close to constant.The proof uses anticoncentration on the influential variables, followed by a concentration bound on the remaining coefficients.Source: E Proofs from Section 7 · pp. 30–31
  • The tail-variable concentration step needs only O(d log(1/β))-wise independence, rather than full independence.The proof obtains this by applying the polynomial tail bound with a parameter determined by the coefficient-norm and constant-term bounds.Source: E Proofs from Section 7 · p. 31

F Appendix to Section 8

The appendix extends the Gaussian halfspace-intersection result and outlines an extension to degree-2 threshold intersections. It also points to quantitative improvements, including quartic dependence on the number of halfspaces in the Gaussian setting.

F Appendix to Section 8

  • For Gaussian intersections of m halfspaces, Ω(m^6/ε^2)-wise independence suffices.The appendix notes that the dependence on m can be reduced to quartic in Section G.2.Source: F Appendix to Section 8 · pp. 31–32

G Various Quantitative Improvements

F Appendix to Section 8

  • For m degree-2 threshold functions, the proof maps the intersection problem to a region in R^4m after decomposing each polynomial.It defines one region constraint for each polynomial using its decomposition.Source: F Appendix to Section 8 · p. 32
  • The appendix extends the Gaussian halfspace-intersection theorem to degree-2 polynomial thresholds, with k = Ω(poly(m)/ε^8).The supplied theorem statement specifies Gaussian inputs and k-wise independent Gaussian inputs.Source: F Appendix to Section 8 · p. 32
  • For hypercube inputs, the argument applies decision-tree restrictions separately to each threshold function and combines them with a union bound.It sets τ′ = τ/m, with τ = ε^2 for halfspaces and τ = ε^9 for degree-2 threshold functions.Source: F Appendix to Section 8 · p. 33

G.1 Improved FT-mollification

The quantitative improvements sharpen FT-mollification derivative bounds and reduce the independence requirement for Gaussian intersections of halfspaces. The latter improvement uses an orthonormal change of basis and is specific to the Gaussian setting.

G.1 Improved FT-mollification

  • For |β| = Ω(d), the improved FT-mollification bound can shrink the earlier derivative upper bound by a factor d^−|β|/2 in high dimension.The improvement is achieved by sharpening the bound on ∥∂βB∥1.Source: §G.1 · pp. 33–34

G.2 Improvements to fooling the intersection of halfspaces

  • The second factor of m is shaved by an orthonormal basis change, an improvement that is specific to Gaussian inputs and does not carry over to Bernoulli inputs.The other factor is shaved using the improved derivative bound.Source: §G.2 · p. 35
  • For Gaussian intersections of m halfspaces, even k = Ω(m^4/ε^2)-wise independence suffices.The earlier bound was Ω(m^6/ε^2); the proof shaves one factor of m using a sharper derivative bound and another with a change of basis.Source: §G.2 · p. 35
Loading 0911.3389v2…