Optimal hitting sets for combinatorial shapes

DOI10.4086/TOC.2013.V009A013MaRDI QIDQ3191583zbMATH OpenOpenAlexFDO

Authors Aditya Bhaskara, Devendra Desai, Srinkath Srinivasan

Publication date 6 October 2014

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2013.v009a013

zbMATH Keywords

derandomizationexpandersexplicit constructionhitting setsperfect hashing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27)

Recommendations

• Optimal Hitting Sets for Combinatorial Shapes
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Pseudorandom generators for combinatorial shapes
• Asymptotically Optimal Hitting Sets Against Polynomials
• A lower bound for the hitting set size for combinatorial rectangles and an application

Cites work

• Storing a Sparse Table with 0 (1) Worst Case Access Time

Cited in

(5)

• 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
• Recursive methods for some problems in coding and random permutations

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 Q3191583)