1 Search Results for "Geyzel, Zeev"

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-dev.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}
}
  • Refine by Author
  • 1 Dunkelman, Orr
  • 1 Geyzel, Zeev
  • 1 Keller, Chaya
  • 1 Keller, Nathan
  • 1 Ronen, Eyal
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Error-correcting codes
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 1 Brunn-Minkowski theorem
  • 1 Sperner’s lemma
  • 1 error resilience
  • 1 high-dimensional rounding
  • 1 space partition
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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 Imprint Privacy Contact