Tight Chang's-lemma-type bounds for Boolean functions

Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, Swagato Sanyal

Type: Preprint

Publication Date: 2020-01-01

Citations: 1

DOI: https://doi.org/10.48550/arxiv.2012.02335

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Tight Chang's-Lemma-Type Bounds for Boolean Functions.	2020	Sourav Chakraborty Nikhil S. Mande Rajat Mittal Tulasimohan Molli Manaswi Paraashar Swagato Sanyal
+ PDF Chat	On Fourier analysis of sparse Boolean functions over certain Abelian groups	2024	Sourav Chakraborty Swarnalipa Datta Pranjal Dutta Arijit Ghosh Swagato Sanyal
+	Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity	2014	Swagato Sanyal
+	Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity	2014	Swagato Sanyal
+	Fourier sparsity, spectral norm, and the Log-rank conjecture	2013	Hing Yin Tsang Chung Hoi Wong Ning Xie Shengyu Zhang
+ PDF Chat	Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture	2013	Hing Yin Tsang Chung Hoi Wong Ning Xie Shengyu Zhang
+	Refuting approaches to the log-rank conjecture for XOR functions	2023	Hamed Hatami Kaave Hosseini Shachar Lovett Anthony Ostuni
+	Analysis of Boolean Functions	2014	Ryan O’Donnell
+	Analysis of Boolean Functions	2021	Ryan O’Donnell
+ PDF Chat	A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry	2016	Anindya De Ilias Diakonikolas Rocco A. Servedio
+ PDF Chat	A Generalization of a Theorem of Rothschild and van Lint	2021	Ning Xie Shuai Xu Yekun Xu
+	A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry	2012	Anindya De Ilias Diakonikolas Rocco A. Servedio
+ PDF Chat	Analysis of Boolean Functions	2014	Ryan O’Donnell
+ PDF Chat	Boolean Functions with Small Approximate Spectral Norm	2024	Tsun-Ming Cheung Hamed Hatami Ruidong Zhao Itai Zilberstein
+	Improved Bounds on Fourier Entropy and Min-Entropy	2020	Srinivasan Arunachalam Sourav Chakraborty Michal Koucký Nitin Saurabh Ronald de Wolf
+	Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity	2015	Swagato Sanyal
+	The List-Decoding Size of Fourier-Sparse Boolean Functions	2015	Ishay Haviv Oded Regev
+	The List-Decoding Size of Fourier-Sparse Boolean Functions	2015	Ishay Haviv Oded Regev
+	Improved bounds on Fourier entropy and Min-entropy.	2018	Srinivasan Arunachalam Sourav Chakraborty Michal Koucký Nitin Saurabh Ronald de Wolf
+ PDF Chat	Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)	2019	Ilias Diakonikolas Daniel M. Kane

Works That Cite This (2)

Action	Title	Year	Authors
+	Fourier growth of structured $\mathbb{F}_2$-polynomials and applications	2021	Jarosław Błasiok Peter Ivanov Yaonan Jin Chin Ho Lee Rocco A. Servedio Emanuele Viola
+ PDF Chat	Two new results about quantum exact learning	2021	Srinivasan Arunachalam Sourav Chakraborty Troy Lee Manaswi Paraashar Ronald de Wolf

Works Cited by This (17)

Action	Title	Year	Authors
+	Arithmetic progressions in sumsets	2002	B. Green
+	A polynomial bound in Freiman's theorem	2002	Mei-Chu Chang
+ PDF Chat	Additive structures in sumsets	2008	Tom Sanders
+ PDF Chat	Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture	2013	Hing Yin Tsang Chung Hoi Wong Ning Xie Shengyu Zhang
+	Some Constructions in the Inverse Spectral Theory of Cyclic Groups	2003	Ben Green
+ PDF Chat	An Entropic Proof of Chang's Inequality	2014	Russell Impagliazzo Cristopher Moore Alexander Russell
+ PDF Chat	Freiman's theorem in an arbitrary abelian group	2007	Ben Green Imre Z. Ruzsa
+	Testing Booleanity and the Uncertainty Principle	2013	Tom Gur Omer Tamuz
+ PDF Chat	Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications	2014	Eli Ben‐Sasson Noga Ron‐Zewi Madhur Tulsiani Julia Wolf
+ PDF Chat	Chvátal's conjecture and correlation inequalities	2017	Ehud Friedgut Jeff Kahn Gil Kalai Nathan Keller