TY - GEN

T1 - Efficient construction of a small hitting set for combinatorial rectangles in high dimension

AU - Linial, Nati

AU - Luby, Michael

AU - Saks, Michael

AU - Zuckerman, David

N1 - Publisher Copyright:
© 1993 ACM.

PY - 1993/6/1

Y1 - 1993/6/1

N2 - Given d, m and €, we deterministically produce a sequence of points S that hits every combinatorial rectangle in [m]d of volume at least 6. Both the running time of the algorithm and ISI are polynomial in m log(d) /€. This algorithm has applications to deterministic constructions of small sample spaces for general multivalued random variables.

AB - Given d, m and €, we deterministically produce a sequence of points S that hits every combinatorial rectangle in [m]d of volume at least 6. Both the running time of the algorithm and ISI are polynomial in m log(d) /€. This algorithm has applications to deterministic constructions of small sample spaces for general multivalued random variables.

UR - http://www.scopus.com/inward/record.url?scp=0027148936&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027148936&partnerID=8YFLogxK

U2 - 10.1145/167088.167166

DO - 10.1145/167088.167166

M3 - Conference contribution

AN - SCOPUS:0027148936

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 258

EP - 267

BT - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993

PB - Association for Computing Machinery

T2 - 25th Annual ACM Symposium on Theory of Computing, STOC 1993

Y2 - 16 May 1993 through 18 May 1993

ER -