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

DOI10.1145/167088.167166zbMath1310.68207OpenAlexW1984992697MaRDI QIDQ5248494

David Zuckerman, Nathan Linial, Michael Luby, Michael E. Saks

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167166

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Combinatorial aspects of packing and covering (05B40)

Related Items

Efficient constructions of Hitting Sets for systems of linear functions ⋮ Simulating BPP using a general weak random source ⋮ Approximating hyper-rectangles: Learning and pseudorandom sets