Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles

A common subproblem of DNF approximate counting and derandomizing RL is the discrepancy problem for combinatorial rectangles. We explicitly construct a poly(n)-size sample space that approximates the volume of any combinatorial rectangle in [n]/sup n/ to within o(1) error. The construction extends the previous techniques for the analogous hitting set problem, most notably via discrepancy preserving reductions.

Authors

• Roy Armoni
• Michael E. Saks
• Avi Wigderson
• Shiyu Zhou

Keywords

• Computer science
• Mathematics
• Distributed computing
• Polynomials
• Circuits
• Rectangular
• Cost Reduction
• Dimensionality Reduction
• Functional Independence
• Family Functioning
• Hash Function
• Family Settings
• Details Of Construction
• Power-of-two
• Input Length
• Multiset
• Explicit Construction
• Independent Families
• Department Of Computer Science
• Output Length
• Fraction Of Points
• Rutgers University