12 Search Results for "Meir, Uri"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.102
Smoothed Analysis of Dynamic Graph Algorithms

Authors: Uri Meir and Ami Paz

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

Abstract
Recent years have seen significant progress in the study of dynamic graph algorithms, and most notably, the introduction of strong lower bound techniques for them (e.g., Henzinger, Krinninger, Nanongkai and Saranurak, STOC 2015; Larsen and Yu, FOCS 2023). As worst-case analysis (adversarial inputs) may lead to the necessity of high running times, a natural question arises: in which cases are high running times really necessary, and in which cases these inputs merely manifest unique pathological cases? Early attempts to tackle this question were made by Nikoletseas, Reif, Spirakis and Yung (ICALP 1995) and by Alberts and Henzinger (Algorithmica 1998), who considered models with very little adversarial control over the inputs, and showed fast algorithms exist for them. The question was then overlooked for decades, until Henzinger, Lincoln and Saha (SODA 2022) recently addressed uniformly random inputs, and presented algorithms and impossibility results for several subgraph counting problems. To tackle the above question more thoroughly, we employ smoothed analysis, a celebrated framework introduced by Spielman and Teng (J. ACM, 2004). An input is proposed by an adversary but then a noisy version of it is processed by the algorithm instead. This model of inputs is parameterized by the amount of adversarial control, and fully interpolates between worst-case inputs and a uniformly random input. Doing so, we extend impossibility results for some problems to the smoothed model with only a minor quantitative loss. That is, we show that partially-adversarial inputs suffice to impose high running times for certain problems. In contrast, we show that other problems become easy even with the slightest amount of noise. In addition, we study the interplay between the adversary and the noise, leading to three natural models of smoothed inputs, for which we show a hierarchy of increasing difficulty stretching between the average-case and the worst-case complexities.
Cite as

Uri Meir and Ami Paz. Smoothed Analysis of Dynamic Graph Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.ITCS.2026.102,
  author =	{Meir, Uri and Paz, Ami},
  title =	{{Smoothed Analysis of Dynamic Graph Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{102:1--102:20},
  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.102},
  URN =		{urn:nbn:de:0030-drops-253896},
  doi =		{10.4230/LIPIcs.ITCS.2026.102},
  annote =	{Keywords: Dynamic graph algorithms, Smoothed analysis, Shortest paths}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.59
Testing Tensor Products of Algebraic Codes

Authors: Sumegha Garg, Madhu Sudan, and Gabriel Wu

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

Abstract
Motivated by recent advances in locally testable codes and quantum LDPCs based on robust testability of tensor product codes, we explore the local testability of tensor products of (an abstraction of) algebraic geometry codes. Such codes are parameterized by, in addition to standard parameters such as block length n and dimension k, their genus g. We show that the tensor product of two algebraic geometry codes is robustly locally testable provided n = Ω((k+g)²). Apart from Reed-Solomon codes, this seems to be the first explicit family of two-wise tensor codes of high dual distance that is robustly locally testable by the natural test that measures the expected distance of a random row/column from the underlying code.
Cite as

Sumegha Garg, Madhu Sudan, and Gabriel Wu. Testing Tensor Products of Algebraic Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.APPROX/RANDOM.2025.59,
  author =	{Garg, Sumegha and Sudan, Madhu and Wu, Gabriel},
  title =	{{Testing Tensor Products of Algebraic Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{59:1--59:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.59},
  URN =		{urn:nbn:de:0030-drops-244254},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.59},
  annote =	{Keywords: Algebraic geometry codes, Robust testability, Tensor products of codes}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.44
Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances

Authors: Tim A. Hartmann and Dániel Marx

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The distance-d variants of Independent Set and Dominating Set problems have been extensively studied from different algorithmic viewpoints. In particular, the complexity of these problems are well understood on bounded-treewidth graphs [Katsikarelis, Lampis, and Paschos, Discret. Appl. Math 2022][Borradaile and Le, IPEC 2016]: given a tree decomposition of width t, the two problems can be solved in time d^t⋅ n^O(1) and (2d+1)^t⋅ n^O(1), respectively. Furthermore, assuming the Strong Exponential-Time Hypothesis (SETH), the base constants are best possible in these running times: they cannot be improved to d-ε and 2d+1-ε, respectively, for any ε > 0. We investigate continuous versions of these problems in a setting introduced by Megiddo and Tamir [SICOMP 1983], where every edge is modeled by a unit-length interval of points. In the δ-Dispersion problem, the task is to find a maximum number of points (possibly inside edges) that are pairwise at distance at least δ from each other. Similarly, in the δ-Covering problem, the task is to find a minimum number of points (possibly inside edges) such that every point of the graph (including those inside edges) is at distance at most δ from the selected point set. We provide a comprehensive understanding of these two problems on bounded-treewidth graphs. 1) Let δ = a/b with a and b being coprime. If a ≤ 2, then δ-Dispersion is polynomial-time solvable. For a ≥ 3, given a tree decomposition of width t, the problem can be solved in time (2a)^t⋅ n^O(1), and, assuming SETH, there is no (2a-ε)^t⋅n^{O(1)} time algorithm for any ε > 0. 2) Let δ = a/b with a and b being coprime. If a = 1, then δ-Covering is polynomial-time solvable. For a ≥ 2, given a tree decomposition of width t, the problem can be solved in time ((2+2(bod 2)) a)^t⋅ n^O(1), and, assuming SETH, there is no ((2+2(bod 2))a -ε)^t⋅n^O(1) time algorithm for any ε > 0. 3) For every fixed irrational number δ > 0 satisfying some mild computability condition, both δ-Dispersion and δ-Covering can be solved in time n^O(t) on graphs of treewidth t. We show a very explicitly defined irrational number δ = (4∑_{j=1}^∞ 2^{-2^j})^{-1} ≈ 0.790085 such that δ-Dispersion and δ/2-Covering are W[1]-hard parameterized by the treewidth t of the input graph, and, assuming ETH, cannot be solved in time f(t)⋅n^o(t). As a key step in obtaining these results, we extend earlier results on distance-d versions of Independent Set and Dominating Set: We determine the exact complexity of these problems in the special case when the input graph arises from some graph G' by subdividing every edge exactly b times.
Cite as

