Cover Image

The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients

Fuente: arXiv

Saved in:

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

Similar Items

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)

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

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

Improved Small Set Expansion in High Dimensional Expanders
by: Kaufman, Tali, et al.
Published: (2025)

Hypergraph Samplers: Typical and Worst Case Behavior
by: Alev, Vedat Levi, et al.
Published: (2026)

Good Locally Testable Codes with Small Alphabet and Small Query Size
by: First, Uriya, et al.
Published: (2025)

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

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

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

Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
by: Li, Yaqiao
Published: (2025)

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

Constant congestion linkages in polynomially strong digraphs in polynomial time
by: Lopes, Raul, et al.
Published: (2024)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
by: Collins, Nathaniel A., et al.
Published: (2024)

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

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

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

The Complexity Classes of Hamming Distance Recoverable Robust Problems
by: Grüne, Christoph
Published: (2022)

The geodesic cover problem for butterfly networks
by: Manuel, Paul, et al.
Published: (2022)

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

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

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

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

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)

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

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

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

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

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

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

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

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
by: Notarantonio, Hadrien, et al.
Published: (2023)

An Invariance Principle for the Multi-slice, with Applications
by: Braverman, Mark, et al.
Published: (2021)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

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

A Subexponential Reduction from Product Partition to Subset Sum
by: Costandin, Marius
Published: (2024)

Lions and Contamination: Trees and General Graphs
by: Kim, Dohoon, et al.
Published: (2026)

Representing Matroids over the Reals is $\exists \mathbb R$-complete
by: Kim, Eun Jung, et al.
Published: (2023)

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
by: Dikstein, Yotam, et al.
Published: (2023)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
by: Grüne, Christoph, et al.
Published: (2026)