Author name cluster
Roy Armoni
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
1 author row
Possible papers
2FOCS Conference 1996 Conference Paper
Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
- Roy Armoni
- Michael E. Saks
- Avi Wigderson
- Shiyu Zhou
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.