Copertina

An Invariance Principle for the Multi-slice, with Applications

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Braverman, Mark, Khot, Subhash, Lifshitz, Noam, Minzer, Dor
Natura:	Preprint
Pubblicazione:	2021
Soggetti:	Computational Complexity Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On Approximability of Satisfiable k-CSPs: IV
di: Bhangale, Amey, et al.
Pubblicazione: (2023)

Constant Degree Direct Product Testers with Small Soundness
di: Bafna, Mitali, et al.
Pubblicazione: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

The Lens of Abelian Embeddings
di: Minzer, Dor
Pubblicazione: (2026)

On Approximability of Satisfiable k-CSPs: V
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

Parallel Repetition for $3$-Player XOR Games
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
di: Bhangale, Amey, et al.
Pubblicazione: (2025)

Product Mixing in Compact Lie Groups
di: Ellis, David, et al.
Pubblicazione: (2024)

Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$
di: Bhangale, Amey, et al.
Pubblicazione: (2023)

A Distance Amplification Lemma for Monotonicity
di: Minzer, Dor
Pubblicazione: (2025)

A Dense Model Theorem for the Boolean Slice
di: Kalai, Gil, et al.
Pubblicazione: (2024)

Characterizing Direct Product Testing via Coboundary Expansion
di: Bafna, Mitali, et al.
Pubblicazione: (2023)

Isoperimetric Inequalities Made Simpler
di: Eldan, Ronen, et al.
Pubblicazione: (2022)

Near Optimal Hardness of Approximating $k$-CSP
di: Minzer, Dor, et al.
Pubblicazione: (2025)

Query complexity of Boolean functions on the middle slice of the cube
di: Gerbner, Dániel, et al.
Pubblicazione: (2023)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
di: S., Karthik C., et al.
Pubblicazione: (2021)

Biased Linearity Testing in the 1% Regime
di: Khot, Subhash, et al.
Pubblicazione: (2025)

Quasi-Linear Size PCPs with Small Soundness from HDX
di: Bafna, Mitali, et al.
Pubblicazione: (2024)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2025)

Improved Round-by-round Soundness IOPs via Reed-Muller Codes
di: Minzer, Dor, et al.
Pubblicazione: (2025)

Near Optimal Alphabet-Soundness Tradeoff PCPs
di: Minzer, Dor, et al.
Pubblicazione: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
di: Fei, Yumou, et al.
Pubblicazione: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2026)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
di: Gur, Tom, et al.
Pubblicazione: (2025)

Interactive Proofs For Distribution Testing With Conditional Oracles
di: Biswas, Ari, et al.
Pubblicazione: (2025)

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
di: Chang, Fan, et al.
Pubblicazione: (2025)

Low-Degree Polynomials Are Good Extractors
di: Alrabiah, Omar, et al.
Pubblicazione: (2024)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2025)

Refuting Perfect Matchings in Spectral Expanders is Hard
di: Biswas, Ari, et al.
Pubblicazione: (2025)

A Note on the Complexity of Directed Clique
di: Gutowski, Grzegorz, et al.
Pubblicazione: (2026)

Direct Product Primality Testing of Graphs is GI-hard
di: Calderoni, Luca, et al.
Pubblicazione: (2020)

Monotone Circuit Complexity of Matching
di: Cavalar, Bruno, et al.
Pubblicazione: (2025)

Hunting a rabbit: complexity, approximability and some characterizations
di: Ben-Ameur, Walid, et al.
Pubblicazione: (2025)

On the Keevash-Knox-Mycroft Conjecture
di: Gan, Luyining, et al.
Pubblicazione: (2022)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
di: Borzechowski, Michaela, et al.
Pubblicazione: (2023)

Sparse juntas on the biased hypercube
di: Dinur, Irit, et al.
Pubblicazione: (2017)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
di: Basu, Arpon, et al.
Pubblicazione: (2024)

Flat origami is Turing Complete
di: Hull, Thomas C., et al.
Pubblicazione: (2023)