Search Results

Documents authored by Tessler, Ran J.

Document
DOI: 10.4230/LIPIcs.ITCS.2023.78
Garland’s Technique for Posets and High Dimensional Grassmannian Expanders

Authors: Tali Kaufman and Ran J. Tessler

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Local to global machinery plays an important role in the study of simplicial complexes, since the seminal work of Garland [Garland, 1973] to our days. In this work we develop a local to global machinery for general posets. We show that the high dimensional expansion notions and many recent expansion results have a generalization to posets. Examples are fast convergence of high dimensional random walks generalizing [Kaufman et al., 2020], [Alev and Lau, 2020], an equivalence with a global random walk definition, generalizing [Dikstein et al., 2018] and a trickling down theorem, generalizing [Oppenheim, 2018]. In particular, we show that some posets, such as the Grassmannian poset, exhibit qualitatively stronger trickling down effect than simplicial complexes. Using these methods, and the novel idea of posetification to Ramanujan complexes [Lubotzky et al., 2005a], [Lubotzky et al., 2005b], we construct a constant degree expanding Grassmannian poset, and analyze its expansion. This it the first construction of such object, whose existence was conjectured in [Dikstein et al., 2018].
Cite as

Tali Kaufman and Ran J. Tessler. Garland’s Technique for Posets and High Dimensional Grassmannian Expanders. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 78:1-78:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.ITCS.2023.78,
  author =	{Kaufman, Tali and Tessler, Ran J.},
  title =	{{Garland’s Technique for Posets and High Dimensional Grassmannian Expanders}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{78:1--78:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.78},
  URN =		{urn:nbn:de:0030-drops-175819},
  doi =		{10.4230/LIPIcs.ITCS.2023.78},
  annote =	{Keywords: High dimensional Expanders, Posets, Grassmannian, Garland Method}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2021.4
Error Resilient Space Partitioning (Invited Talk)

Authors: Orr Dunkelman, Zeev Geyzel, Chaya Keller, Nathan Keller, Eyal Ronen, Adi Shamir, and Ran J. Tessler

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
In this paper we consider a new type of space partitioning which bridges the gap between continuous and discrete spaces in an error resilient way. It is motivated by the problem of rounding noisy measurements from some continuous space such as ℝ^d to a discrete subset of representative values, in which each tile in the partition is defined as the preimage of one of the output points. Standard rounding schemes seem to be inherently discontinuous across tile boundaries, but in this paper we show how to make it perfectly consistent (with error resilience ε) by guaranteeing that any pair of consecutive measurements X₁ and X₂ whose L₂ distance is bounded by ε will be rounded to the same nearby representative point in the discrete output space. We achieve this resilience by allowing a few bits of information about the first measurement X₁ to be unidirectionally communicated to and used by the rounding process of the second measurement X₂. Minimizing this revealed information can be particularly important in privacy-sensitive applications such as COVID-19 contact tracing, in which we want to find out all the cases in which two persons were at roughly the same place at roughly the same time, by comparing cryptographically hashed versions of their itineraries in an error resilient way. The main problem we study in this paper is characterizing the achievable tradeoffs between the amount of information provided and the error resilience for various dimensions. We analyze the problem by considering the possible colored tilings of the space with k available colors, and use the color of the tile in which X₁ resides as the side information. We obtain our upper and lower bounds with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Sperner’s lemma, and Čech cohomology. In particular, we show that when X_i ∈ ℝ^d, communicating log₂(d+1) bits of information is both sufficient and necessary (in the worst case) to achieve positive resilience, and when d=3 we obtain a tight upper and lower asymptotic bound of (0.561 …)k^{1/3} on the achievable error resilience when we provide log₂(k) bits of information about X₁’s color.
Cite as

Orr Dunkelman, Zeev Geyzel, Chaya Keller, Nathan Keller, Eyal Ronen, Adi Shamir, and Ran J. Tessler. Error Resilient Space Partitioning (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dunkelman_et_al:LIPIcs.ICALP.2021.4,
  author =	{Dunkelman, Orr and Geyzel, Zeev and Keller, Chaya and Keller, Nathan and Ronen, Eyal and Shamir, Adi and Tessler, Ran J.},
  title =	{{Error Resilient Space Partitioning}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.4},
  URN =		{urn:nbn:de:0030-drops-140731},
  doi =		{10.4230/LIPIcs.ICALP.2021.4},
  annote =	{Keywords: space partition, high-dimensional rounding, error resilience, sphere packing, Sperner’s lemma, Brunn-Minkowski theorem, \v{C}ech cohomology}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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