Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition

DOI10.1007/978-1-4614-6642-0_4zbMath1303.11022arXiv1108.3790OpenAlexW1775468292MaRDI QIDQ2840793

Khodakhast Bibak

Publication date: 23 July 2013

Published in: Springer Proceedings in Mathematics & Statistics (Search for Journal in Brave)

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

zbMATH Keywords

sumsetscomputer sciencerandomnessadditive combinatoricssum products

Mathematics Subject Classification ID

Cryptography (94A60) Other combinatorial number theory (11B75) Additive bases, including sumsets (11B13) Arithmetic combinatorics; higher degree uniformity (11B30)

Related Items

Deletion correcting codes meet the Littlewood-Offord problem ⋮ An improved lower bound for finite additive 2-bases ⋮ Unnamed Item

Cites Work

• Combinatorial theorems in sparse random sets
• Equivalence of polynomial conjectures in additive combinatorics
• A point of view on Gowers uniformity norms
• Expansion in \(\text{SL}_d(\mathbb Z/q\mathbb Z)\), \(q\) arbitrary.
• Sum and shifted-product subsets of product-sets over finite rings
• Pinned distance sets, \(k\)-simplices, Wolff's exponent in finite fields and sum-product estimates
• A new proof of the density Hales-Jewett theorem
• An incidence theorem in higher dimensions
• Projections, entropy and sumsets
• Points on curves in small boxes and applications
• On the Erdős distinct distances problem in the plane
• Sets of integers that do not contain long arithmetic progressions
• Near optimal bounds in Freiman's theorem
• Estimation of certain exponential sums arising in complexity theory
• A probabilistic technique for finding almost-periods of convolutions
• The endpoint case of the Bennett-Carbery-Tao multilinear Kakeya conjecture
• Extractors and rank extractors for polynomial sources
• Deducing the multidimensional Szemerédi theorem from an infinitary removal lemma
• Linear forms and higher-degree uniformity for functions on \(\mathbb F^n_p\)
• Sum-product phenomenon in finite fields not of prime order
• An application of coding theory to estimating Davenport constants
• Explicit constructions of RIP matrices and related problems
• The inverse conjecture for the Gowers norm over finite fields via the correspondence principle
• Deducing the density Hales-Jewett theorem from an infinitary removal lemma
• A new proof of the graph removal lemma
• On Roth's theorem on progressions
• The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields
• Affine extractors over prime fields
• Towards dimension expanders over finite fields
• Arithmetic progressions in Salem-type subsets of the integers
• Suzuki groups as expanders.
• Sum-product theorem and exponential sum estimates in residue classes with modulus involving few prime factors
• Property testing. Current research and surveys
• Approximate subgroups of linear groups.
• Concentration of points on two and three dimensional modular hyperbolas and applications
• The primes contain arbitrarily long polynomial progressions
• Character-free approach to progression-free sets
• Extremal problems in discrete geometry
• On sum-sets and product-sets of complex numbers
• Bounding multiplicative energy by the sumset
• On the sum product estimates and two variables expanders
• Affine linear sieve, expanders, and sum-product
• On threshold properties of \(k\)-SAT: An additive viewpoint
• A variant of the hypergraph removal lemma
• A quantitative ergodic theory proof of Szemerédi's theorem
• On sum-product representation in \(\mathbb Z_q\)
• On the construction of affine extractors
• On the Minkowski distances and products of sum sets
• A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
• The restricted isometry property and its implications for compressed sensing
• Sum-product estimates via directed expanders
• Intersective polynomials and the polynomial Szemerédi theorem
• On the elliptic curve analogue of the sum-product problem
• Roth's theorem on progressions revisited
• Appendix to `Roth's theorem on progressions revisited' by J. Bourgain
• Some additive applications of the isoperimetric approach
• On the size of the set \(A(A + 1)\)
• On sums and products in \(\mathbb C[x\)]
• Linear equations in primes
• On subsets of \(\mathbb F_q^n\) containing no \(k\)-term progressions
• Generalizations of the removal lemma
• Multilinear exponential sums in prime fields under optimal entropy condition on the sources
• On the exponential sum-product problem
• A quantified version of Bourgain's sum-product estimate in \(\mathbb F_{p}\) for subsets of incomparable sizes
• Expanders and dimensional expansion
• On additive properties of product sets in an arbitrary finite field
• Arithmetic progressions in sets of fractional dimension
• Generalized incidence theorems, homogeneous forms and sum-product estimates in finite fields
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Expanders that beat the eigenvalue bound: Explicit construction and applications
• An ergodic Szemerédi theorem for commuting transformations
• Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions
• A new proof of Szemerédi's theorem for arithmetic progressions of length four
• On data structures and asymmetric communication complexity
• Spectra of elements in the group ring of SU(2)
• Decoding of Reed Solomon codes beyond the error-correction bound
• Influences of variables and threshold intervals under group symmetries
• Generalized additive bases, König's lemma, and the Erdős--Turán conjecture
• An improved construction of progression-free sets
• Algebraic methods in sum-product phenomena
• Sums and products along sparse graphs
• A density version of the Hales-Jewett theorem
• A polynomial bound in Freiman's theorem.
• New bounds on exponential sums related to the Diffie-Hellman distributions
• Encryption against storage-bounded adversaries from on-line strong extractors
• Constructing locally computable extractors and cryptosystems in the bounded-storage model
• A sum--product theorem in semi-simple commutative Banach algebras
• A sum-product estimate in finite fields, and applications
• On subsets of finite Abelian groups with no 3-term arithmetic progressions
• An isoperimetric method in additive theory
• On the concentration of points of polynomial maps and applications
• Bounds for graph regularity and removal lemmas
• Inverse additive problems for Minkowski sumsets. II
• Noise correlation bounds for uniform low degree functions
• On the Bogolyubov-Ruzsa lemma
• Inverse additive problems for Minkowski sumsets. I
• Random matrices: Universality of local eigenvalue statistics up to the edge
• Some additive combinatorics problems in matrix rings
• Algebraic methods in discrete analogs of the Kakeya problem
• On triples in arithmetic progression
• The sum-product estimate for large subsets of prime fields
• RANDOM MATRICES: THE CIRCULAR LAW
• An extension of Bourgain and Garaev's sum-product estimates
• Decoding by Linear Programming
• Extractor Codes
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Freiman's Theorem in Finite Fields via Extremal Set Theory
• The distribution of polynomials over finite fields, with applications to the Gowers norms
• The sum-product phenomenon in arbitrary rings
• An equivalence between inverse sumset theorems and inverse conjectures for theU³norm
• Randomness conductors and constant-degree lossless expanders
• Better extractors for better codes?
• Decompositions, approximate structure, transference, and the Hahn-Banach theorem
• On a variant of sum-product estimates and explicit exponential sum bounds in prime fields
• Incidences and the Spectra of Graphs
• Sumsets and entropy
• Every Monotone Graph Property Is Testable
• Optimal Randomness Extraction from a Diffie-Hellman Element
• Pseudorandom Bit Generators That Fool Modular Sums
• Sum-product estimates for well-conditioned matrices
• On a two-dimensional analogue of Szemerédi's theorem in Abelian groups
• Explicit constructions of extractors and expanders
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Regularity and Positional Games
• On sets of integers containing k elements in arithmetic progression
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• On the number of sums and products
• Sum-Products Estimates with Several Sets and Applications
• Mordell’s exponential sum estimate revisited
• Hunting for sharp thresholds
• Long arithmetic progressions in sum-sets and the number x-sum-free sets
• Some doubly exponential sums over Z_m
• Regularity Lemma for k-uniform hypergraphs
• Fourier analysis and expanding phenomena in finite fields
• On the Hidden Shifted Power Problem
• Sumset and Inverse Sumset Theory for Shannon Entropy
• A unified framework for testing linear‐invariant properties
• Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
• 2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness
• Affine dispersers from subspace polynomials
• Green's conjecture and testing linear-invariant properties
• Non-malleable extractors and symmetric key cryptography from weak secrets
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
• Gowers Uniformity, Influence of Variables, and PCPs
• lgorithmic and Analysis Techniques in Property Testing
• Freiman's theorem for solvable groups
• Additive and Multiplicative Structure in Matrix Spaces
• Freiman's theorem in an arbitrary abelian group
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
• Yet another proof of Szemeredi's theorem
• On the number of solutions of exponential congruences
• A refinement of the Cameron-Erdős conjecture
• Regularity lemmas for stable graphs
• Monotone expansion
• From affine to two-source extractors via approximate duality
• Correlation testing for affine invariant properties on F _p ⁿ in the high error regime
• Some Arithmetical Applications of the Sum-Product Theorems in Finite Fields
• Higher correlations of divisor sums related to primes III: small gaps between primes
• An Explicit Sum-Product Estimate in Fp
• Sum-product Estimates in Finite Fields via Kloosterman Sums
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Regular Partitions of Hypergraphs: Counting Lemmas
• AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM
• Machine Learning: ECML 2004
• ESTIMATES FOR THE NUMBER OF SUMS AND PRODUCTS AND FOR EXPONENTIAL SUMS IN FIELDS OF PRIME ORDER
• The counting lemma for regular k‐uniform hypergraphs
• Applications of the regularity lemma for uniform hypergraphs
• Stable signal recovery from incomplete and inaccurate measurements
• Optimal Testing of Multivariate Polynomials over Small Prime Fields
• Quadratic Goldreich-Levin Theorems
• Tight Lower Bounds for 2-query LCCs over Finite Fields
• New Extension of the Weil Bound for Character Sums with Applications to Coding
• On sets of integers containing no four elements in arithmetic progression
• ON THE NUMBER OF SUMS AND PRODUCTS
• Long arithmetic progressions in sumsets: Thresholds and bounds
• Extracting Randomness Using Few Independent Sources
• On Certain Sets of Integers
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• The isoperimetric method
• An inverse theorem for the Gowers \(U^{s+1}[N\)-norm]
• Deterministic extractors for small-space sources
• Simulating independence
• On the statistical properties of Diffie-Hellman distributions
• Pseudorandom generators without the XOR lemma
• A new proof of Szemerédi's theorem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Roth's theorem in many variables
• Counting sum-free sets in abelian groups
• Simple extractors via constructions of cryptographic pseudo-random generators
• Linear forms and quadratic uniformity for functions on \(\mathbb{Z}_{N}\)
• Product set estimates for non-commutative groups
• A sum-product estimate in algebraic division algebras
• Nonconventional ergodic averages and nilmanifolds
• The primes contain arbitrarily long arithmetic progressions
• Growth and generation in \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\).
• Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).
• On an application of Guth-Katz theorem
• Isomorphism classes of elliptic curves over a finite field in some thin families
• Growth in \(\mathrm{SL}_3(\mathbb Z/p\mathbb Z)\).
• Extremal results in sparse pseudorandom graphs
• On congruences with products of variables from short intervals and applications
• Another sum-product estimate in finite fields
• Sum-product theorems and incidence geometry
• The Gaussian primes contain arbitrarily shaped constellations
• Hypergraph regularity and the multidimensional Szemerédi theorem
• New results on expanders
• Finite and infinite arithmetic progressions in sumsets
• A Gauss sum estimate in arbitrary finite fields
• Sieving and expanders
• The critical probability for random Voronoi percolation in the plane is 1/2
• Roth-type theorems in finite groups
• On a question of Erdős and Moser
• Estimates on exponential sums related to the Diffie-Hellman distributions
• Ramsey theory applications
• Sum-product theorems in algebraic number fields
• On the structure of cubic and quartic polynomials
• New bounds on cap sets
• Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments
• Collisions Are Not Incidental: A Compression Function Exploiting Discrete Geometry
• Computational Extractors and Pseudorandomness
• SUM–PRODUCT ESTIMATES AND MULTIPLICATIVE ORDERS OFγANDγ+γ⁻¹IN FINITE FIELDS
• Linear correlations amongst numbers represented by positive definite binary quadratic forms
• Entropy and set cardinality inequalities for partition-determined functions
• An Improved Sum–Product Inequality in Fields of Prime Order
• Semantic Security for the Wiretap Channel
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• Sum-Product Theorems and Applications
• A Note on Elkin’s Improvement of Behrend’s Construction
• Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdős-Falconer distance conjecture
• Sums of powers of subsets of an arbitrary finite field
• An Introduction to Randomness Extractors
• Testability and repair of hereditary hypergraph properties
• On the size of Kakeya sets in finite fields
• Extremal Combinatorics
• Sums and products of sets and estimates of rational trigonometric sums in fields of prime order
• Pseudorandom Bits for Polynomials
• Approximate groups. I The torsion-free nilpotent case
• AN INVERSE THEOREM FOR THE GOWERSU⁴-NORM
• AN EXPLICIT INCIDENCE THEOREM IN
• An arithmetic regularity lemma, associated counting lemma, and applications
• Regularity partitions and the topology of graphons
• Green–Tao theorem in function fields
• Slightly improved sum-product estimates in fields of prime order
• LINEAR FORMS AND QUADRATIC UNIFORMITY FOR FUNCTIONS ON
• APPROXIMATE GROUPS, II: THE SOLVABLE LINEAR CASE
• Mapping incidences
• Kakeya Sets, New Mergers, and Old Extractors
• Poincaré recurrence and number theory: thirty years later
• Non-asymptotic theory of random matrices: extreme singular values
• On the Waring problem with Dickson polynomials in finite fields
• On Sumsets of Convex Sets
• Expander graphs in pure and applied mathematics
• Stable group theory and approximate subgroups
• Sum-product estimates for rational functions
• Property testing and its connection to learning and approximation
• GOWERS UNIFORMITY NORM AND PSEUDORANDOM MEASURES OF THE PSEUDORANDOM BINARY SEQUENCES
• Explicit incidence bounds over general finite fields
• An improved sum-product estimate for general finite fields
• The Green-Tao Theorem on arithmetic progressions in the primes: an ergodic point of view
• A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
• Bilinear character sums and sum-product problems on elliptic curves
• A sum-division estimate of reals
• Growth in finite simple groups of Lie type
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• A slight improvement to Garaev's sum product estimate
• Szemerédi's theorem and problems on arithmetic progressions
• Expander graphs and their applications