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

scientific article

Language	Label	Description	Also known as
English	Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition	scientific article

Statements

instance of

scholarly article

0 references

title

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

0 references

zbMATH Open document ID

1303.11022

0 references

DOI

10.1007/978-1-4614-6642-0_4

0 references

author

Khodakhast Bibak

0 references

published in

Springer Proceedings in Mathematics & Statistics

0 references

publication date

23 July 2013

0 references

full work available at URL

https://arxiv.org/abs/1108.3790

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

additive combinatorics

0 references

sumsets

0 references

sum products

0 references

randomness

0 references

computer science

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

0 references

Machine Learning: ECML 2004

0 references

Bilinear character sums and sum-product problems on elliptic curves

0 references

Q3424887

0 references

A Characterization of the (Natural) Graph Properties Testable with One-Sided Error

0 references

Every Monotone Graph Property Is Testable

0 references

A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity

0 references

A refinement of the Cameron-Erdős conjecture

0 references

Counting sum-free sets in abelian groups

0 references

Sums and products along sparse graphs

0 references

Deducing the multidimensional Szemerédi theorem from an infinitary removal lemma

0 references

Deducing the density Hales-Jewett theorem from an infinitary removal lemma

0 references

Testability and repair of hereditary hypergraph properties

0 references

Noise correlation bounds for uniform low degree functions

0 references

Projections, entropy and sumsets

0 references

Another sum-product estimate in finite fields

0 references

On the number of solutions of exponential congruences

0 references

Sum-Products Estimates with Several Sets and Applications

0 references

Extracting Randomness Using Few Independent Sources

0 references

2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction

0 references

Simulating independence

0 references

New bounds on cap sets

0 references

On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

0 references

Semantic Security for the Wiretap Channel

0 references

Affine dispersers from subspace polynomials

0 references

From affine to two-source extractors via approximate duality

0 references

Intersective polynomials and the polynomial Szemerédi theorem

0 references

A unified framework for testing linear‐invariant properties

0 references

Tight Lower Bounds for 2-query LCCs over Finite Fields

0 references

Pseudorandom Bits for Polynomials

0 references

The critical probability for random Voronoi percolation in the plane is 1/2

0 references

On triples in arithmetic progression

0 references

New bounds on exponential sums related to the Diffie-Hellman distributions

0 references

Estimates on exponential sums related to the Diffie-Hellman distributions

0 references

Estimation of certain exponential sums arising in complexity theory

0 references

MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS

0 references

Mordell’s exponential sum estimate revisited

0 references

On the construction of affine extractors

0 references

Some Arithmetical Applications of the Sum-Product Theorems in Finite Fields

0 references

Roth's theorem on progressions revisited

0 references

Expanders and dimensional expansion

0 references

Multilinear exponential sums in prime fields under optimal entropy condition on the sources

0 references

Q3613902

0 references

Sum-Product Theorems and Applications

0 references

Sum-product theorem and exponential sum estimates in residue classes with modulus involving few prime factors

0 references

A Gauss sum estimate in arbitrary finite fields

0 references

Sum-product theorems in algebraic number fields

0 references

New results on expanders

0 references

Uniform expansion bounds for Cayley graphs of $\text{SL}_2(\mathbb F_p)$.

0 references

On a variant of sum-product estimates and explicit exponential sum bounds in prime fields

0 references

Influences of variables and threshold intervals under group symmetries

0 references

Expansion in $\text{SL}_d(\mathbb Z/q\mathbb Z)$, $q$ arbitrary.

0 references

Monotone expansion

0 references

A sum-product estimate in finite fields, and applications

0 references

ESTIMATES FOR THE NUMBER OF SUMS AND PRODUCTS AND FOR EXPONENTIAL SUMS IN FIELDS OF PRIME ORDER

0 references

Sieving and expanders

0 references

Affine linear sieve, expanders, and sum-product

0 references

Explicit constructions of RIP matrices and related problems

0 references

On the Hidden Shifted Power Problem

0 references

On congruences with products of variables from short intervals and applications

0 references

Approximate groups. I The torsion-free nilpotent case

0 references

APPROXIMATE GROUPS, II: THE SOLVABLE LINEAR CASE

0 references

Suzuki groups as expanders.

0 references

Approximate subgroups of linear groups.

0 references

Sum-product estimates for rational functions

0 references

The restricted isometry property and its implications for compressed sensing

0 references

Decoding by Linear Programming

0 references

Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

0 references

Stable signal recovery from incomplete and inaccurate measurements

