Optimal Hitting Sets for Combinatorial Shapes

DOI10.1007/978-3-642-32512-0_36MaRDI QIDQ3167414zbMATH OpenOpenAlexFDO

Authors Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.3439

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) Randomized algorithms (68W20)

Abstract: We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2011). These generalize many well-studied classes of tests, including symmetric functions and combinatorial rectangles. Generalizing results of Linial, Luby, Saks, and Zuckerman (Combinatorica 1997) and Rabani and Shpilka (SICOMP 2010), we construct hitting sets for Combinatorial Shapes of size polynomial in the alphabet, dimension, and the inverse of the error parameter. This is optimal up to polynomial factors. The best previous hitting sets came from the Pseudorandom Generator construction of Gopalan et al., and in particular had size that was quasipolynomial in the inverse of the error parameter. Our construction builds on natural variants of the constructions of Linial et al. and Rabani and Shpilka. In the process, we construct fractional perfect hash families and hitting sets for combinatorial rectangles with stronger guarantees. These might be of independent interest.

Recommendations

• Optimal hitting sets for combinatorial shapes
• Maximum hitting of a set by compressed intersecting families
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Geometric hitting sets for disks: theory and practice
• Asymptotically Optimal Hitting Sets Against Polynomials
• A lower bound for the hitting set size for combinatorial rectangles and an application
• Dynamic Geometric Set Cover and Hitting Set
• Dynamic Geometric Set Cover and Hitting Set

Cited in

(6)

• A lower bound for the hitting set size for combinatorial rectangles and an application
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Optimal hitting sets for combinatorial shapes
• Asymptotically Optimal Hitting Sets Against Polynomials
• Efficient constructions of hitting sets for systems of linear functions
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Optimal Hitting Sets for Combinatorial Shapes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167414)