Cover Image

Improved Small Set Expansion in High Dimensional Expanders

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kaufman, Tali, Mass, David
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Good $2$-Query Locally Testable Codes from Sheaves on High Dimensional Expanders
by: First, Uriya A., et al.
Published: (2022)

The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients
by: First, Uriya A., et al.
Published: (2022)

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
by: First, Uriya A., et al.
Published: (2024)

Sparse High Dimensional Expanders via Local Lifts
by: Yaacov, Inbar Ben, et al.
Published: (2024)

Coboundary expansion of coset complexes
by: Kaufman, Tali, et al.
Published: (2024)

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

Pseudorandomness of Expander Walks via Fourier Analysis on Groups
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

A Simple Sub-Polynomial Degree Coboundary Expander
by: Hopkins, Max, et al.
Published: (2026)

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes
by: Kopparty, Swastik, et al.
Published: (2023)

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
by: Mittal, Kunal
Published: (2025)

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

On the Structure of Hamiltonian Graphs with Small Independence Number
by: Jedličková, Nikola, et al.
Published: (2024)

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

Explicit Lossless Vertex Expanders
by: Hsieh, Jun-Ting, et al.
Published: (2025)

Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
by: Hsieh, Jun-Ting, et al.
Published: (2024)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
by: Li, Xin, et al.
Published: (2024)

Explicit Almost-Optimal $\varepsilon$-Balanced Codes via Free Expander Walks
by: Hsieh, Jun-Ting, et al.
Published: (2026)

Temporal Reachability Dominating Sets: contagion in temporal graphs
by: Kutner, David C., et al.
Published: (2023)

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

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

List Decoding Quotient Reed-Muller Codes
by: Gotlib, Omri, et al.
Published: (2025)

When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
by: Cheng, Kuan, et al.
Published: (2026)

Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
by: Yang, Chao, et al.
Published: (2024)

Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
by: Yang, Chao, et al.
Published: (2024)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
by: Yang, Chao, et al.
Published: (2024)

Translational Aperiodic Sets of 7 Polyominoes
by: Yang, Chao, et al.
Published: (2024)

On Detecting $H$-Induced Minors for Small $H$
by: Eagling-Vose, Tala, et al.
Published: (2026)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Algorithmic Cluster Expansions for Quantum Problems
by: Mann, Ryan L., et al.
Published: (2023)

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

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

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

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
by: Hodur, Nadzieja, et al.
Published: (2025)

A near-optimal Quadratic Goldreich-Levin algorithm
by: Briët, Jop, et al.
Published: (2025)

Assembly Addition Chains
by: Cronin, Leroy, et al.
Published: (2025)

Tensor rank and dimension expanders
by: Dvir, Zeev
Published: (2025)

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

Matchgate signatures under variable permutations
by: Meng, Boning, et al.
Published: (2025)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)