Efficient construction of a small hitting set for combinatorial rectangles in high dimension
From MaRDI portal
Publication:1382408
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
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]
