Efficient construction of a small hitting set for combinatorial rectangles in high dimension |
| |
Authors: | Nathan Linial Michael Luby Michael Saks David Zuckerman |
| |
Affiliation: | (1) Computer Science Department, Hebrew University, Jerusalem, Israel;(2) DEC/SRC, 130 Lytton Avenue, 94301 Palo Alto, California;(3) Department of Mathematics, Rutgers University, 08854 New Brunswick, NJ, USA;(4) Department of Computer Sciences, The University of Texas at Austin, 78713 Austin, Texas, USA |
| |
Abstract: | We describe a deterministic algorithm which, on input integersd, m and real number (0,1), produces a subset S of [m]d={1,2,3,...,m}d that hits every combinatorial rectangle in [m]d of volume at least , i.e., every subset of [m]d the formR1×R2×...×Rd of size at least md. The cardinality of S is polynomial inm(logd)/, and the time to construct it is polynomial inmd/. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables.A preliminary version of this paper appeared in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993.Research partially done while visiting the International Computer Science Institute. Research supported in part by a grant from the Israel-USA Binational Science Foundation.A large portion of this research was done while still at the International Computer Science Institute in Berkeley, California. Research supported in part by National Science Foundation operating grants CCR-9304722 and NCR-9416101, and United States-Israel Binational Science Foundation grant No. 92-00226.Supported in part by NSF under grants CCR-8911388 and CCR-9215293 and by AFOSR grants AFOSR-89-0512 AFOSR-90-0008, and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology. Research partially done while visiting the International Computer Science Institute.Partially supported by NSF NYI Grant No. CCR-9457799. Most of this research was done while the author was at MIT, partially supported by an NSF Postdoctoral Fellowship. Research partially done while visiting the International Computer Science Institute. |
| |
Keywords: | 068Q25 05B40 68R05 |
本文献已被 SpringerLink 等数据库收录! |
|