5 Search Results for "Bilu, Yonatan"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.92
A Combinatorial Characterization of Constant Mixing Time

Authors: Lap Chi Lau and Raymond Liu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Classical spectral graph theory characterizes graphs with logarithmic mixing time. In this work, we present a combinatorial characterization of graphs with constant mixing time. The combinatorial characterization is based on the small-set bipartite density condition, which is weaker than having near-optimal spectral radius and is stronger than having near-optimal small-set vertex expansion.
Cite as

Lap Chi Lau and Raymond Liu. A Combinatorial Characterization of Constant Mixing Time. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 92:1-92:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lau_et_al:LIPIcs.ITCS.2026.92,
  author =	{Lau, Lap Chi and Liu, Raymond},
  title =	{{A Combinatorial Characterization of Constant Mixing Time}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{92:1--92:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.92},
  URN =		{urn:nbn:de:0030-drops-253792},
  doi =		{10.4230/LIPIcs.ITCS.2026.92},
  annote =	{Keywords: Random walks, mixing time, bipartite density, spectral graph theory}
}
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
DOI: 10.4230/LIPIcs.ITCS.2025.40
Derandomized Squaring: An Analytical Insight into Its True Behavior

Authors: Gil Cohen, Itay Cohen, Gal Maor, and Yuval Peled

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
The notion of the derandomized square of two graphs, denoted as G s H, was introduced by Rozenman and Vadhan as they rederived Reingold’s Theorem, SL = 𝐋. This pseudorandom primitive, closely related to the Zig-Zag product, plays a crucial role in recent advancements on space-bounded derandomization. For this and other reasons, understanding the spectral expansion λ(G s H) becomes paramount. Rozenman and Vadhan derived an upper bound for λ(G s H) in terms of the spectral expansions of the individual graphs, λ(G) and λ(H). They also proved their bound is optimal if the only information incorporated to the bound is the spectral expansion of the two graphs. The objective of this work is to gain deeper insights into the behavior of derandomized squaring by taking into account the entire spectrum of H, where we focus on a vertex-transitive c-regular H. Utilizing deep results from analytic combinatorics, we establish a lower bound on λ(G s H) that applies universally to all graphs G. Our work reveals that the bound is the minimum value of the function d⋅ x - d(d-1)χ_x(H)/χ_x'(H) in the domain (c,∞), where χ_x(H) is the characteristic polynomial of the d-vertex graph H. This bound lies far below the known upper bound for λ(G s H) for most reasonable choices for H. Empirical evidence suggests that our lower bound is optimal. We support the tightness of our lower bound by showing that the bound is tight for a class of graphs which exhibit local behavior similar to a derandomized squaring operation with H. To this end, we make use of finite free probability theory. In our second result, we resolve an open question posed by Cohen and Maor (STOC 2023) and establish a lower bound for the spectral expansion of rotating expanders. These graphs are constructed by taking a random walk with vertex permutations occurring after each step. We prove that Cohen and Maor’s construction is essentially optimal. Unlike our results on derandomized squaring, the proof in this instance relies solely on combinatorial methods. The key insight lies in establishing a connection between random walks on graph products and the Fuss-Catalan numbers.
Cite as

Gil Cohen, Itay Cohen, Gal Maor, and Yuval Peled. Derandomized Squaring: An Analytical Insight into Its True Behavior. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ITCS.2025.40,
  author =	{Cohen, Gil and Cohen, Itay and Maor, Gal and Peled, Yuval},
  title =	{{Derandomized Squaring: An Analytical Insight into Its True Behavior}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{40:1--40:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.40},
  URN =		{urn:nbn:de:0030-drops-226681},
  doi =		{10.4230/LIPIcs.ITCS.2025.40},
  annote =	{Keywords: Derandomized Squaring, Spectral Graph Theory, Analytic Combinatorics}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.9
Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations

Authors: Chandra Chekuri and Shalmoli Gupta

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

Abstract
We consider clustering in the perturbation resilience model that has been studied since the work of Bilu and Linial [Yonatan Bilu and Nathan Linial, 2010] and Awasthi, Blum and Sheffet [Awasthi et al., 2012]. A clustering instance I is said to be alpha-perturbation resilient if the optimal solution does not change when the pairwise distances are modified by a factor of alpha and the perturbed distances satisfy the metric property - this is the metric perturbation resilience property introduced in [Angelidakis et al., 2017] and a weaker requirement than prior models. We make two high-level contributions. - We show that the natural LP relaxation of k-center and asymmetric k-center is integral for 2-perturbation resilient instances. We belive that demonstrating the goodness of standard LP relaxations complements existing results [Maria{-}Florina Balcan et al., 2016; Angelidakis et al., 2017] that are based on new algorithms designed for the perturbation model. - We define a simple new model of perturbation resilience for clustering with outliers. Using this model we show that the unified MST and dynamic programming based algorithm proposed in [Angelidakis et al., 2017] exactly solves the clustering with outliers problem for several common center based objectives (like k-center, k-means, k-median) when the instances is 2-perturbation resilient. We further show that a natural LP relxation is integral for 2-perturbation resilient instances of k-center with outliers.
Cite as

Chandra Chekuri and Shalmoli Gupta. Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:LIPIcs.APPROX-RANDOM.2018.9,
  author =	{Chekuri, Chandra and Gupta, Shalmoli},
  title =	{{Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{9:1--9:16},
  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.9},
  URN =		{urn:nbn:de:0030-drops-94136},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.9},
  annote =	{Keywords: Clustering, Perturbation Resilience, LP Integrality, Outliers, Beyond Worst Case Analysis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.526
On the practically interesting instances of MAXCUT

Authors: Yonatan Bilu, Amit Daniely, Nati Linial, and Michael Saks

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
For many optimization problems, the instances of practical interest often occupy just a tiny part of the algorithm's space of instances. Following (Y. Bilu and N. Linial, 2010), we apply this perspective to MAXCUT, viewed as a clustering problem. Using a variety of techniques, we investigate practically interesting instances of this problem. Specifically, we show how to solve in polynomial time distinguished, metric, expanding and dense instances of MAXCUT under mild stability assumptions. In particular, (1 + epsilon)-stability (which is optimal) suffices for metric and dense MAXCUT. We also show how to solve in polynomial time Omega(sqrt(n))-stable instances of MAXCUT, substantially improving the best previously known result.
Cite as

Yonatan Bilu, Amit Daniely, Nati Linial, and Michael Saks. On the practically interesting instances of MAXCUT. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 526-537, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bilu_et_al:LIPIcs.STACS.2013.526,
  author =	{Bilu, Yonatan and Daniely, Amit and Linial, Nati and Saks, Michael},
  title =	{{On the practically interesting instances of MAXCUT}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{526--537},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.526},
  URN =		{urn:nbn:de:0030-drops-39625},
  doi =		{10.4230/LIPIcs.STACS.2013.526},
  annote =	{Keywords: MAXCUT, Clustering, Hardness in practice, Stability, Non worst-case analysis}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2018
  • 1 2013

  • Refine by Author
  • 1 Bilu, Yonatan
  • 1 Chekuri, Chandra
  • 1 Cohen, Gil
  • 1 Cohen, Itay
  • 1 Daniely, Amit
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Spectra of graphs
  • 1 Theory of computation
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Random walks and Markov chains

  • Refine by Keyword
  • 2 Clustering
  • 1 Analytic Combinatorics
  • 1 Beyond Worst Case Analysis
  • 1 Derandomized Squaring
  • 1 Grassmannian expander
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact