Buchumschlag

Constant Degree Direct Product Testers with Small Soundness

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bafna, Mitali, Lifshitz, Noam, Minzer, Dor
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Characterizing Direct Product Testing via Coboundary Expansion
von: Bafna, Mitali, et al.
Veröffentlicht: (2023)

Quasi-Linear Size PCPs with Small Soundness from HDX
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

An Invariance Principle for the Multi-slice, with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2021)

The Lens of Abelian Embeddings
von: Minzer, Dor
Veröffentlicht: (2026)

Constant Degree Networks for Almost-Everywhere Reliable Transmission
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable k-CSPs: IV
von: Bhangale, Amey, et al.
Veröffentlicht: (2023)

Product Mixing in Compact Lie Groups
von: Ellis, David, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

A Distance Amplification Lemma for Monotonicity
von: Minzer, Dor
Veröffentlicht: (2025)

Improved Round-by-round Soundness IOPs via Reed-Muller Codes
von: Minzer, Dor, et al.
Veröffentlicht: (2025)

Near Optimal Alphabet-Soundness Tradeoff PCPs
von: Minzer, Dor, et al.
Veröffentlicht: (2024)

A Dense Model Theorem for the Boolean Slice
von: Kalai, Gil, et al.
Veröffentlicht: (2024)

Isoperimetric Inequalities Made Simpler
von: Eldan, Ronen, et al.
Veröffentlicht: (2022)

Near Optimal Hardness of Approximating $k$-CSP
von: Minzer, Dor, et al.
Veröffentlicht: (2025)

On Approximability of Satisfiable k-CSPs: V
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Low-Degree Polynomials Are Good Extractors
von: Alrabiah, Omar, et al.
Veröffentlicht: (2024)

Direct Product Primality Testing of Graphs is GI-hard
von: Calderoni, Luca, et al.
Veröffentlicht: (2020)

The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients
von: First, Uriya A., et al.
Veröffentlicht: (2022)

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
von: Cheng, Kuan, et al.
Veröffentlicht: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

On the Structure of Hamiltonian Graphs with Small Independence Number
von: Jedličková, Nikola, et al.
Veröffentlicht: (2024)

A Note on the Complexity of Directed Clique
von: Gutowski, Grzegorz, et al.
Veröffentlicht: (2026)

Improved Small Set Expansion in High Dimensional Expanders
von: Kaufman, Tali, et al.
Veröffentlicht: (2025)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
von: Li, Xin, et al.
Veröffentlicht: (2024)

3-Query RLDCs are Strictly Stronger than 3-Query LDCs
von: Gur, Tom, et al.
Veröffentlicht: (2025)

Rounding Large Independent Sets on Expanders
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

A Simple Sub-Polynomial Degree Coboundary Expander
von: Hopkins, Max, et al.
Veröffentlicht: (2026)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
von: Li, Xin, et al.
Veröffentlicht: (2023)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
von: Hsieh, Jun-Ting, et al.
Veröffentlicht: (2024)

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
von: Chang, Fan, et al.
Veröffentlicht: (2025)

Communication Complexity of Disjointness under Product Distributions
von: Hunter, Zach, et al.
Veröffentlicht: (2026)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
von: Dikstein, Yotam, et al.
Veröffentlicht: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

A Subexponential Reduction from Product Partition to Subset Sum
von: Costandin, Marius
Veröffentlicht: (2024)

Constant congestion linkages in polynomially strong digraphs in polynomial time
von: Lopes, Raul, et al.
Veröffentlicht: (2024)

An Efficient Algorithm to Generate all Labeled Triangle-free Graphs with a given Graphical Degree Sequence
von: Wang, Kai
Veröffentlicht: (2026)

A General Framework for Low Soundness Homomorphism Testing
von: Mittal, Tushant, et al.
Veröffentlicht: (2025)