Search Results

Documents authored by Dikstein, Yotam

Document
DOI: 10.4230/LIPIcs.CCC.2025.7
Sparser Abelian High Dimensional Expanders

Authors: Yotam Dikstein, Siqi Liu, and Avi Wigderson

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
The focus of this paper is the development of new elementary techniques for the construction and analysis of high dimensional expanders. Specifically, we present two new explicit constructions of Cayley high dimensional expanders (HDXs) over the abelian group 𝔽₂ⁿ. Our expansion proofs use only linear algebra and combinatorial arguments. The first construction gives local spectral HDXs of any constant dimension and subpolynomial degree exp(n^ε) for every ε > 0, improving on a construction by Golowich [Golowich, 2023] which achieves ε = 1/2. [Golowich, 2023] derives these HDXs by sparsifying the complete Grassmann poset of subspaces. The novelty in our construction is the ability to sparsify any expanding Grassmann posets, leading to iterated sparsification and much smaller degrees. The sparse Grassmannian (which is of independent interest in the theory of HDXs) serves as the generating set of the Cayley graph. Our second construction gives a 2-dimensional HDX of any polynomial degree exp(ε n) for any constant ε > 0, which is simultaneously a spectral expander and a coboundary expander. To the best of our knowledge, this is the first such non-trivial construction. We name it the Johnson complex, as it is derived from the classical Johnson scheme, whose vertices serve as the generating set of this Cayley graph. This construction may be viewed as a derandomization of the recent random geometric complexes of [Liu et al., 2023]. Establishing coboundary expansion through Gromov’s "cone method" and the associated isoperimetric inequalities is the most intricate aspect of this construction. While these two constructions are quite different, we show that they both share a common structure, resembling the intersection patterns of vectors in the Hadamard code. We propose a general framework of such "Hadamard-like" constructions in the hope that it will yield new HDXs.
Cite as

Yotam Dikstein, Siqi Liu, and Avi Wigderson. Sparser Abelian High Dimensional Expanders. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 7:1-7:98, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dikstein_et_al:LIPIcs.CCC.2025.7,
  author =	{Dikstein, Yotam and Liu, Siqi and Wigderson, Avi},
  title =	{{Sparser Abelian High Dimensional Expanders}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{7:1--7:98},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.7},
  URN =		{urn:nbn:de:0030-drops-237013},
  doi =		{10.4230/LIPIcs.CCC.2025.7},
  annote =	{Keywords: Local spectral expander, coboundary expander, Grassmannian expander}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.62
Coboundary and Cosystolic Expansion Without Dependence on Dimension or Degree

Authors: Yotam Dikstein and Irit Dinur

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
We give new bounds on the cosystolic expansion constants of several families of high dimensional expanders, and the known coboundary expansion constants of order complexes of homogeneous geometric lattices, including the spherical building of SL_n(𝔽_q). The improvement applies to the high dimensional expanders constructed by Lubotzky, Samuels and Vishne, and by Kaufman and Oppenheim. Our new expansion constants do not depend on the degree of the complex nor on its dimension, nor on the group of coefficients. This implies improved bounds on Gromov’s topological overlap constant, and on Dinur and Meshulam’s cover stability, which may have applications for agreement testing. In comparison, existing bounds decay exponentially with the ambient dimension (for spherical buildings) and in addition decay linearly with the degree (for all known bounded-degree high dimensional expanders). Our results are based on several new techniques: - We develop a new "color-restriction" technique which enables proving dimension-free expansion by restricting a multi-partite complex to small random subsets of its color classes. - We give a new "spectral" proof for Evra and Kaufman’s local-to-global theorem, deriving better bounds and getting rid of the dependence on the degree. This theorem bounds the cosystolic expansion of a complex using coboundary expansion and spectral expansion of the links. - We derive absolute bounds on the coboundary expansion of the spherical building (and any order complex of a homogeneous geometric lattice) by constructing a novel family of very short cones.
Cite as

