Abstract
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]n to within o(1) error (improving on the constructions of [EGLNV92]). The construction extends the techniques of [LLSZ95] for the analogous hitting set problem, most notably via discrepancy preserving reductions.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 412-421 |
| Number of pages | 10 |
| Journal | Annual Symposium on Foundations of Computer Science - Proceedings |
| State | Published - 1996 |
| Externally published | Yes |
| Event | Proceedings of the 1996 37th Annual Symposium on Foundations of Computer Science - Burlington, VT, USA Duration: Oct 14 1996 → Oct 16 1996 |
All Science Journal Classification (ASJC) codes
- Hardware and Architecture