{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/53322"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/53322","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Kakeya sets and the method of multiplicities","abstract":"We extend the \"method of multiplicities\" to get the following results, of interest in combinatorics and randomness extraction. 1. We show that every Kakeya set (a set of points that contains a line in every direction) in F' must be of size at least qn/2n. This bound is tight to within a 2 + o(1) factor for every n as q -- oc, compared to previous bounds that were off by exponential factors in n. 2. We give improved randomness extractors and \"randomness mergers\". Mergers are seeded functions that take as input A (possibly correlated) random variables in {0, 1}N and a short random seed and output a single random variable in {0, 1}N that is statistically close to having entropy (1 - 6) - N when one of the A input variables is distributed uniformly. The seed we require is only (1/6) - log A-bits long, which significantly improves upon previous construction of mergers. 3. Using our new mergers, we show how to construct randomness extractors that use logarithmic length seeds while extracting 1- o(1) fraction of the min-entropy of the source. The \"method of multiplicities\", as used in prior work, analyzed subsets of vector spaces over finite fields by constructing somewhat low degree interpolating polynomials that vanish on every point in the subset with high multiplicity. The typical use of this method involved showing that the interpolating polynomial also vanished on some points outside the subset, and then used simple bounds on the number of zeroes to complete the analysis. Our augmentation to this technique is that we prove, under appropriate conditions, that the interpolating polynomial vanishes with high multiplicity outside the set. This novelty leads to significantly tighter analyses.","abstract_html":"We extend the "method of multiplicities" to get the following results, of interest in combinatorics and randomness extraction. 1. We show that every Kakeya set (a set of points that contains a line in every direction) in F' must be of size at least qn/2n. This bound is tight to within a 2 + o(1) factor for every n as q -- oc, compared to previous bounds that were off by exponential factors in n. 2. We give improved randomness extractors and "randomness mergers". Mergers are seeded functions that take as input A (possibly correlated) random variables in {0, 1}N and a short random seed and output a single random variable in {0, 1}N that is statistically close to having entropy (1 - 6) - N when one of the A input variables is distributed uniformly. The seed we require is only (1/6) - log A-bits long, which significantly improves upon previous construction of mergers. 3. Using our new mergers, we show how to construct randomness extractors that use logarithmic length seeds while extracting 1- o(1) fraction of the min-entropy of the source. The "method of multiplicities", as used in prior work, analyzed subsets of vector spaces over finite fields by constructing somewhat low degree interpolating polynomials that vanish on every point in the subset with high multiplicity. The typical use of this method involved showing that the interpolating polynomial also vanished on some points outside the subset, and then used simple bounds on the number of zeroes to complete the analysis. Our augmentation to this technique is that we prove, under appropriate conditions, that the interpolating polynomial vanishes with high multiplicity outside the set. This novelty leads to significantly tighter analyses.","abstract_has_math":false,"creators":["Saraf, Shubhangi"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Madhu Sudan."],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009","date_published":"2009","updated_at":"2026-07-22T22:21:18Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/53322","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Madhu Sudan."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Saraf, Shubhangi"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2010-03-25T15:31:14Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2010-03-25T15:31:14Z"]},{"key":"dc:date.issued","label":"Date","values":["2009"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/53322"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 51-53)."]},{"key":"dc:description.abstract","label":"Abstract","values":["We extend the \"method of multiplicities\" to get the following results, of interest in combinatorics and randomness extraction. 1. We show that every Kakeya set (a set of points that contains a line in every direction) in F' must be of size at least qn/2n. This bound is tight to within a 2 + o(1) factor for every n as q -- oc, compared to previous bounds that were off by exponential factors in n. 2. We give improved randomness extractors and \"randomness mergers\". Mergers are seeded functions that take as input A (possibly correlated) random variables in {0, 1}N and a short random seed and output a single random variable in {0, 1}N that is statistically close to having entropy (1 - 6) - N when one of the A input variables is distributed uniformly. The seed we require is only (1/6) - log A-bits long, which significantly improves upon previous construction of mergers. 3. Using our new mergers, we show how to construct randomness extractors that use logarithmic length seeds while extracting 1- o(1) fraction of the min-entropy of the source. The \"method of multiplicities\", as used in prior work, analyzed subsets of vector spaces over finite fields by constructing somewhat low degree interpolating polynomials that vanish on every point in the subset with high multiplicity. The typical use of this method involved showing that the interpolating polynomial also vanished on some points outside the subset, and then used simple bounds on the number of zeroes to complete the analysis. Our augmentation to this technique is that we prove, under appropriate conditions, that the interpolating polynomial vanishes with high multiplicity outside the set. This novelty leads to significantly tighter analyses."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Kakeya sets and the method of multiplicities"]}]}],"canonical_facts":{"dc:contributor.advisor":["Madhu Sudan."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Saraf, Shubhangi"],"dc:date.accessioned":["2010-03-25T15:31:14Z"],"dc:date.available":["2010-03-25T15:31:14Z"],"dc:date.issued":["2009"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 51-53)."],"dc:description.abstract":["We extend the \"method of multiplicities\" to get the following results, of interest in combinatorics and randomness extraction. 1. We show that every Kakeya set (a set of points that contains a line in every direction) in F' must be of size at least qn/2n. This bound is tight to within a 2 + o(1) factor for every n as q -- oc, compared to previous bounds that were off by exponential factors in n. 2. We give improved randomness extractors and \"randomness mergers\". Mergers are seeded functions that take as input A (possibly correlated) random variables in {0, 1}N and a short random seed and output a single random variable in {0, 1}N that is statistically close to having entropy (1 - 6) - N when one of the A input variables is distributed uniformly. The seed we require is only (1/6) - log A-bits long, which significantly improves upon previous construction of mergers. 3. Using our new mergers, we show how to construct randomness extractors that use logarithmic length seeds while extracting 1- o(1) fraction of the min-entropy of the source. The \"method of multiplicities\", as used in prior work, analyzed subsets of vector spaces over finite fields by constructing somewhat low degree interpolating polynomials that vanish on every point in the subset with high multiplicity. The typical use of this method involved showing that the interpolating polynomial also vanished on some points outside the subset, and then used simple bounds on the number of zeroes to complete the analysis. Our augmentation to this technique is that we prove, under appropriate conditions, that the interpolating polynomial vanishes with high multiplicity outside the set. This novelty leads to significantly tighter analyses."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/53322"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Kakeya sets and the method of multiplicities"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:18Z"}