Bounded Independence Fools Halfspaces

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

doi:10.1109/FOCS.2009.68

Bounded Independence Fools Halfspaces

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We show that any distribution on {−1, +1}ⁿ that is k-wise independent fools any halfspace (a.k.a. threshold) h : {−1, +1}ⁿ → {−1, +1}, i.e., any function of the form h(x) = sign(∑ⁿ_i=1 w_ix_i − θ) where the w₁, . . . , w_n, θ are arbitrary real
numbers, with error ε for k = O(ε⁻² log²(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}ⁿ that fool halfspaces. Specifically, we fool halfspaces with error ε and seed length s = k · log n = O(log n · ε⁻² log²(1/ε)).

Our approach combines classical tools from real approximation theory with structural results

Original language	English
Title of host publication	2009 50th Annual IEEE Symposium on Foundations of Computer Science
Place of Publication	Los Alamitos, CA, USA
Publisher	Institute of Electrical and Electronics Engineers
Pages	171-180
Number of pages	10
ISBN (Print)	978-1-4244-5116-6
DOIs	https://doi.org/10.1109/FOCS.2009.68
Publication status	Published - 2009

Access to Document

10.1109/FOCS.2009.68

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5438634

Cite this

@inproceedings{2f8962bac15e468598a338f150b44565,

title = "Bounded Independence Fools Halfspaces",

abstract = "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(∑ni=1 wixi − θ) where the w1, . . . , wn, θ are arbitrary real numbers, with error ε for k = O(ε−2 log2(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 ε and seed length s = k · log n = O(log n · ε−2 log2(1/ε)). Our approach combines classical tools from real approximation theory with structural results",

author = "Ilias Diakonikolas and Parikshit Gopalan and Ragesh Jaiswal and Servedio, \{Rocco A.\} and Emanuele Viola",

year = "2009",

doi = "10.1109/FOCS.2009.68",

language = "English",

isbn = "978-1-4244-5116-6",

pages = "171--180",

booktitle = "2009 50th Annual IEEE Symposium on Foundations of Computer Science",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

}

TY - GEN

T1 - Bounded Independence Fools Halfspaces

AU - Diakonikolas, Ilias

AU - Gopalan, Parikshit

AU - Jaiswal, Ragesh

AU - Servedio, Rocco A.

AU - Viola, Emanuele

PY - 2009

Y1 - 2009

N2 - 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(∑ni=1 wixi − θ) where the w1, . . . , wn, θ are arbitrary real numbers, with error ε for k = O(ε−2 log2(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 ε and seed length s = k · log n = O(log n · ε−2 log2(1/ε)). Our approach combines classical tools from real approximation theory with structural results

AB - 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(∑ni=1 wixi − θ) where the w1, . . . , wn, θ are arbitrary real numbers, with error ε for k = O(ε−2 log2(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 ε and seed length s = k · log n = O(log n · ε−2 log2(1/ε)). Our approach combines classical tools from real approximation theory with structural results

U2 - 10.1109/FOCS.2009.68

DO - 10.1109/FOCS.2009.68

M3 - Conference contribution

SN - 978-1-4244-5116-6

SP - 171

EP - 180

BT - 2009 50th Annual IEEE Symposium on Foundations of Computer Science

PB - Institute of Electrical and Electronics Engineers

CY - Los Alamitos, CA, USA

ER -

Bounded Independence Fools Halfspaces

Abstract

Access to Document

Fingerprint

Cite this