Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers

DOI10.1109/FOCS.2009.40zbMath1292.68119arXiv0901.2529MaRDI QIDQ5171174

Swastik Kopparty, Zeev Dvir, Madhu Sudan, Shubhangi Saraf

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items (26)

Zero-Fixing Extractors for Sub-Logarithmic Entropy ⋮ Deterministic Truncation of Linear Matroids ⋮ Local Correlation Breakers and Applications to Three-Source Extractors and Mergers ⋮ Finite Field Kakeya and Nikodym Sets in Three Dimensions ⋮ Explicit subspace designs ⋮ Alon's nullstellensatz for multisets ⋮ On the size of Kakeya sets in finite vector spaces ⋮ Kakeya sets in finite affine spaces ⋮ Weighted Reed-Muller codes revisited ⋮ Incidence bounds on multijoints and generic joints ⋮ Kakeya-type sets in finite vector spaces ⋮ Unnamed Item ⋮ An Introduction to Randomness Extractors ⋮ More results on the number of zeros of multiplicity at least \(r\) ⋮ The Kakeya problem: a gap in the spectrum and classification of the smallest examples ⋮ Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory ⋮ Unnamed Item ⋮ A note on large Kakeya sets ⋮ The small Kakeya sets in T2*(C), C a conic ⋮ A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density ⋮ Better short-seed quantum-proof extractors ⋮ Explicit two-source extractors and resilient functions ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ High-rate codes with sublinear-time decoding ⋮ Non-malleability against polynomial tampering ⋮ Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry

This page was built for publication: Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers