DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.26

A Simple Sub-Polynomial Degree Coboundary Expander

Authors: Max Hopkins and Arka Ray

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

High dimensional expanders simultaneously satisfying spectral and combinatorial (coboundary) expansion have recently played a major role in breakthroughs in PCP and coding theory, but the only known construction of such complexes is extremely involved, requiring deep algebraic number theory. In this work, we give an extremely simple combinatorial construction of a sub-polynomial degree complex based on projections of the flags complex (subspace chains) that is (i) a local spectral expander, (ii) a coboundary expander, and (iii) a swap coboundary expander. As a corollary, we also give the first near-linear size combinatorial hypergraphs with good agreement tests in the `1%' regime, and a simple PCP construction with near-linear size.

Cite as

Max Hopkins and Arka Ray. A Simple Sub-Polynomial Degree Coboundary Expander. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 26:1-26:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hopkins_et_al:LIPIcs.CCC.2026.26,
  author =	{Hopkins, Max and Ray, Arka},
  title =	{{A Simple Sub-Polynomial Degree Coboundary Expander}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{26:1--26:41},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.26},
  URN =		{urn:nbn:de:0030-drops-270685},
  doi =		{10.4230/LIPIcs.CCC.2026.26},
  annote =	{Keywords: high dimensional expansders, agreement testing, probabilistically checkable proofs}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2024.30

Improved Linearly Ordered Colorings of Hypergraphs via SDP Rounding

Authors: Anand Louis, Alantha Newman, and Arka Ray

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract

We consider the problem of linearly ordered (LO) coloring of hypergraphs. A hypergraph has an LO coloring if there is a vertex coloring, using a set of ordered colors, so that (i) no edge is monochromatic, and (ii) each edge has a unique maximum color. It is an open question as to whether or not a 2-LO colorable 3-uniform hypergraph can be LO colored with 3 colors in polynomial time. Nakajima and Živný recently gave a polynomial-time algorithm to color such hypergraphs with Õ(n^{1/3}) colors and asked if SDP methods can be used directly to obtain improved bounds. Our main result is to show how to use SDP-based rounding methods to produce an LO coloring with Õ(n^{1/5}) colors for such hypergraphs. We show how to reduce the problem to cases with highly structured SDP solutions, which we call balanced hypergraphs. Then we discuss how to apply classic SDP-rounding tools in this case to obtain improved bounds.

Cite as

Anand Louis, Alantha Newman, and Arka Ray. Improved Linearly Ordered Colorings of Hypergraphs via SDP Rounding. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{louis_et_al:LIPIcs.FSTTCS.2024.30,
  author =	{Louis, Anand and Newman, Alantha and Ray, Arka},
  title =	{{Improved Linearly Ordered Colorings of Hypergraphs via SDP Rounding}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.30},
  URN =		{urn:nbn:de:0030-drops-222199},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.30},
  annote =	{Keywords: hypergraph coloring, SDP rounding, promise constraint satisfaction problems}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2024.33

Sparse Cuts in Hypergraphs from Random Walks on Simplicial Complexes

Authors: Anand Louis, Rameesh Paul, and Arka Ray

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract

There are a lot of recent works on generalizing the spectral theory of graphs and graph partitioning to k-uniform hypergraphs. There have been two broad directions toward this goal. One generalizes the notion of graph conductance to hypergraph conductance [Louis, Makarychev - TOC'16; Chan, Louis, Tang, Zhang - JACM'18]. In the second approach, one can view a hypergraph as a simplicial complex and study its various topological properties [Linial, Meshulam - Combinatorica'06; Meshulam, Wallach - RSA'09; Dotterrer, Kaufman, Wagner - SoCG'16; Parzanchevski, Rosenthal - RSA'17] and spectral properties [Kaufman, Mass - ITCS'17; Dinur, Kaufman - FOCS'17; Kaufman, Openheim - STOC'18; Oppenheim - DCG'18; Kaufman, Openheim - Combinatorica'20]. In this work, we attempt to bridge these two directions of study by relating the spectrum of up-down walks and swap walks on the simplicial complex, a downward closed set system, to hypergraph expansion. More precisely, we study the simplicial complex obtained by downward closing the given hypergraph and random walks between its levels X(l), i.e., the sets of cardinality l. In surprising contrast to random walks on graphs, we show that the spectral gap of swap walks and up-down walks between level m and l with 1 < m ⩽ l cannot be used to infer any bounds on hypergraph conductance. Moreover, we show that the spectral gap of swap walks between X(1) and X(k-1) cannot be used to infer any bounds on hypergraph conductance. In contrast, we give a Cheeger-like inequality relating the spectra of walks between level 1 and l for any l ⩽ k to hypergraph expansion. This is a surprising difference between swaps walks and up-down walks! Finally, we also give a construction to show that the well-studied notion of link expansion in simplicial complexes cannot be used to bound hypergraph expansion in a Cheeger-like manner.

Cite as

Anand Louis, Rameesh Paul, and Arka Ray. Sparse Cuts in Hypergraphs from Random Walks on Simplicial Complexes. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{louis_et_al:LIPIcs.SWAT.2024.33,
  author =	{Louis, Anand and Paul, Rameesh and Ray, Arka},
  title =	{{Sparse Cuts in Hypergraphs from Random Walks on Simplicial Complexes}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.33},
  URN =		{urn:nbn:de:0030-drops-200739},
  doi =		{10.4230/LIPIcs.SWAT.2024.33},
  annote =	{Keywords: Sparse Cuts, Random Walks, Link Expansion, Hypergraph Expansion, Simplicial Complexes, High Dimensional Expander, Threshold Rank}
}

Search Results

Documents authored by Ray, Arka

A Simple Sub-Polynomial Degree Coboundary Expander

Abstract

Cite as

Improved Linearly Ordered Colorings of Hypergraphs via SDP Rounding

Abstract

Cite as

Sparse Cuts in Hypergraphs from Random Walks on Simplicial Complexes

Abstract

Cite as

Thanks for your feedback!

Could not send message