Image de couverture de livre

Fourier growth of structured $\mathbb{F}_2$-polynomials and applications

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Błasiok, Jarosław, Ivanov, Peter, Jin, Yaonan, Lee, Chin Ho, Servedio, Rocco A., Viola, Emanuele
Format:	Preprint
Publié:	2021
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Pseudorandomness, symmetry, smoothing: I
par: Derksen, Harm, et autres
Publié: (2024)

Pseudorandomness, symmetry, smoothing: II
par: Derksen, Harm, et autres
Publié: (2024)

Hardness of clique approximation for monotone circuits
par: Błasiok, Jarosław, et autres
Publié: (2025)

Pseudorandom bits for non-commutative programs
par: Lee, Chin Ho, et autres
Publié: (2025)

Boosting uniformity in quasirandom groups: fast and simple
par: Derksen, Harm, et autres
Publié: (2024)

Resilient functions: Optimized, simplified, and generalized
par: Ivanov, Peter, et autres
Publié: (2024)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
par: Błasiok, Jarosław, et autres
Publié: (2026)

Forrelation is Extremally Hard
par: Girish, Uma, et autres
Publié: (2025)

Testing noisy low-degree polynomials for sparsity
par: Bao, Yiqiao, et autres
Publié: (2025)

Communication complexity of pointer chasing via the fixed-set lemma
par: Viola, Emanuele
Publié: (2025)

Learning Functions of Halfspaces
par: Alman, Josh, et autres
Publié: (2026)

Detecting Low-Degree Truncation
par: De, Anindya, et autres
Publié: (2024)

DNF formulas are efficiently testable with relative error
par: Chen, Xi, et autres
Publié: (2026)

Testing Convex Truncation
par: De, Anindya, et autres
Publié: (2023)

Condensing and Extracting Against Online Adversaries
par: Chattopadhyay, Eshan, et autres
Publié: (2024)

Relative-error testing of conjunctions and decision lists
par: Chen, Xi, et autres
Publié: (2025)

Is nasty noise actually harder than malicious noise?
par: Blanc, Guy, et autres
Publié: (2025)

Testing Juntas and Junta Subclasses with Relative Error
par: Chen, Xi, et autres
Publié: (2025)

Lower Bounds for Convexity Testing
par: Chen, Xi, et autres
Publié: (2024)

Testing Sumsets is Hard
par: Chen, Xi, et autres
Publié: (2024)

Sublinear-query relative-error testing of halfspaces
par: Chen, Xi, et autres
Publié: (2026)

Halfspaces are hard to test with relative error
par: Chen, Xi, et autres
Publié: (2025)

Sparsifying Suprema of Gaussian Processes
par: De, Anindya, et autres
Publié: (2024)

Extractors for Polynomial Sources over $\mathbb{F}_2$
par: Chattopadhyay, Eshan, et autres
Publié: (2023)

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
par: Chattopadhyay, Eshan, et autres
Publié: (2025)

Relative-error unateness testing
par: Chen, Xi, et autres
Publié: (2025)

Model-agnostic super-resolution in high dimensions
par: Chen, Xi, et autres
Publié: (2025)

Some structural complexity results for $\exists\mathbb R$
par: Meer, Klaus, et autres
Publié: (2025)

Relative-error monotonicity testing
par: Chen, Xi, et autres
Publié: (2024)

Are Depth-2 Regular Expressions Hard to Intersect?
par: Ascone, Rocco, et autres
Publié: (2025)

A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
par: Ivanov, Sergiu, et autres
Publié: (2024)

Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$
par: Çivril, Ali
Publié: (2021)

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
par: Baraskar, Omkar, et autres
Publié: (2024)

Boolean PCSPs through the lens of Fourier Analysis
par: Banakh, Demian, et autres
Publié: (2026)

Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
par: Binnendyk, Eric
Publié: (2025)

Classification of polynomial models without 2-jet determination in $\mathbb{C}^3$
par: Liczman, Petr, et autres
Publié: (2025)

A Lower Bound on the Constant in the Fourier Min-Entropy/Influence Conjecture
par: Biswas, Aniruddha, et autres
Publié: (2022)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
par: Anand, Kartik, et autres
Publié: (2025)

Revealing the canalizing structure of Boolean functions: Algorithms and applications
par: Dimitrova, Elena, et autres
Publié: (2021)

Constant-depth circuits for polynomial GCD over any characteristic
par: Bhattacharjee, Somnath, et autres
Publié: (2025)