Yotam Dikstein and Irit Dinur. Coboundary and Cosystolic Expansion Without Dependence on Dimension or Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 62:1-62:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dikstein_et_al:LIPIcs.APPROX/RANDOM.2024.62,
  author =	{Dikstein, Yotam and Dinur, Irit},
  title =	{{Coboundary and Cosystolic Expansion Without Dependence on Dimension or Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{62:1--62:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.62},
  URN =		{urn:nbn:de:0030-drops-210556},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.62},
  annote =	{Keywords: High Dimensional Expanders, HDX, Spectral Expansion, Coboundary Expansion, Cocycle Expansion, Cosystolic Expansion}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.68
Sparse High Dimensional Expanders via Local Lifts

Authors: Inbar Ben Yaacov, Yotam Dikstein, and Gal Maor

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
High dimensional expanders (HDXs) are a hypergraph generalization of expander graphs. They are extensively studied in the math and TCS communities due to their many applications. Like expander graphs, HDXs are especially interesting for applications when they are bounded degree, namely, if the number of edges adjacent to every vertex is bounded. However, only a handful of constructions are known to have this property, all of which rely on algebraic techniques. In particular, no random or combinatorial construction of bounded degree high dimensional expanders is known. As a result, our understanding of these objects is limited. The degree of an i-face in an HDX is the number of (i+1)-faces that contain it. In this work we construct complexes whose higher dimensional faces have bounded degree. This is done by giving an elementary and deterministic algorithm that takes as input a regular k-dimensional HDX X and outputs another regular k-dimensional HDX X̂ with twice as many vertices. While the degree of vertices in X̂ grows, the degree of the (k-1)-faces in X̂ stays the same. As a result, we obtain a new "algebra-free" construction of HDXs whose (k-1)-face degree is bounded. Our construction algorithm is based on a simple and natural generalization of the expander graph construction by Bilu and Linial [Yehonatan Bilu and Nathan Linial, 2006], which build expander graphs using lifts coming from edge signings. Our construction is based on local lifts of high dimensional expanders, where a local lift is a new complex whose top-level links are lifts of the links of the original complex. We demonstrate that a local lift of an HDX is also an HDX in many cases. In addition, combining local lifts with existing bounded degree constructions creates new families of bounded degree HDXs with significantly different links than before. For every large enough D, we use this technique to construct families of bounded degree HDXs with links that have diameter ≥ D.
Cite as

Inbar Ben Yaacov, Yotam Dikstein, and Gal Maor. Sparse High Dimensional Expanders via Local Lifts. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 68:1-68:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{benyaacov_et_al:LIPIcs.APPROX/RANDOM.2024.68,
  author =	{Ben Yaacov, Inbar and Dikstein, Yotam and Maor, Gal},
  title =	{{Sparse High Dimensional Expanders via Local Lifts}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{68:1--68:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.68},
  URN =		{urn:nbn:de:0030-drops-210612},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.68},
  annote =	{Keywords: High Dimensional Expanders, HDX, Spectral Expansion, Lifts, Covers, Explicit Constructions, Randomized Constructions, Deterministic Constructions}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.38
Boolean Function Analysis on High-Dimensional Expanders

Authors: Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders. Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse model for the Boolean slice or hypercube, and quite possibly additional results from Boolean function analysis can be carried over to this sparse model. Therefore, this model can be viewed as a derandomization of the Boolean slice, containing |X(k)|=O(n) points in comparison to binom{n}{k+1} points in the (k+1)-slice (which consists of all n-bit strings with exactly k+1 ones).
Cite as

Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha. Boolean Function Analysis on High-Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dikstein_et_al:LIPIcs.APPROX-RANDOM.2018.38,
  author =	{Dikstein, Yotam and Dinur, Irit and Filmus, Yuval and Harsha, Prahladh},
  title =	{{Boolean Function Analysis on High-Dimensional Expanders}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{38:1--38:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.38},
  URN =		{urn:nbn:de:0030-drops-94421},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.38},
  annote =	{Keywords: high dimensional expanders, Boolean function analysis, sparse model}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact