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

DOI10.1007/BF01200907zbMath0886.68076OpenAlexW2611007065MaRDI QIDQ1382408

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

Publication date: 26 March 1998

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01200907

zbMATH Keywords

rectanglessmall hitting set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial aspects of packing and covering (05B40)

Related Items

Almost Optimal Cover-Free Families ⋮ Recursive methods for some problems in coding and random permutations ⋮ Finding hidden independent sets in interval graphs ⋮ Low discrepancy sets yield approximate min-wise independent permutation families ⋮ Unnamed Item ⋮ Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints ⋮ Deterministic constructions of high-dimensional sets with small dispersion ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ A note on stabbing convex bodies with points, lines, and flats ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Expected dispersion of uniformly distributed points ⋮ Improved dispersion bounds for modified Fibonacci lattices ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Unnamed Item ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ A lower bound for the hitting set size for combinatorial rectangles and an application ⋮ Active sampling for multiple output identification ⋮ Perfect information leader election in \(\log^*n+O(1)\) rounds

Cites Work

• Expanders, randomness, or time versus space
• On the power of two-point based sampling
• Explicit constructions of linear-sized superconcentrators
• Pseudorandom generators for space-bounded computation
• Universal classes of hash functions
• Inclusion-exclusion: exact and approximate
• Simulating BPP using a general weak random source
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Approximating the Number of Zeroes of a GF[2 Polynomial]