Explicit constructions of extractors and expanders

DOI10.4064/AA140-3-2MaRDI QIDQ3651118zbMATH OpenOpenAlexFDO

Authors Norbert Hegyvári, François Hennecart

Publication date 8 December 2009

Published in Acta Arithmetica (Search for Journal in Brave)

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

zbMATH Keywords

expanderexponetially distributed polynomialextractor

Mathematics Subject Classification ID

Arithmetic combinatorics; higher degree uniformity (11B30) Other combinatorial number theory (11B75) Estimates on exponential sums (11L07) Polynomials over finite fields (11T06) Combinatorics in computer science (68R05)

Abstract: We investigate 2-variable expanders and 3-source extractors in prime fields. We extend previous results of J. Bourgain.

Recommendations

• scientific article; zbMATH DE number 2156273
• scientific article; zbMATH DE number 1820017
• Extractor Lower Bounds, Revisited
• On the construction of affine extractors
• Explicit expanders of every degree and size
• The complexity of explicit constructions
• The complexity of explicit constructions
• Explicit two-source extractors and resilient functions

Cited in

(22)

• Moderate expanders over rings
• On thin sum-product bases
• Explicit expanders of every degree and size
• Distance sets over arbitrary finite fields
• Conditional expanding bounds for two-variable functions over prime fields
• On two-variable expanders over finite rings
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Combinatorial Nullstellensatz approach to polynomial expansion
• Conditional expanding bounds for two-variable functions over finite valuation rings
• Extraction in the Lambek-Grishin Calculus
• On point-line incidences in vector spaces over finite fields
• Incidences between planes over finite fields
• An explicit two-source extractor with min-entropy rate near $4/9$
• Explicit two-source extractors and resilient functions
• Distribution of residues in approximate subgroups of \(\mathbb F_p^*\)
• On four-variable expanders in finite fields
• On three-variable expanders over finite fields
• Extractor Lower Bounds, Revisited
• Some remarks on multilinear exponential sums with an application
• On monochromatic solutions of some nonlinear equations in \(\mathbb Z/p\mathbb Z\)
• The complexity of subcube partition relates to the additive structure of the support
• A note on the size of the set \(A^2+A\)

This page was built for publication: Explicit constructions of extractors and expanders

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