CaltechAUTHORS
  A Caltech Library Service

Better lossless condensers through derandomized curve samplers

Ta-Shma, Amnon and Umans, Christopher (2006) Better lossless condensers through derandomized curve samplers. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). IEEE , Piscataway, NJ, pp. 177-186. ISBN 0-7695-2720-5. https://resolver.caltech.edu/CaltechAUTHORS:20170427-151755097

[img] PDF - Published Version
See Usage Policy.

200Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170427-151755097

Abstract

Lossless condensers are unbalanced expander graphs, with expansion close to optimal. Equivalently, they may be viewed as functions that use a short random seed to map a source on n bits to a source on many fewer bits while preserving all of the min-entropy. It is known how to build lossless condensers when the graphs are slightly unbalanced in the work of M. Capalbo et al. (2002). The highly unbalanced case is also important but the only known construction does not condense the source well. We give explicit constructions of lossless condensers with condensing close to optimal, and using near-optimal seed length. Our main technical contribution is a randomness-efficient method for sampling FD (where F is a field) with low-degree curves. This problem was addressed before in the works of E. Ben-Sasson et al. (2003) and D. Moshkovitz and R. Raz (2006) but the solutions apply only to degree one curves, i.e., lines. Our technique is new and elegant. We use sub-sampling and obtain our curve samplers by composing a sequence of low-degree manifolds, starting with high-dimension, low-degree manifolds and proceeding through lower and lower dimension manifolds with (moderately) growing degrees, until we finish with dimension-one, low-degree manifolds, i.e., curves. The technique may be of independent interest.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://dx.doi.org/10.1109/FOCS.2006.18DOIArticle
http://ieeexplore.ieee.org/document/4031354/PublisherArticle
Additional Information:© 2006 IEEE. Supported by the Israel Science Foundation, by the Binational Science Foundation, and by the EU Integrated Project QAP. Supported by NSF Grant CCF-0346991, BSF Grant 2004329, and an Alfred P. Sloan Research Fellowship.
Funders:
Funding AgencyGrant Number
Israel Science FoundationUNSPECIFIED
European UnionUNSPECIFIED
NSFCCF-0346991
Binational Science Foundation (USA-Israel)2004329
Alfred P. Sloan FoundationUNSPECIFIED
Record Number:CaltechAUTHORS:20170427-151755097
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170427-151755097
Official Citation:A. Ta-Shma and C. Umans, "Better lossless condensers through derandomized curve samplers," 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), Berkeley, CA, 2006, pp. 177-186. doi: 10.1109/FOCS.2006.18
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:77025
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:27 Apr 2017 22:32
Last Modified:03 Oct 2019 17:52

Repository Staff Only: item control page