Bounded independence plus noise fools products

DOI10.4230/LIPICS.CCC.2017.14MaRDI QIDQ5111144zbMATH OpenFDO

Authors Elad Haramaty, Chin Ho Lee, Emanuele Viola

Publication date 26 May 2020

zbMATH Keywords

noisepseudorandomnesserror-correcting codesbounded independenceproduct tests

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Pseudo-random numbers; Monte Carlo methods (11K45) Synchronization error-correcting codes (94B50)

Recommendations

• Bounded independence plus noise fools products
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Bounded Independence Fools Halfspaces
• Polylogarithmic independence can fool DNF formulas
• Improved pseudorandom generators for depth 2 circuits

Cited in

(2)

• Bounded Independence Fools Halfspaces
• Bounded independence plus noise fools products

This page was built for publication: Bounded independence plus noise fools products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111144)