Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications

Eli Ben‐Sasson, Noga Ron‐Zewi, Madhur Tulsiani, Julia Wolf

Type: Book-Chapter

Publication Date: 2014-01-01

Citations: 3

DOI: https://doi.org/10.1007/978-3-662-43948-7_79

View Publication

Download PDF

Locations

Lecture notes in computer science - View
arXiv (Cornell University) - View - PDF
HAL (Le Centre pour la Communication Scientifique Directe) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	None	2017	Shachar Lovett
+ PDF Chat	Quadratic Goldreich--Levin Theorems	2014	Madhur Tulsiani Julia Wolf
+	Guest column	2009	Luca Trevisan
+	Structure and Randomness in Complexity Theory and Additive Combinatorics	2019	Seyed Kaave Hosseini
+	Pseudorandomness In Computer Science and In Additive Combinatorics	2010	Luca Trevisan
+	Additive Combinatorics and Theoretical Computer Science	2009	Luca Trevisan
+	A probabilistic technique for finding almost-periods of convolutions	2010	Ernie Croot Olof Sisask
+	A probabilistic technique for finding almost-periods of convolutions	2010	Ernie Croot Olof Sisask
+ PDF Chat	http://discreteanalysisjournal.com/article/2105-notes-on-nilspaces-algebraic-aspects	2018	Pablo Candela
+ PDF Chat	Key developments in algorithmic randomness	2020	Johanna N. Y. Franklin Christopher P. Porter
+ PDF Chat	Logarithmic bounds for Roth's theorem via almost-periodicity	2019	Thomas F. Bloom Olof Sisask
+	Deterministic Sparse Fourier Approximation via Fooling Arithmetic Progressions.	2010	Adi Akavia
+	Fooling intersections of low-weight halfspaces	2017	Rocco A. Servedio Li-Yang Tan
+ PDF Chat	A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds	2019	Kaave Hosseini Shachar Lovett
+	Cubic Goldreich-Levin	2022	Dain Kim Anqi Li Jonathan Tidor
+	Almost Optimal Pseudorandom Generators for Spherical Caps	2014	Pravesh K. Kothari Raghu Meka
+	Almost Optimal Pseudorandom Generators for Spherical Caps	2014	Pravesh K. Kothari Raghu Meka
+ PDF Chat	Almost Optimal Pseudorandom Generators for Spherical Caps	2015	Pravesh K. Kothari Raghu Meka
+ PDF Chat	Quasirandom arithmetic permutations	2005	Joshua Cooper
+	Quasirandom Arithmetic Permutations	2003	Joshua Cooper

Works That Cite This (2)

Action	Title	Year	Authors
+ PDF Chat	Finite field models in arithmetic combinatorics – ten years on	2014	Jason B. Wolf
+	Tight Chang's-lemma-type bounds for Boolean functions	2020	Sourav Chakraborty Nikhil S. Mande Rajat Mittal Tulasimohan Molli Manaswi Paraashar Swagato Sanyal

Works Cited by This (32)

Action	Title	Year	Authors
+ PDF Chat	AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM	2008	Ben Green Terence Tao
+	On arithmetic progressions in sums of sets of integers	2012	Jean Bourgain
+	From affine to two-source extractors via approximate duality	2011	Noga Ron‐Zewi Eli Ben‐Sasson
+	Arithmetic progressions in sumsets	2002	B. Green
+ PDF Chat	An Additive Combinatorics Approach Relating Rank to Communication Complexity	2012	Eli Ben‐Sasson Shachar Lovett Noga Ron‐Zewi
+	A polynomial bound in Freiman's theorem	2002	Mei-Chu Chang
+ PDF Chat	Additive structures in sumsets	2008	Tom Sanders
+	Finite field models in additive combinatorics	2005	Ben Green
+ PDF Chat	On the Bogolyubov–Ruzsa lemma	2012	Tom Sanders
+	On the structure of steps of three-term arithmetic progressions in a dense set of integers	2009	Pablo Candela