Tim A. Hartmann and Dániel Marx. Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hartmann_et_al:LIPIcs.STACS.2025.44,
  author =	{Hartmann, Tim A. and Marx, D\'{a}niel},
  title =	{{Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.44},
  URN =		{urn:nbn:de:0030-drops-228700},
  doi =		{10.4230/LIPIcs.STACS.2025.44},
  annote =	{Keywords: Independence, Domination, Irrationals, Treewidth, SETH}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.26
Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function

Authors: Nikolai Chukhin, Alexander S. Kulikov, and Ivan Mihajlin

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Proving formula depth lower bounds is a fundamental challenge in complexity theory, with the strongest known bound of (3 - o(1))log n established by Håstad over 25 years ago. The Karchmer-Raz-Wigderson (KRW) conjecture offers a promising approach to advance these bounds and separate P from NC¹. It suggests that the depth complexity of a function composition f ⋄ g approximates the sum of the depth complexities of f and g. The Karchmer-Wigderson (KW) relation framework translates formula depth into communication complexity, restating the KRW conjecture as CC(KW_f ⋄ KW_g) ≈ CC(KW_f) + CC(KW_g). Prior work has confirmed the conjecture under various relaxations, often replacing one or both KW relations with the universal relation or constraining the communication game through strong composition. In this paper, we examine the strong composition KW_XOR ⊛ KW_f of the parity function and a random Boolean function f. We prove that with probability 1-o(1), any protocol solving this composition requires at least n^{3 - o(1)} leaves. This result establishes a depth lower bound of (3 - o(1))log n, matching Håstad’s bound, but is applicable to a broader class of inner functions, even when the outer function is simple. Though bounds for the strong composition do not translate directly to formula depth bounds, they usually help to analyze the standard composition (of the corresponding two functions) which is directly related to formula depth. Our proof utilizes formal complexity measures. First, we apply Khrapchenko’s method to show that numerous instances of f remain unsolved after several communication steps. Subsequently, we transition to a different formal complexity measure to demonstrate that the remaining communication problem is at least as hard as KW_OR ⊛ KW_f. This hybrid approach not only achieves the desired lower bound, but also introduces a novel technique for analyzing formula depth, potentially informing future research in complexity theory.
Cite as

Nikolai Chukhin, Alexander S. Kulikov, and Ivan Mihajlin. Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chukhin_et_al:LIPIcs.STACS.2025.26,
  author =	{Chukhin, Nikolai and Kulikov, Alexander S. and Mihajlin, Ivan},
  title =	{{Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.26},
  URN =		{urn:nbn:de:0030-drops-228513},
  doi =		{10.4230/LIPIcs.STACS.2025.26},
  annote =	{Keywords: complexity, formula complexity, lower bounds, Boolean functions, depth}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.94
New Direct Sum Tests

Authors: Alek Westover, Edward Yu, and Kai Zhe Zheng

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

Abstract
A function f:[n]^{d} → 𝔽₂ is a direct sum if there are functions L_i:[n] → 𝔽₂ such that f(x) = ∑_i L_i(x_i). In this work we give multiple results related to the property testing of direct sums. Our first result concerns a test proposed by Dinur and Golubev in [Dinur and Golubev, 2019]. We call their test the Diamond test and show that it is indeed a direct sum tester. More specifically, we show that if a function f is ε-far from being a direct sum function, then the Diamond test rejects f with probability at least Ω_{n,ε}(1). Even in the case of n = 2, the Diamond test is, to the best of our knowledge, novel and yields a new tester for the classic property of affinity. Apart from the Diamond test, we also analyze a broad family of direct sum tests, which at a high level, run an arbitrary affinity test on the restriction of f to a random hypercube inside of [n]^d. This family of tests includes the direct sum test analyzed in [Dinur and Golubev, 2019], but does not include the Diamond test. As an application of our result, we obtain a direct sum test which works in the online adversary model of [Iden Kalemaj et al., 2022]. Finally, we also discuss a Fourier analytic interpretation of the diamond tester in the n = 2 case, as well as prove local correction results for direct sum as conjectured by [Dinur and Golubev, 2019].
Cite as

Alek Westover, Edward Yu, and Kai Zhe Zheng. New Direct Sum Tests. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 94:1-94:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{westover_et_al:LIPIcs.ITCS.2025.94,
  author =	{Westover, Alek and Yu, Edward and Zheng, Kai Zhe},
  title =	{{New Direct Sum Tests}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{94:1--94:26},
  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.94},
  URN =		{urn:nbn:de:0030-drops-227229},
  doi =		{10.4230/LIPIcs.ITCS.2025.94},
  annote =	{Keywords: Linearity testing, Direct sum, Grids}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.65
Online Versus Offline Adversaries in Property Testing

Authors: Esty Kelman, Ephraim Linder, and Sofya Raskhodnikova

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

Abstract
We study property testing with incomplete or noisy inputs. The models we consider allow for adversarial manipulation of the input, but differ in whether the manipulation can be done only offline, i.e., before the execution of the algorithm, or online, i.e., as the algorithm runs. The manipulations by an adversary can come in the form of erasures or corruptions. We compare the query complexity and the randomness complexity of property testing in the offline and online models. Kalemaj, Raskhodnikova, and Varma (Theory Comput. `23) provide properties that can be tested with a small number of queries with offline erasures, but cannot be tested at all with online erasures. We demonstrate that the two models are incomparable in terms of query complexity: we construct properties that can be tested with a constant number of queries in the online corruption model, but require querying a significant fraction of the input in the offline erasure model. We also construct properties that exhibit a strong separation between the randomness complexity of testing in the presence of offline and online adversaries: testing these properties in the online model requires exponentially more random bits than in the offline model, even when they are tested with nearly the same number of queries in both models. Our randomness separation relies on a novel reduction from randomness-efficient testers in the adversarial online model to query-efficient testers in the standard model.
Cite as

Esty Kelman, Ephraim Linder, and Sofya Raskhodnikova. Online Versus Offline Adversaries in Property Testing. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 65:1-65:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kelman_et_al:LIPIcs.ITCS.2025.65,
  author =	{Kelman, Esty and Linder, Ephraim and Raskhodnikova, Sofya},
  title =	{{Online Versus Offline Adversaries in Property Testing}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{65:1--65:18},
  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.65},
  URN =		{urn:nbn:de:0030-drops-226933},
  doi =		{10.4230/LIPIcs.ITCS.2025.65},
  annote =	{Keywords: Property Testing, Online Adversary, Offline Adversary, Query Complexity, Randomness Complexity, Separations}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.57
Stochastic Distance in Property Testing

Authors: Uri Meir, Gregory Schwartzman, and Yuichi Yoshida

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

Abstract
We introduce a novel concept termed "stochastic distance" for property testing. Diverging from the traditional definition of distance, where a distance t implies that there exist t edges that can be added to ensure a graph possesses a certain property (such as k-edge-connectivity), our new notion implies that there is a high probability that adding t random edges will endow the graph with the desired property. While formulating testers based on this new distance proves challenging in a sequential environment, it is much easier in a distributed setting. Taking k-edge-connectivity as a case study, we design ultra-fast testing algorithms in the CONGEST model. Our introduction of stochastic distance offers a more natural fit for the distributed setting, providing a promising avenue for future research in emerging models of computation.
Cite as

Uri Meir, Gregory Schwartzman, and Yuichi Yoshida. Stochastic Distance in Property Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 57:1-57:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.APPROX/RANDOM.2024.57,
  author =	{Meir, Uri and Schwartzman, Gregory and Yoshida, Yuichi},
  title =	{{Stochastic Distance in Property Testing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{57:1--57:13},
  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.57},
  URN =		{urn:nbn:de:0030-drops-210506},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.57},
  annote =	{Keywords: Connectivity, k-edge connectivity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.11
Property Testing with Online Adversaries

Authors: Omri Ben-Eliezer, Esty Kelman, Uri Meir, and Sofya Raskhodnikova

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies property testing in situations where access to the input degrades continuously and adversarially. Specifically, after each query made by the tester is answered, the adversary can intervene and either erase or corrupt t data points. In this work, we investigate a more nuanced version of the online model in order to overcome old and new impossibility results for the original model. We start by presenting an optimal tester for linearity and a lower bound for low-degree testing of Boolean functions in the original model. We overcome the lower bound by allowing batch queries, where the tester gets a group of queries answered between manipulations of the data. Our batch size is small enough so that function values for a single batch on their own give no information about whether the function is of low degree. Finally, to overcome the impossibility results of Kalemaj et al. for sortedness and the Lipschitz property of sequences, we extend the model to include t < 1, i.e., adversaries that make less than one erasure per query. For sortedness, we characterize the rate of erasures for which online testing can be performed, exhibiting a sharp transition from optimal query complexity to impossibility of testability (with any number of queries). Our online tester works for a general class of local properties of sequences. One feature of our results is that we get new (and in some cases, simpler) optimal algorithms for several properties in the standard property testing model.
Cite as

Omri Ben-Eliezer, Esty Kelman, Uri Meir, and Sofya Raskhodnikova. Property Testing with Online Adversaries. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 11:1-11:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2024.11,
  author =	{Ben-Eliezer, Omri and Kelman, Esty and Meir, Uri and Raskhodnikova, Sofya},
  title =	{{Property Testing with Online Adversaries}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{11:1--11:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.11},
  URN =		{urn:nbn:de:0030-drops-195395},
  doi =		{10.4230/LIPIcs.ITCS.2024.11},
  annote =	{Keywords: Linearity testing, low-degree testing, Reed-Muller codes, testing properties of sequences, erasure-resilience, corruption-resilience}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.86
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.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}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.17
Comparison Graphs: A Unified Method for Uniformity Testing

Authors: Uri Meir

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Distribution testing can be described as follows: q samples are being drawn from some unknown distribution P over a known domain [n]. After the sampling process, a decision must be made about whether P holds some property, or is far from it. The most studied problem in the field is arguably uniformity testing, where one needs to distinguish the case that P is uniform over [n] from the case that P is ε-far from being uniform (in 𝓁₁). It is known that for this task Θ(√n/ε²) samples are necessary and sufficient. This problem was recently considered in various restricted models that pose, for example, communication or memory constraints. In more than one occasion, the known optimal solution boils down to counting collisions among the drawn samples (each two samples that have the same value add one to the count). This idea dates back to the first uniformity tester, and was coined the name "collision-based tester". In this paper, we introduce the notion of comparison graphs and use it to formally define a generalized collision-based tester. Roughly speaking, the edges of the graph indicate the tester which pairs of samples should be compared (that is, the original tester is induced by a clique, where all pairs are being compared). We prove a structural theorem that gives a sufficient condition for a comparison graph to induce a good uniformity tester. As an application, we develop a generic method to test uniformity, and devise nearly-optimal uniformity testers under various computational constraints. We improve and simplify a few known results, and introduce a new constrained model in which the method also produces an efficient tester. The idea behind our method is to translate computational constraints of a certain model to ones on the comparison graph, which paves the way to finding a good graph: a set of comparisons allowed by the model that suffice to test for uniformity. We believe that in future consideration of uniformity testing in new models, our method can be used to obtain efficient testers with minimal effort.
Cite as

Uri Meir. Comparison Graphs: A Unified Method for Uniformity Testing. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{meir:LIPIcs.ITCS.2021.17,
  author =	{Meir, Uri},
  title =	{{Comparison Graphs: A Unified Method for Uniformity Testing}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.17},
  URN =		{urn:nbn:de:0030-drops-135560},
  doi =		{10.4230/LIPIcs.ITCS.2021.17},
  annote =	{Keywords: Distribution Testing, Uniformity Testing, Distributed Algorithms, Streaming Algorithms, Comparison Graphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.28
Distributed Quantum Proofs for Replicated Data

Authors: Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
This paper tackles the issue of checking that all copies of a large data set replicated at several nodes of a network are identical. The fact that the replicas may be located at distant nodes prevents the system from verifying their equality locally, i.e., by having each node consult only nodes in its vicinity. On the other hand, it remains possible to assign certificates to the nodes, so that verifying the consistency of the replicas can be achieved locally. However, we show that, as the replicated data is large, classical certification mechanisms, including distributed Merlin-Arthur protocols, cannot guarantee good completeness and soundness simultaneously, unless they use very large certificates. The main result of this paper is a distributed quantum Merlin-Arthur protocol enabling the nodes to collectively check the consistency of the replicas, based on small certificates, and in a single round of message exchange between neighbors, with short messages. In particular, the certificate-size is logarithmic in the size of the data set, which gives an exponential advantage over classical certification mechanisms. We propose yet another usage of a fundamental quantum primitive, called the SWAP test, in order to show our main result.
Cite as

Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz. Distributed Quantum Proofs for Replicated Data. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.ITCS.2021.28,
  author =	{Fraigniaud, Pierre and Le Gall, Fran\c{c}ois and Nishimura, Harumichi and Paz, Ami},
  title =	{{Distributed Quantum Proofs for Replicated Data}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.28},
  URN =		{urn:nbn:de:0030-drops-135679},
  doi =		{10.4230/LIPIcs.ITCS.2021.28},
  annote =	{Keywords: Quantum Computing, Distributed Network Computing, Algorithmic Aspects of Networks}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.36
Models of Smoothing in Dynamic Networks

Authors: Uri Meir, Ami Paz, and Gregory Schwartzman

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Smoothed analysis is a framework suggested for mediating gaps between worst-case and average-case complexities. In a recent work, Dinitz et al. [Distributed Computing, 2018] suggested to use smoothed analysis in order to study dynamic networks. Their aim was to explain the gaps between real-world networks that function well despite being dynamic, and the strong theoretical lower bounds for arbitrary networks. To this end, they introduced a basic model of smoothing in dynamic networks, where an adversary picks a sequence of graphs, representing the topology of the network over time, and then each of these graphs is slightly perturbed in a random manner. The model suggested above is based on a per-round noise, and our aim in this work is to extend it to models of noise more suited for multiple rounds. This is motivated by long-lived networks, where the amount and location of noise may vary over time. To this end, we present several different models of noise. First, we extend the previous model to cases where the amount of noise is very small. Then, we move to more refined models, where the amount of noise can change between different rounds, e.g., as a function of the number of changes the network undergoes. We also study a model where the noise is not arbitrarily spread among the network, but focuses in each round in the areas where changes have occurred. Finally, we study the power of an adaptive adversary, who can choose its actions in accordance with the changes that have occurred so far. We use the flooding problem as a running case-study, presenting very different behaviors under the different models of noise, and analyze the flooding time in different models.
Cite as

Uri Meir, Ami Paz, and Gregory Schwartzman. Models of Smoothing in Dynamic Networks. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.DISC.2020.36,
  author =	{Meir, Uri and Paz, Ami and Schwartzman, Gregory},
  title =	{{Models of Smoothing in Dynamic Networks}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.36},
  URN =		{urn:nbn:de:0030-drops-131145},
  doi =		{10.4230/LIPIcs.DISC.2020.36},
  annote =	{Keywords: Distributed dynamic graph algorithms, Smoothed analysis, Flooding}
}
  • Refine by Type
  • 12 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 2 2024
  • 1 2023
  • 2 2021
  • Show More...

  • Refine by Author
  • 6 Meir, Uri
  • 3 Paz, Ami
  • 2 Kelman, Esty
  • 2 Raskhodnikova, Sofya
  • 2 Schwartzman, Gregory
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Distributed computing models
  • 2 Theory of computation → Dynamic graph algorithms
  • 1 Applied computing → Biological networks
  • Show More...

  • Refine by Keyword
  • 2 Linearity testing
  • 2 Smoothed analysis
  • 1 Algebraic geometry codes
  • 1 Algorithmic Aspects of Networks
  • 1 Boolean functions
  • 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