Extensions to the method of multiplicities, with applications to Kakeya sets and mergers

DOI10.1137/100783704MaRDI QIDQ5408768zbMATH OpenOpenAlexFDO

Authors Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Publication date 11 April 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/59284

zbMATH Keywords

finite fieldspolynomial methodrandomness extractionlist-decoding

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) Finite geometry and special incidence structures (51E99)

Recommendations

• Kakeya sets, new mergers, and old extractors
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• An improved analysis of linear mergers
• Sharp density bounds on the finite field Kakeya problem
• Extractors with weak random seeds

Cited in

(39)

• Fast systematic encoding of multiplicity codes
• A discretized Severi-type theorem with applications to harmonic analysis
• On the Alon-Füredi bound
• scientific article; zbMATH DE number 7561729 (Why is no real title available?)
• Joints tightened
• Linear hashing with \(\ell_\infty\) guarantees and two-sided Kakeya bounds
• Conical Kakeya and Nikodym sets in finite fields
• New bounds on the density of lattice coverings
• Gröbner bases for increasing sequences
• On zeros of a polynomial in a finite grid
• An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
• The Kakeya conjecture on local fields of positive characteristic
• Multijoints and factorisation
• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
• Extractor Lower Bounds, Revisited
• Joints of varieties
• Polynomials that vanish to high order on most of the hypercube
• Unconditional UC-secure computation with (stronger-malicious) PUFs
• The resultant method in higher dimensions
• Proof of the Kakeya set conjecture over rings of integers modulo square-free \(N\)
• Furstenberg sets in finite fields: explaining and improving the Ellenberg-Erman proof
• Interactions of computational complexity theory and mathematics
• Quantified Derandomization: How to Find Water in the Ocean
• How to extract useful randomness from unreliable sources
• Bounding the Number of Common Zeros of Multivariate Polynomials and Their Consecutive Derivatives
• Zeros with multiplicity, Hasse derivatives and linear factors of general skew polynomials
• Contemporary coding theory. Abstracts from the workshop held March 17--23, 2019
• Ranks of matrices with few distinct entries
• Covering almost all the layers of the hypercube with multiplicities
• The spherical Kakeya problem in finite fields
• Joints formed by lines and a \(k\)-plane, and a discrete estimate of Kakeya type
• Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
• Kakeya sets, new mergers, and old extractors
• Sharp density bounds on the finite field Kakeya problem
• The constant of point-line incidence constructions
• Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
• scientific article; zbMATH DE number 5368669 (Why is no real title available?)
• New applications of the polynomial method: the cap set conjecture and beyond
• Probabilities of incidence between lines and a plane curve over finite fields

This page was built for publication: Extensions to the method of multiplicities, with applications to Kakeya sets and mergers

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