2 Search Results for "Shayevitz, Ofer"


Document
Incompressiblity and Next-Block Pseudoentropy

Authors: Iftach Haitner, Noam Mazor, and Jad Silbak

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


Abstract
A distribution is k-incompressible, Yao [FOCS '82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy, Hastad, Impagliazzo, Levin, and Luby [SICOMP '99], and to other cryptographic hardness assumptions, was unclear. We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k-2) bits of next-block pseudoentropy, a refinement of pseudoentropy introduced by Haitner, Reingold, and Vadhan [SICOMP '13]. We deduce that a samplable distribution X that is (H(X)+2)-incompressible, implies the existence of one-way functions.

Cite as

Iftach Haitner, Noam Mazor, and Jad Silbak. Incompressiblity and Next-Block Pseudoentropy. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{haitner_et_al:LIPIcs.ITCS.2023.66,
  author =	{Haitner, Iftach and Mazor, Noam and Silbak, Jad},
  title =	{{Incompressiblity and Next-Block Pseudoentropy}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{66:1--66:18},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.66},
  URN =		{urn:nbn:de:0030-drops-175697},
  doi =		{10.4230/LIPIcs.ITCS.2023.66},
  annote =	{Keywords: incompressibility, next-block pseudoentropy, sparse languages}
}
Document
Resilience of 3-Majority Dynamics to Non-Uniform Schedulers

Authors: Uri Meir, Rotem Oshman, Ofer Shayevitz, and Yuval Volkov

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


Abstract
In recent years there has been great interest in networks of passive, computationally-weak nodes, whose interactions are controlled by the outside environment; examples include population protocols, chemical reactions networks (CRNs), DNA computing, and more. Such networks are usually studied under one of two extreme regimes: the schedule of interactions is either assumed to be adversarial, or it is assumed to be chosen uniformly at random. In this paper we study an intermediate regime, where the interaction at each step is chosen from some not-necessarily-uniform distribution: we introduce the definition of a (p,ε)-scheduler, where the distribution that the scheduler chooses at every round can be arbitrary, but it must have 𝓁_p-distance at most ε from the uniform distribution. We ask how far from uniform we can get before the dynamics of the model break down. For simplicity, we focus on the 3-majority dynamics, a type of chemical reaction network where the nodes of the network interact in triplets. Each node initially has an opinion of either 𝖷 or 𝖸, and when a triplet of nodes interact, all three nodes change their opinion to the majority of their three opinions. It is known that under a uniformly random scheduler, if we have an initial gap of Ω(√{n log n}) in favor of one value, then w.h.p. all nodes converge to the majority value within O(n log n) steps. For the 3-majority dynamics, we prove that among all non-uniform schedulers with a given 𝓁_1- or 𝓁_∞-distance to the uniform scheduler, the worst case is a scheduler that creates a partition in the network, disconnecting some nodes from the rest: under any (p,ε)-close scheduler, if the scheduler’s distance from uniform only suffices to disconnect a set of size at most S nodes and we start from a configuration with a gap of Ω(S+√{n log n}) in favor of one value, then we are guaranteed that all but O(S) nodes will convert to the majority value. We also show that creating a partition is not necessary to cause the system to converge to the wrong value, or to fail to converge at all. We believe that our work can serve as a first step towards understanding the resilience of chemical reaction networks and population protocols under non-uniform schedulers.

Cite as

Uri Meir, Rotem Oshman, Ofer Shayevitz, and Yuval Volkov. Resilience of 3-Majority Dynamics to Non-Uniform Schedulers. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 86:1-86:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.ITCS.2023.86,
  author =	{Meir, Uri and Oshman, Rotem and Shayevitz, Ofer and Volkov, Yuval},
  title =	{{Resilience of 3-Majority Dynamics to Non-Uniform Schedulers}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{86:1--86:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.86},
  URN =		{urn:nbn:de:0030-drops-175895},
  doi =		{10.4230/LIPIcs.ITCS.2023.86},
  annote =	{Keywords: chemical reaction networks, population protocols, randomized scheduler}
}
  • Refine by Author
  • 1 Haitner, Iftach
  • 1 Mazor, Noam
  • 1 Meir, Uri
  • 1 Oshman, Rotem
  • 1 Shayevitz, Ofer
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Biological networks
  • 1 Computing methodologies → Distributed algorithms
  • 1 Theory of computation → Computational complexity and cryptography

  • Refine by Keyword
  • 1 chemical reaction networks
  • 1 incompressibility
  • 1 next-block pseudoentropy
  • 1 population protocols
  • 1 randomized scheduler
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2023

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