Fooling parity tests with parity gates

DOI10.1007/978-3-540-27821-4_34MaRDI QIDQ5313041zbMATH OpenOpenAlexFDO

Authors Dan Gutfreund, Emanuele Viola

Publication date 25 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99805

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Improved pseudorandom generators for depth 2 circuits
• Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
• On ε‐biased generators in NC⁰
• Randomness-Efficient Sampling Within NC 1
• Pseudorandom Bit Generators That Fool Modular Sums

Cited in

(11)

• Local expanders
• 3SUM, 3XOR, triangles
• On probabilistic space-bounded machines with multiple access to random tape
• Randomness-Efficient Sampling Within NC 1
• Pseudorandom Bit Generators That Fool Modular Sums
• Arithmetic circuits: the chasm at depth four gets wider
• Typically-correct derandomization for small time and space
• scientific article; zbMATH DE number 7758312 (Why is no real title available?)
• Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\)
• Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
• Randomness-efficient sampling within NC\(^{1}\)

This page was built for publication: Fooling parity tests with parity gates

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