| Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension (1993) | |||||||||||||||
Abstract | |||||||||||||||
| Given d, m and epsilon, we deterministically produce a sequence of points S that hits every combinatorial rectangle in [m]^d of volume at least epsilon. Both the running time of the algorithm and |S| are polynomial in m log(d)/epsilon. This algorithm has applications to deterministic constructions of small sample spaces for general multivalued random variables. 1 Introduction The problem we consider in this paper is motivated by the following basic witness finding problem: design an efficient algorithm that on Hebrew University, Computer Science Department, Jerusalem Israel. Research partially done while visiting the International Computer Science Institute. y International Computer Science Institute and UC Berkeley. Research partially supported by NSF Grant CCR-9016468 and grant No. 89-00312 from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel. z Department of Mathematics, Rutgers University and Department of CSE, UCSD. Supported in part by NSF under grant C... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||