0 references

On the statistical properties of Diffie-Hellman distributions

0 references

Randomness conductors and constant-degree lossless expanders

0 references

A polynomial bound in Freiman's theorem.

0 references

A sum--product theorem in semi-simple commutative Banach algebras

0 references

A sum-product estimate in algebraic division algebras

0 references

On sum-product representation in $\mathbb Z_q$

0 references

Additive and Multiplicative Structure in Matrix Spaces

0 references

Sum-product theorems and incidence geometry

0 references

Points on curves in small boxes and applications

0 references

Pinned distance sets, $k$-simplices, Wolff's exponent in finite fields and sum-product estimates

0 references

Optimal Randomness Extraction from a Diffie-Hellman Element

0 references

Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

0 references

Concentration of points on two and three dimensional modular hyperbolas and applications

0 references

On the concentration of points of polynomial maps and applications

0 references

Isomorphism classes of elliptic curves over a finite field in some thin families

0 references

Bounds for graph regularity and removal lemmas

0 references

Combinatorial theorems in sparse random sets

0 references

Extremal results in sparse pseudorandom graphs

0 references

Generalized incidence theorems, homogeneous forms and sum-product estimates in finite fields

0 references

On sums and products in $\mathbb C[x]$

0 references

Q5431589

0 references

A probabilistic technique for finding almost-periods of convolutions

0 references

Computational Extractors and Pseudorandomness

0 references

Non-malleable extractors and symmetric key cryptography from weak secrets

0 references

On the size of Kakeya sets in finite fields

0 references

Towards dimension expanders over finite fields

0 references

Q3002825

0 references

Kakeya Sets, New Mergers, and Old Extractors

0 references

Extractors and rank extractors for polynomial sources

0 references

Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers

0 references

On the number of sums and products

0 references

An improved construction of progression-free sets

0 references

Q3041274

0 references

The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent

0 references

Some additive combinatorics problems in matrix rings

0 references

A new proof of the graph removal lemma

0 references

Q3215325

0 references

Inverse additive problems for Minkowski sumsets. I

0 references

Inverse additive problems for Minkowski sumsets. II

0 references

Hunting for sharp thresholds

0 references

A sharp threshold for random graphs with a monochromatic triangle in every edge coloring

0 references

Some doubly exponential sums over Zm

0 references

Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions

0 references

An ergodic Szemerédi theorem for commuting transformations

0 references

A density version of the Hales-Jewett theorem

0 references

Spectra of elements in the group ring of SU(2)

0 references

An Explicit Sum-Product Estimate in Fp

0 references

A quantified version of Bourgain's sum-product estimate in $\mathbb F_{p}$ for subsets of incomparable sizes

0 references

The sum-product estimate for large subsets of prime fields

0 references

Sums and products of sets and estimates of rational trigonometric sums in fields of prime order

0 references

On the size of the set $A(A + 1)$

0 references

Q3066502

0 references

Sums of powers of subsets of an arbitrary finite field

0 references

On additive properties of product sets in an arbitrary finite field

0 references

Property testing. Current research and surveys

0 references

Property testing and its connection to learning and approximation

0 references

Q4430610

0 references

Higher correlations of divisor sums related to primes III: small gaps between primes

0 references

A new proof of Szemerédi's theorem for arithmetic progressions of length four

0 references

A new proof of Szemerédi's theorem

0 references

Hypergraph regularity and the multidimensional Szemerédi theorem

0 references

Decompositions, approximate structure, transference, and the Hahn-Banach theorem

0 references

Linear forms and higher-degree uniformity for functions on $\mathbb F^n_p$

0 references

Linear forms and quadratic uniformity for functions on $\mathbb{Z}_{N}$

0 references

LINEAR FORMS AND QUADRATIC UNIFORMITY FOR FUNCTIONS ON

0 references

Q3997075

0 references

Q3416242

0 references

Freiman's theorem in an arbitrary abelian group

0 references

AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM

0 references

The primes contain arbitrarily long arithmetic progressions

0 references

Freiman's Theorem in Finite Fields via Extremal Set Theory

0 references

Q3613910

0 references

The distribution of polynomials over finite fields, with applications to the Gowers norms

0 references

An arithmetic regularity lemma, associated counting lemma, and applications

0 references

An equivalence between inverse sumset theorems and inverse conjectures for theU3norm

0 references

Linear equations in primes

0 references

Yet another proof of Szemeredi's theorem

0 references

AN INVERSE THEOREM FOR THE GOWERSU4-NORM

