Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Binomial Distribution
Symmetric Function
Subscribe
Academic
Publications
Pseudorandom Generators for Combinatorial Shapes
Pseudorandom Generators for Combinatorial Shapes,Electronic Colloquium on Computational Complexity,Parikshit Gopalan,Raghu Meka,Omer Reingold,David Zu
Edit
Pseudorandom Generators for Combinatorial Shapes
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Parikshit Gopalan
,
Raghu Meka
,
Omer Reingold
,
David Zuckerman
We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, biased spaces, 0/1 halfspaces, and 0/1 modular sums. A function f : [m] n !f0; 1g is an (m;n)combinatorial shape if there exist sets A1;:::;An [m] and a
symmetric function
h :f0; 1g n ! f0; 1g such that f(x1;:::;xn) = h(1A1 (x1);:::; 1An (xn)). Our generator uses seed length O(logm + logn + log 2 (1=")) to get error ". When m = 2, this gives the rst generator of seed length O(logn) which fools all weightbased tests, meaning that the distribution of the weight of any subset is "close to the appropriate
binomial distribution
in statistical distance. Along the way, we give a generator for combinatorial rectangles with seed length O(log 3=2 n) and error 1=poly(n), matching Lu’s bound [ICALP 1998].
Journal:
Electronic Colloquium on Computational Complexity  ECCC
, vol. 17, 2010
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.informatik.unitrier.de
)
(
eccc.hpiweb.de
)
Citation Context
(1)
...Faced with this difficulty, research was focussed on solving special cases of this problem with better seed lengths ([15],[16],[
17
])...
...In contrast, results in [15], [16], [
17
] which are directed towards “symmetric functions” use a combination of hash functions and INW generator...
Anindya De
.
Pseudorandomness for Permutation and Regular Branching Programs
References
(23)
Simple Constructions of Almost kWise Independent Random Variables
(
Citations: 184
)
Noga Alon
,
Oded Goldreich
,
Johan Håstad
,
René Peralta
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 544553, 1990
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
(
Citations: 15
)
Roy Armoni
,
Michael E. Saks
,
Avi Wigderson
,
Shiyu Zhou
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 412421, 1996
Polylogarithmic Independence Can Fool DNF Formulas
(
Citations: 24
)
Louay Bazzi
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 6373, 2007
Total variation asymptotics for sums of independent integer random variables
(
Citations: 26
)
A. D. Barbour
,
V. Ćekanavićius
Journal:
Annals of Probability  ANN PROBAB
, vol. 30, no. 2002, pp. 509545, 2002
Bounded Independence Fools Halfspaces
(
Citations: 23
)
Ilias Diakonikolas
,
Parikshit Gopalan
,
Ragesh Jaiswal
,
Rocco A. Servedio
,
Emanuele Viola
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. abs/0902.3, no. 8, pp. 171180, 2009
Sort by:
Citations
(1)
Pseudorandomness for Permutation and Regular Branching Programs
Anindya De
Conference:
Annual IEEE Conference on Computational Complexity  CCC
, pp. 221231, 2011