column

Guest column: from randomness extraction to rotating needles

Author:

Z. DvirAuthors Info & Claims

ACM SIGACT News, Volume 40, Issue 4

Pages 46 - 61

https://doi.org/10.1145/1711475.1711487

Published: 25 January 2010 Publication History

Abstract

The finite field Kakeya problem deals with the way lines in different directions can overlap in a vector space over a finite field. This problem came up in the study of certain Euclidean problems and, independently, in the search for explicit randomness extractors. We survey recent progress on this problem and describe several of its applications.

References

[1]

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501--555, 1998.

Digital Library

[2]

S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. J. ACM, 45(1):70--122, 1998.

Digital Library

[3]

J. Bennett, A. Carbery, and T. Tao. On the multilinear restriction and Kakeya conjectures. Acta Mathematica, 196:261--302, 2006.

[4]

A. Besicovitch. On Kakeya's problem and a similar one. Mathematische Zeitschrift, (27):312--320, 1928.

[5]

L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Complexity Theory, 3:307--318, 1993.

Digital Library

[6]

J. Bourgain, N. Katz, and T. Tao. A sum-product estimate in finite fields, and applications. Geom. Funct. Anal., 14(1):27--57, 2004.

[7]

J. Bourgain. On the dimension of Kakeya sets and related maximal inequalities. Geom. Funct. Anal., 9(2):256--282, 1999.

[8]

J. Bourgain. Harmonic analysis and combinatorics: How much may they contribute to each other? IMU/Amer. Math. Soc., pages 13--32, 2000.

[9]

Z. Dvir, S. Kopparty, S. Saraf, andM. Sudan. Extensions to the method of multiplicities, with applications to kakeya sets and mergers. In FOCS 09 (to appear), 2009.

Digital Library

[10]

Z. Dvir and A. Shpilka. An improved analysis of linear mergers. Comput. Complex., 16(1):34--59, 2007. (Extended abstract appeared in RANDOM 2005).

Digital Library

[11]

Z. Dvir. On the size of Kakeya sets in finite fields. J. AMS (to appear), 2008.

[12]

Z. Dvir and A. Wigderson. Kakeya sets, new mergers and old extractors. In FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 625--633, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[13]

G. Elekes, H. Kaplan, and M. Sharir. On lines, joints, and incidences in three dimensions, 2009. Manuscript.

[14]

J. Ellenberg, R. Oberlin, and T. Tao. The Kakeya set and maximal conjectures for algebraic varieties over finite fields, 2009. Manuscript.

[15]

S. Feldman and M. Sharir. An improved bound for joints in arrangements of lines in space. Discrete Comput. Geom., 33(2):307--320, 2005.

Digital Library

[16]

L. Guth and N. H. Katz. Algebraic methods in discrete analogs of the Kakeya problem, 2008. Manuscript.

[17]

V. Guruswami and A. Rudra. Explicit codes achieving list decoding capacity: Errorcorrection with optimal redundancy. IEEE Transactions on Information Theory, 54(1):135--150, 2008.

Digital Library

[18]

M. Gromov. Isoperimetry of waists and concentration of maps. Geom. Funct. Anal.,

[19]

V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraicgeometry codes. IEEE Transactions on Information Theory, 45(6):1757--1767, 1999.

Digital Library

[20]

L. Guth. The endpoint case of the Bennett-Carbery-Tao multilinear Kakeya conjecture, 2008. Manuscript.

[21]

V. Guruswami, C. Umans, and S. Vadhan. Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes. J. ACM, 56(4):1--34, 2009.

Digital Library

[22]

H. Kaplan, M. Sharir, and E. Shustin. On lines and joints, 2009. Manuscript.

[23]

N. Katz and T. Tao. New bounds for Kakeya problems. Journal d'Analyse de Jerusalem, 87:231--263, 2002.

[24]

R. Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, pages 216--226. Springer-Verlag, 1979.

Digital Library

Cited By

Bibak K(2013)Additive Combinatorics: With a View Towards Computer Science and Cryptography—An ExpositionNumber Theory and Related Fields10.1007/978-1-4614-6642-0_4(99-128)Online publication date: 5-Apr-2013
https://doi.org/10.1007/978-1-4614-6642-0_4
Chen XKayal NWigderson A(2011)Partial Derivatives in Arithmetic Complexity and BeyondFoundations and Trends® in Theoretical Computer Science10.1561/04000000436:1—2(1-138)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1561/0400000043

Recommendations

Guest Column: A Recipe for Constructing Two-Source Extractors

Randomness is a valuable resource in computation. Randomness is used to run various Monte Carlo simulations of complex systems such as the stock market or weather prediction systems. Various randomized algorithms have been discovered that often vastly ...
Pseudo-Random Pattern Generator Design for Column-Matching BIST
DSD '07: Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools

This paper discusses possibilities for a choice of a pseudorandom pattern generator that is to be used in combination with the column-matching based built-in self-test design method. The pattern generator should be as small as possible, whereas patterns ...
Scaling Matrices to Prescribed Row and Column Maxima

A nonnegative symmetric matrix $B$ has row maxima prescribed by a given vector $r$, if for each index $i$, the maximum entry in the $i$th row of $B$ equals $r_i$. This paper presents necessary and sufficient conditions so that for a given nonnegative ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGACT News

ACM SIGACT News Volume 40, Issue 4

December 2009

152 pages

ISSN:0163-5700

DOI:10.1145/1711475

Issue’s Table of Contents

Copyright © 2010 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 January 2010

Published in SIGACT Volume 40, Issue 4

Check for updates

Qualifiers

Column

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
118
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bibak K(2013)Additive Combinatorics: With a View Towards Computer Science and Cryptography—An ExpositionNumber Theory and Related Fields10.1007/978-1-4614-6642-0_4(99-128)Online publication date: 5-Apr-2013
https://doi.org/10.1007/978-1-4614-6642-0_4
Chen XKayal NWigderson A(2011)Partial Derivatives in Arithmetic Complexity and BeyondFoundations and Trends® in Theoretical Computer Science10.1561/04000000436:1—2(1-138)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1561/0400000043

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents