A Caltech Library Service

Randomness-Efficient Curve Sampling


Guo, Zeyu (2014) Randomness-Efficient Curve Sampling. Master's thesis, California Institute of Technology. doi:10.7907/N64Q-T997.


Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the sampled curve is still low-degree. This property is often used in combination with the sampling property and has found many applications, including PCP constructions, local decoding of codes, and algebraic PRG constructions.

The randomness complexity of curve samplers is a crucial parameter for its applications. It is known that (non-explicit) curve samplers using O(log N + log(1/δ)) random bits exist, where N is the domain size and δ is the confidence error. The question of explicitly constructing randomness-efficient curve samplers was first raised in [TU06] where they obtained curve samplers with near-optimal randomness complexity.

In this thesis, we present an explicit construction of low-degree curve samplers with optimal randomness complexity (up to a constant factor) that sample curves of degree (m logq(1/δ))O(1) in Fqm. Our construction is a delicate combination of several components, including extractor machinery, limited independence, iterated sampling, and list-recoverable codes.

Item Type:Thesis (Master's thesis)
Subject Keywords:pseudorandomness, extractor, explicit construction
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Umans, Christopher M.
Thesis Committee:
  • None, None
Defense Date:1 March 2014
Non-Caltech Author Email:gzy (AT)
Record Number:CaltechTHESIS:02242014-040043833
Persistent URL:
Guo, Zeyu0000-0001-7893-4346
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:8097
Deposited By: Zeyu Guo
Deposited On:24 Mar 2014 18:45
Last Modified:04 Oct 2019 00:03

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page