0 references

An inverse theorem for the Gowers $U^{s+1}[N]$-norm

0 references

A Note on Elkin’s Improvement of Behrend’s Construction

0 references

Better extractors for better codes?

0 references

Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes

0 references

The endpoint case of the Bennett-Carbery-Tao multilinear Kakeya conjecture

0 references

Algebraic methods in discrete analogs of the Kakeya problem

0 references

On the Erdős distinct distances problem in the plane

0 references

Regularity and Positional Games

0 references

An isoperimetric method in additive theory

0 references

Some additive applications of the isoperimetric approach

0 references

The isoperimetric method

0 references

On the structure of cubic and quartic polynomials

0 references

Optimal Testing of Multivariate Polynomials over Small Prime Fields

0 references

Sum-product Estimates in Finite Fields via Kloosterman Sums

0 references

Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdős-Falconer distance conjecture

0 references

Fourier analysis and expanding phenomena in finite fields

0 references

Correlation testing for affine invariant properties on F p n in the high error regime

0 references

Explicit constructions of extractors and expanders

0 references

Growth and generation in $\text{SL}_2(\mathbb{Z}/p\mathbb{Z})$.

0 references

Growth in $\mathrm{SL}_3(\mathbb Z/p\mathbb Z)$.

0 references

AN EXPLICIT INCIDENCE THEOREM IN

0 references

Expander graphs and their applications

0 references

Q5417607

0 references

Nonconventional ergodic averages and nilmanifolds

0 references

A point of view on Gowers uniformity norms

0 references

Stable group theory and approximate subgroups

0 references

On an application of Guth-Katz theorem

0 references

Collisions Are Not Incidental: A Compression Function Exploiting Discrete Geometry

0 references

Explicit incidence bounds over general finite fields

0 references

Extremal Combinatorics

0 references

Q3597148

0 references

2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness

0 references

Deterministic extractors for small-space sources

0 references

A slight improvement to Garaev's sum product estimate

0 references

Q3400049

0 references

New Extension of the Weil Bound for Character Sums with Applications to Coding

0 references

Q4878666

0 references

The Green-Tao Theorem on arithmetic progressions in the primes: an ergodic point of view

0 references

Q5490975

0 references

Q5431586

0 references

Poincaré recurrence and number theory: thirty years later

0 references

Arithmetic progressions in sets of fractional dimension

0 references

Green–Tao theorem in function fields

0 references

Character-free approach to progression-free sets

0 references

Slightly improved sum-product estimates in fields of prime order

0 references

An improved sum-product estimate for general finite fields

0 references

A sum-division estimate of reals

0 references

On subsets of $\mathbb F_q^n$ containing no $k$-term progressions

0 references

Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments

0 references

GOWERS UNIFORMITY NORM AND PSEUDORANDOM MEASURES OF THE PSEUDORANDOM BINARY SEQUENCES

0 references

Regularity partitions and the topology of graphons

0 references

Q3002801

0 references

Equivalence of polynomial conjectures in additive combinatorics

0 references

Q5302078

0 references

Pseudorandom Bit Generators That Fool Modular Sums

0 references

Encryption against storage-bounded adversaries from on-line strong extractors

0 references

Expander graphs in pure and applied mathematics

0 references

Entropy and set cardinality inequalities for partition-determined functions

0 references

Regularity lemmas for stable graphs

0 references

Linear correlations amongst numbers represented by positive definite binary quadratic forms

0 references

On subsets of finite Abelian groups with no 3-term arithmetic progressions

0 references

On data structures and asymmetric communication complexity

0 references

The counting lemma for regular k‐uniform hypergraphs

0 references

Q4889853

0 references

Q4895030

0 references

Generalized additive bases, König's lemma, and the Erdős--Turán conjecture

0 references

Q3078218

0 references

Sets of integers that do not contain long arithmetic progressions

0 references

On the Waring problem with Dickson polynomials in finite fields

0 references

On threshold properties of $k$-SAT: An additive viewpoint

0 references

An application of coding theory to estimating Davenport constants

0 references

A new proof of the density Hales-Jewett theorem

0 references

Arithmetic progressions in Salem-type subsets of the integers

0 references

Growth in finite simple groups of Lie type

0 references

Q3288185

0 references

Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources

0 references

On the Minkowski distances and products of sum sets

0 references

Q3549648

0 references

Regular Partitions of Hypergraphs: Regularity Lemmas

0 references

Regular Partitions of Hypergraphs: Counting Lemmas

