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

DOI10.1137/100783704zbMATH Open1285.68116OpenAlexW2150616341MaRDI QIDQ5408768FDOQ5408768

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

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

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)

Cited In (39)

• A discretized Severi-type theorem with applications to harmonic analysis
• Joints tightened
• Title not available (Why is that?)
• On the Alon-Füredi bound
• Linear hashing with \(\ell_\infty\) guarantees and two-sided Kakeya bounds
• New bounds on the density of lattice coverings
• Conical Kakeya and Nikodym sets in finite fields
• 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
• Extractor Lower Bounds, Revisited
• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
• 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
• Ranks of matrices with few distinct entries
• Contemporary coding theory. Abstracts from the workshop held March 17--23, 2019
• 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
• Sharp density bounds on the finite field Kakeya problem
• The constant of point-line incidence constructions
• Kakeya sets, new mergers, and old extractors
• Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
• Title not available (Why is that?)
• New applications of the polynomial method: the cap set conjecture and beyond
• Probabilities of incidence between lines and a plane curve over finite fields
• Fast systematic encoding of multiplicity codes

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)