Randomness-efficient curve samplers

DOI10.1007/978-3-642-40328-6_40zbMATH Open1405.68437arXiv1309.1089OpenAlexW1883061115MaRDI QIDQ2851887FDOQ2851887

Authors: Zeyu Guo 

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Abstract: 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(logN+log(1/delta))$ random bits exist, where $N$ is the domain size and $delta$ is the confidence error. The question of explicitly constructing randomness-efficient curve samplers was first raised in cite{TU06} where they obtained curve samplers with near-optimal randomness complexity. We present an explicit construction of low-degree curve samplers with {em optimal} randomness complexity (up to a constant factor), sampling curves of degree $left(mlo{g}_q(1/delta)ight{)}^{O(1)}$ in $mathbb{F}_q^m$. Our construction is a delicate combination of several components, including extractor machinery, limited independence, iterated sampling, and list-recoverable codes.

Full work available at URL: https://arxiv.org/abs/1309.1089

Recommendations

• scientific article; zbMATH DE number 1097580
• scientific article; zbMATH DE number 1256745
• Extractors and lower bounds for locally samplable sources
• Extractors and lower bounds for locally samplable sources
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

Cited In (1)

• On the randomness complexity of efficient sampling

This page was built for publication: Randomness-efficient curve samplers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851887)