Discrepancy sets and pseudorandom generators for combinatorial rectangles

Roy Armoni, Michael Saks, Avi Wigderson, Shiyu Zhou

Research output: Contribution to journalConference articlepeer-review

30 Scopus citations

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 languageEnglish (US)
Pages (from-to)412-421
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1996
Externally publishedYes
EventProceedings of the 1996 37th Annual Symposium on Foundations of Computer Science - Burlington, VT, USA
Duration: Oct 14 1996Oct 16 1996

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this