0 references

Generalizations of the removal lemma

0 references

Q3060865

0 references

Regularity Lemma for k-uniform hypergraphs

0 references

Applications of the regularity lemma for uniform hypergraphs

0 references

lgorithmic and Analysis Techniques in Property Testing

0 references

Ramsey theory applications

0 references

On Certain Sets of Integers

0 references

Non-asymptotic theory of random matrices: extreme singular values

0 references

An Improved Sum–Product Inequality in Fields of Prime Order

0 references

Sumsets and entropy

0 references

Q4175585

0 references

Q3549650

0 references

Gowers Uniformity, Influence of Variables, and PCPs

0 references

Appendix to `Roth's theorem on progressions revisited' by J. Bourgain

0 references

On the Bogolyubov-Ruzsa lemma

0 references

On Roth's theorem on progressions

0 references

Near optimal bounds in Freiman's theorem

0 references

On Sumsets of Convex Sets

0 references

Roth's theorem in many variables

0 references

Q3416247

0 references

Q3152800

0 references

An Introduction to Randomness Extractors

0 references

Green's conjecture and testing linear-invariant properties

0 references

An extension of Bourgain and Garaev's sum-product estimates

0 references

On the sum product estimates and two variables expanders

0 references

Sum-product phenomenon in finite fields not of prime order

0 references

Algebraic methods in sum-product phenomena

0 references

Szemerédi's theorem and problems on arithmetic progressions

0 references

On a two-dimensional analogue of Szemerédi's theorem in Abelian groups

0 references

On the elliptic curve analogue of the sum-product problem

0 references

On the exponential sum-product problem

0 references

SUM–PRODUCT ESTIMATES AND MULTIPLICATIVE ORDERS OFγANDγ+γ−1IN FINITE FIELDS

0 references

Q5496111

0 references

On sum-sets and product-sets of complex numbers

0 references

ON THE NUMBER OF SUMS AND PRODUCTS

0 references

Incidences and the Spectra of Graphs

0 references

Bounding multiplicative energy by the sumset

0 references

Roth-type theorems in finite groups

0 references

An incidence theorem in higher dimensions

0 references

Sum-product estimates for well-conditioned matrices

0 references

On a question of Erdős and Moser

0 references

Decoding of Reed Solomon codes beyond the error-correction bound

0 references

Pseudorandom generators without the XOR lemma

0 references

Crossing Numbers and Hard Erdős Problems in Discrete Geometry

0 references

On sets of integers containing no four elements in arithmetic progression

0 references

On sets of integers containing k elements in arithmetic progression

0 references

Extremal problems in discrete geometry

0 references

Long arithmetic progressions in sum-sets and the number x-sum-free sets

0 references

Finite and infinite arithmetic progressions in sumsets

0 references

Long arithmetic progressions in sumsets: Thresholds and bounds

0 references

Q2756758

0 references

A quantitative ergodic theory proof of Szemerédi's theorem

0 references

A variant of the hypergraph removal lemma

0 references

Q5421714

0 references

The Gaussian primes contain arbitrarily shaped constellations

0 references

A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma

0 references

Product set estimates for non-commutative groups

0 references

Q3545513

0 references

The sum-product phenomenon in arbitrary rings

0 references

Freiman's theorem for solvable groups

0 references

Sumset and Inverse Sumset Theory for Shannon Entropy

0 references

Q4650219

0 references

Q5393666

0 references

RANDOM MATRICES: THE CIRCULAR LAW

0 references

From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices

0 references

Random matrices: Universality of local eigenvalue statistics up to the edge

0 references

The primes contain arbitrarily long polynomial progressions

0 references

The inverse conjecture for the Gowers norm over finite fields via the correspondence principle

0 references

Extractor Codes

0 references

Q3078217

0 references

Quadratic Goldreich-Levin Theorems

0 references

Constructing locally computable extractors and cryptosystems in the bounded-storage model

0 references

Q3096715

0 references

The Szemerédi-Trotter type theorem and the sum-product estimate in finite fields

0 references

Sum and shifted-product subsets of product-sets over finite rings

0 references

Q3002796

0 references

Q3509410

0 references

Sum-product estimates via directed expanders

0 references

Mapping incidences

0 references

Expanders that beat the eigenvalue bound: Explicit construction and applications

0 references

Q4250346

0 references

Affine extractors over prime fields

0 references

Simple extractors via constructions of cryptographic pseudo-random generators

0 references

Q4372786

0 references

Q3002782

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2840793