34 Search Results for "Newman, Ilan"

Document
DOI: 10.4230/LIPIcs.CPM.2026.28
Periodicity Property Testing on Strings with Wildcards

Authors: Carl Barton, Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert, Oded Lachish, and Tatiana Starikovskaya

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
In this work, we study periodicity in strings with wildcards. A string T with at most k wildcards is called strongly (p,k)-periodic if the wildcards in T can be replaced with alphabet symbols to obtain a string with period p, and weakly (p,k)-periodic if T[i] matches T[i+p] for all i. Intuitively, both generalize to (≤ g, k)-periodicity, which is the property of being (p,k)-periodic for some p ∈ [1..g]. An ε-tester for a property 𝒫 is an algorithm that distinguishes between strings that satisfy 𝒫 and strings where one needs to change at least an ε-fraction of the symbols to obtain a string that satisfies 𝒫. We study one-sided error testers, where strings satisfying 𝒫 must always be accepted, while strings that are ε-far must be rejected with probability at least 2/3. The complexity of a tester is the worst-case number of symbols of an input of length n it must read to make the decision. We design the following testers for p,g ≤ n/2: 1) An ε-tester for strong (p,k)-periodicity with complexity Õ_ε(1) . 2) An ε-tester for strong (≤ g,k)-periodicity with complexity Õ_ε(√g). 3) An ε-tester for weak (p,k)-periodicity with complexity Õ_ε(min(k, n /(k+p))). 4) An ε-tester for weak (≤ g,k)-periodicity with complexity Õ_ε(min(k+ √{gk}, n/√k)). Additionally, we show a lower bound on the complexity of ε-testers for weak (≤ g,k)-periodicity, implying that our tester for weak (≤ g,k)-periodicity is optimal up to a multiplicative (ε^{-1} ln(gk))^O(1) factor for a wide range of g and k. Finally, our tester for strong (≤ g,k)-periodicity generalizes the one of [Lachish and Newman; Algorithmica 2011] for strings without wildcards, matching (up to polylogarithmic factors) the unconditional lower bound of ̃Ω(√g) in said work for constant ε.
Cite as

Carl Barton, Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert, Oded Lachish, and Tatiana Starikovskaya. Periodicity Property Testing on Strings with Wildcards. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{barton_et_al:LIPIcs.CPM.2026.28,
  author =	{Barton, Carl and Charalampopoulos, Panagiotis and Ghazi, Taha El and Ellert, Jonas and Lachish, Oded and Starikovskaya, Tatiana},
  title =	{{Periodicity Property Testing on Strings with Wildcards}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.28},
  URN =		{urn:nbn:de:0030-drops-259543},
  doi =		{10.4230/LIPIcs.CPM.2026.28},
  annote =	{Keywords: periodicity, property testing, wildcards}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.89
Approximating Convex Hulls via Range Queries

Authors: Thomas Schibler, Jie Xue, and Jiumu Zhu

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Recently, motivated by the rapid increase of the data size in various applications, Monemizadeh [APPROX'23] and Driemel, Monemizadeh, Oh, Staals, and Woodruff [SoCG'25] studied geometric problems in the setting where the only access to the input point set is via querying a range-search oracle. Algorithms in this setting are evaluated on two criteria: (i) the number of queries to the oracle and (ii) the error of the output. In this paper, we continue this line of research and investigate one of the most fundamental geometric problems in the oracle setting, i.e., the convex hull problem. Let P be an unknown set of points in [0,1]^d equipped with a range-emptiness oracle. Via querying the oracle, the algorithm is supposed to output a convex polygon C ⊆ [0,1]^d as an estimation of the convex hull CH(P) of P. The error of the output is defined as the volume of the symmetric difference C ⊕ CH(P) = (C∖CH(P)) ∪ (CH(P)∖C). We prove tight and near-tight tradeoffs between the number of queries and the error of the output for different variants of the problem, depending on the type of the range-emptiness queries and whether the queries are non-adaptive or adaptive. - Orthogonal emptiness queries in d-dimensional space: We show that the minimum error a deterministic algorithm can achieve with q queries is Θ(q^{-1/d}) if the queries are non-adaptive, and Θ(q^{-1/(d-1)}) if the queries are adaptive. In particular, in 2D, the bounds are Θ(1/√q) and Θ(1/q) for non-adaptive and adaptive queries, respectively. - Halfplane emptiness queries in 2D: We show that the minimum error a deterministic algorithm can achieve with q queries is Θ(1/√q) if the queries are non-adaptive, and Θ̃(1/q²) if the queries are adaptive. Here Θ̃(⋅) hides logarithmic factors.
Cite as

Thomas Schibler, Jie Xue, and Jiumu Zhu. Approximating Convex Hulls via Range Queries. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 89:1-89:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{schibler_et_al:LIPIcs.SoCG.2026.89,
  author =	{Schibler, Thomas and Xue, Jie and Zhu, Jiumu},
  title =	{{Approximating Convex Hulls via Range Queries}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{89:1--89:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.89},
  URN =		{urn:nbn:de:0030-drops-258956},
  doi =		{10.4230/LIPIcs.SoCG.2026.89},
  annote =	{Keywords: convex hull, range searching}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.14
The Careless Coupon Collector’s Problem

Authors: Emilio Cruciani and Aditi Dudeja

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
We initiate the study of the Careless Coupon Collector’s Problem (CCCP), a novel variation of the classical coupon collector, that we envision as a model for information systems such as web crawlers, dynamic caches, and fault-resilient networks. In CCCP, a collector attempts to gather n distinct coupon types by obtaining one coupon type uniformly at random in each discrete round, however the collector is careless: at the end of each round, each collected coupon type is independently lost with probability p. We analyze the number of rounds required to complete the collection as a function of n and p. In particular, we show that it transitions from Θ(n ln n) when p = o((ln n)/n²) up to Θ(((np)/(1-p))ⁿ) when p = ω(1/n) in multiple distinct phases. Interestingly, when p = c/n, the process remains in a metastable phase, where the fraction of collected coupon types is concentrated around 1/(1+c) with probability 1-o(1), for a time window of length e^{Θ(n)}. Finally, we give an algorithm that computes the expected completion time of CCCP in O(n²) time.
Cite as

Emilio Cruciani and Aditi Dudeja. The Careless Coupon Collector’s Problem. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cruciani_et_al:LIPIcs.FUN.2026.14,
  author =	{Cruciani, Emilio and Dudeja, Aditi},
  title =	{{The Careless Coupon Collector’s Problem}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.14},
  URN =		{urn:nbn:de:0030-drops-257333},
  doi =		{10.4230/LIPIcs.FUN.2026.14},
  annote =	{Keywords: Coupon Collector, Markov Chains, Metastability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.30
Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions

Authors: Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Given Boolean functions f, g : 𝔽₂ⁿ → {-1,+1}, we say they are linearly isomorphic if there exists A ∈ GL_n(𝔽₂) such that f(x) = g(Ax) for all x. We study this problem in the tolerant property testing framework under the known-unknown model, where g is given explicitly and f is accessible only via oracle queries, meaning the algorithm may adaptively request the value of f(x) for inputs x ∈ 𝔽₂ⁿ of its choice. Given parameters ε ≥ 0 and ω > 0, the goal is to distinguish whether there exists A ∈ GL_n(𝔽₂) such that the normalized Hamming distance between f and g(Ax) is at most ε, or whether for every A ∈ GL_n(𝔽₂) the distance is at least ε+ω. Our main result is a tolerant tester making Õ ((m/ω) ⁴) queries to f, where m is an upper bound on the spectral norm of g, improving the previous Õ ((m/ω) ^{24}) bound of Wimmer and Yoshida. We complement this with a nearly matching lower bound of Ω(m²) for constant ω (for example, ω = 1/4), improving the prior Ω(log m) lower bound of Grigorescu, Wimmer and Xie. A key technical ingredient on the algorithmic side is a query-efficient local list corrector. For the lower bound, we give a reduction from communication complexity using a novel subclass of Maiorana-McFarland functions from symmetric-key cryptography.
Cite as

Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy. Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.STACS.2026.30,
  author =	{Datta, Swarnalipa and Ghosh, Arijit and Kayal, Chandrima and Paraashar, Manaswi and Roy, Manmatha},
  title =	{{Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{30:1--30:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle 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.2026.30},
  URN =		{urn:nbn:de:0030-drops-255194},
  doi =		{10.4230/LIPIcs.STACS.2026.30},
  annote =	{Keywords: Boolean Function, Isomorphism of Boolean Function, Fourier Analysis, Sublinear Algorithm, Property Testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.55
Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion

Authors: Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the graph satisfies P or not. Often, testers are restricted to a constant number of queries. While the graph properties for which there exists such a tester are somewhat well characterized in the dense graph model, it is not the case for sparse graphs. In this area, Czumaj and Sohler (FOCS’19) proved that H-freeness (i.e. the property of excluding the graph H as a subgraph) can be tested with constant queries on planar graphs as well as on graph classes excluding a minor. Using results from the sparsity toolkit, we propose a simpler alternative to the proof of Czumaj and Sohler, for a statement generalized to the broader notion of bounded expansion. That is, we prove that for any class 𝒞 with bounded expansion and any graph H, testing H-freeness can be done with constant query complexity on any graph G in 𝒞, where the constant depends on H and 𝒞, but is independent of G. While classes excluding a minor are prime examples of classes with bounded expansion, so are, for example, cubic graphs, graph classes with bounded maximum degree, or graphs of bounded book thickness. Additionally, random graphs with bounded average degree almost surely have bounded expansion.
Cite as

Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny. Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{humeau_et_al:LIPIcs.STACS.2026.55,
  author =	{Humeau, Samuel and Kant\'{e}, Mamadou Moustapha and Mock, Daniel and Picavet, Timoth\'{e} and Vigny, Alexandre},
  title =	{{Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle 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.2026.55},
  URN =		{urn:nbn:de:0030-drops-255441},
  doi =		{10.4230/LIPIcs.STACS.2026.55},
  annote =	{Keywords: Property testing, Sparsity, Bounded expansion, Treedepth}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.87
Range Longest Increasing Subsequence and Its Relatives

Authors: Karthik C. S. and Saladi Rahul

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

Abstract
Longest increasing subsequence (LIS) is a classical textbook problem which is still actively studied in various computational models. In this work, we present a few results for the range longest increasing subsequence problem (Range-LIS) and its variants. The input to Range-LIS is a sequence 𝒮 of n real numbers and a collection 𝒬 of m query ranges and for each query in 𝒬, the goal is to report the LIS of the sequence 𝒮 restricted to that query. Our two main results are for the following generalizations of the Range-LIS problem: 2D Range Queries: In this variant of the Range-LIS problem, each query is a pair of ranges, one of indices and the other of values, and we provide a randomized algorithm with running time Õ(mn^{1/2}+ n^{3/2})+O(k), where k is the cumulative length of the m output subsequences. This improves on the elementary Õ(mn) runtime algorithm when m = Ω(√n). Previously, the only known result breaking the quadratic barrier was of Tiskin [SODA'10] which could only handle 1D range queries (i.e., each query was a range of indices) and also just outputted the length of the LIS (instead of reporting the subsequence achieving that length). Subsequent to our paper, Gawrychowski, Gorbachev, and Kociumaka in a preprint have extended Tiskin’s approach to handle reporting 1D range queries in O(n(log n)³+m+k) time. Colored Sequences: In this variant of the Range-LIS problem, each element in 𝒮 is colored and for each query in 𝒬, the goal is to report a monochromatic LIS contained in the sequence 𝒮 restricted to that query. For 2D queries, we provide a randomized algorithm for this colored version with running time Õ(mn^{2/3}+ n^{5/3})+O(k). Moreover, for 1D queries, we provide an improved algorithm with running time Õ(mn^{1/2}+ n^{3/2})+O(k). Thus, we again improve on the elementary Õ(mn) runtime algorithm. Additionally, we prove that assuming the well-known Combinatorial Boolean Matrix Multiplication Hypothesis, that the runtime for 1D queries is essentially tight for combinatorial algorithms. Our algorithms combine several tools such as dynamic programming (to precompute increasing subsequences with some desirable properties), geometric data structures (to efficiently compute the dynamic programming entries), random sampling (to capture elements which are part of the LIS), classification of query ranges into large LIS and small LIS, and classification of colors into light and heavy. We believe that our techniques will be of interest to tackle other variants of LIS problem and other range-searching problems.
Cite as

Karthik C. S. and Saladi Rahul. Range Longest Increasing Subsequence and Its Relatives. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 87:1-87:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karthikc.s._et_al:LIPIcs.ITCS.2026.87,
  author =	{Karthik C. S. and Rahul, Saladi},
  title =	{{Range Longest Increasing Subsequence and Its Relatives}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{87:1--87: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.87},
  URN =		{urn:nbn:de:0030-drops-253740},
  doi =		{10.4230/LIPIcs.ITCS.2026.87},
  annote =	{Keywords: Longest Increasing Subsequence, Range Query, Fine-Grained Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.34
Testing Classical Properties from Quantum Data

Authors: Matthias C. Caro, Preksha Naik, and Joseph Slote

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

Abstract
Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of f instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |f⟩∝ ∑_x|x,f(x)⟩ or the phase state |(-1)^f⟩∝ ∑_x (-1)^{f(x)}|x⟩. Quantum advantage in testing from data. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query-based testers in each case. Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2^{Ω(n)} for any tester relying exclusively on Fourier and classical samples. Classical queries vs. quantum data. Our passive quantum testers are competitive with classical query-based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2^{n/2}) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.
Cite as

Matthias C. Caro, Preksha Naik, and Joseph Slote. Testing Classical Properties from Quantum Data. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 34:1-34:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{caro_et_al:LIPIcs.ITCS.2026.34,
  author =	{Caro, Matthias C. and Naik, Preksha and Slote, Joseph},
  title =	{{Testing Classical Properties from Quantum Data}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{34:1--34:26},
  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.34},
  URN =		{urn:nbn:de:0030-drops-253213},
  doi =		{10.4230/LIPIcs.ITCS.2026.34},
  annote =	{Keywords: Quantum Property Testing, Quantum Data, Boolean Functions}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.37
Communication Complexity of Equality and Error-Correcting Codes

Authors: Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan Prior, and Ilya Volkovich

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We study the public-coin randomized communication complexity of the equality function. The communication complexity of this function is known to be low when the error probability is constant and the players have access to many random bits. The complexity grows, however, if the allowed error probability and the amount of randomness are restricted. We show that public-coin randomized protocols for equality and error-correcting codes are essentially the same object. That is, given a protocol for equality, we can construct a code, and vice versa. We substantially extend the protocol-implies-code direction: any protocol computing a function with a large fooling set can be converted into an error-correcting code. As a corollary, we show that among functions with a fooling set of size s, equality on log s bits has the least randomized communication complexity, regardless of the restrictions on the error probability and the amount of randomness. Finally, we use the connection to error-correcting codes to analyze the randomized communication complexity of equality for varying restrictions on the error probability and the amount of randomness. In most cases, we provide tight bounds. We pinpoint the setting in which tight bounds are still unknown.
Cite as

Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan Prior, and Ilya Volkovich. Communication Complexity of Equality and Error-Correcting Codes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jacobs_et_al:LIPIcs.FSTTCS.2025.37,
  author =	{Jacobs, Dale and Jeang, John and Podolskii, Vladimir and Prior, Morgan and Volkovich, Ilya},
  title =	{{Communication Complexity of Equality and Error-Correcting Codes}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.37},
  URN =		{urn:nbn:de:0030-drops-251175},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.37},
  annote =	{Keywords: communication complexity, randomized communication complexity, error-correcting codes}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.12
Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments

Authors: Mark de Berg, Bart M. P. Jansen, and Jeroen S. K. Lamme

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Planar Separator Theorem, which states that any planar graph 𝒢 has a separator consisting of O(√n) nodes whose removal partitions 𝒢 into components of size at most 2n/3, is a widely used tool to obtain fast algorithms on planar graphs. Intersection graphs of disks, which generalize planar graphs, do not admit such separators. It has recently been shown that disk graphs do admit so-called clique-based separators that consist of O(√n) cliques. This result has been generalized to intersection graphs of various other types of disk-like objects. Unfortunately, segment intersection graphs do not admit small clique-based separators, because they can contain arbitrarily large bicliques. This is true even in the simple case of axis-aligned segments. In this paper we therefore introduce biclique-based separators (and, in particular, star-based separators), which are separators consisting of a small number of bicliques (or stars). We prove that any c-oriented set of n segments in the plane, where c is a constant, admits a star-based separator consisting of O(√n) stars. In fact, our result is more general, as it applies to any set of n pseudo-segments that is partitioned into c subsets such that the pseudo-segments in the same subset are pairwise disjoint. We extend our result to intersection graphs of c-oriented polygons. These results immediately lead to an almost-exact distance oracle for such intersection graphs, which has O(n√n) storage and O(√n) query time, and that can report the hop-distance between any two query nodes in the intersection graph with an additive error of at most 2. This is the first distance oracle for such types of intersection graphs that has subquadratic storage and sublinear query time and that only has an additive error.
Cite as

Mark de Berg, Bart M. P. Jansen, and Jeroen S. K. Lamme. Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2025.12,
  author =	{de Berg, Mark and Jansen, Bart M. P. and Lamme, Jeroen S. K.},
  title =	{{Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.12},
  URN =		{urn:nbn:de:0030-drops-249207},
  doi =		{10.4230/LIPIcs.ISAAC.2025.12},
  annote =	{Keywords: Computational geometry, intersection graphs, biclique-based separators, distance oracles}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.21
On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers

Authors: Parinya Chalermsook, Ly Orgo, and Minoo Zarsav

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
This paper considers the Zarankiewicz problem in bipartite graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). Let Z(n;k) be the maximum number of edges in a bipartite graph with n nodes and is free of a k-by-k biclique. Note that Z(n;k) ∈ Ω(nk) for all "natural" graph classes. Our first result reveals a separation between bipartite graphs of Ferrers dimension three and four: while we show that Z(n;k) ≤ 9n(k-1) for graphs of Ferrers dimension three, Z(n;k) ∈ Ω(n k ⋅ (log n)/(log log n)) for Ferrers dimension four graphs (Chan & Har-Peled, 2023) (Chazelle, 1990). To complement this, we derive a tight upper bound of 2n(k-1) for chordal bipartite graphs and 54n(k-1) for grid intersection graphs (GIG), a prominent graph class residing in four Ferrers dimensions and capturing planar bipartite graphs as well as bipartite intersection graphs of rectangles. Previously, the best-known bound for GIG was Z(n;k) ∈ O(2^{O(k)} n), implied by the results of Fox & Pach (2006) and Mustafa & Pach (2016). Our results advance and offer new insights into the interplay between Ferrers dimensions and extremal combinatorics.
Cite as

Parinya Chalermsook, Ly Orgo, and Minoo Zarsav. On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.GD.2025.21,
  author =	{Chalermsook, Parinya and Orgo, Ly and Zarsav, Minoo},
  title =	{{On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.21},
  URN =		{urn:nbn:de:0030-drops-250074},
  doi =		{10.4230/LIPIcs.GD.2025.21},
  annote =	{Keywords: Bipartite graph classes, extremal graph theory, geometric intersection graphs, Zarankiewicz problem, bicliques}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.78
Testing Depth First Search Numbering

Authors: Artur Czumaj, Christian Sohler, and Stefan Walzer

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Property Testing is a formal framework to study the computational power and complexity of sampling from combinatorial objects. A central goal in standard graph property testing is to understand which graph properties are testable with sublinear query complexity. Here, a graph property P is testable with a sublinear query complexity if there is an algorithm that makes a sublinear number of queries to the input graph and accepts with probability at least 2/3, if the graph has property P, and rejects with probability at least 2/3 if it is ε-far from every graph that has property P. In this paper, we introduce a new variant of the bounded degree graph model. In this variant, in addition to the standard representation of a bounded degree graph, we assume that every vertex v has a unique label num(v) from {1, … , |V|}, and in addition to the standard queries in the bounded degree graph model, we also allow a property testing algorithm to query for the label of a vertex (but not for a vertex with a given label). Our new model is motivated by certain graph processes such as a DFS traversal, which assign consecutive numbers (labels) to the vertices of the graph. We want to study which of these numberings can be tested in sublinear time. As a first step in understanding such a model, we develop a property testing algorithm for discovery times of a DFS traversal with query complexity O(n^{1/3}/ε) and for constant ε > 0 we give a matching lower bound.
Cite as

Artur Czumaj, Christian Sohler, and Stefan Walzer. Testing Depth First Search Numbering. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 78:1-78:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{czumaj_et_al:LIPIcs.ESA.2025.78,
  author =	{Czumaj, Artur and Sohler, Christian and Walzer, Stefan},
  title =	{{Testing Depth First Search Numbering}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{78:1--78:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.78},
  URN =		{urn:nbn:de:0030-drops-245466},
  doi =		{10.4230/LIPIcs.ESA.2025.78},
  annote =	{Keywords: Randomized Algorithms, Graph Algorithms, Property Testing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.22
Constructing Long Paths in Graph Streams

Authors: Christian Konrad and Chhaya Trehan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In the graph stream model of computation, an algorithm processes the edges of an n-vertex input graph in one or more sequential passes while using a memory that is sublinear in the input size. The streaming model poses significant challenges for algorithmically constructing long paths. Many known algorithms that are tasked with extending an existing path as a subroutine require an entire pass over the input to add a single additional edge. This raises a fundamental question: Are multiple passes inherently necessary to construct paths of non-trivial lengths, or can a single pass suffice? To address this question, we systematically study the Longest Path problem in the one-pass streaming model. In this problem, given a desired approximation factor α, the objective is to compute a path of length at least lp(G)/α, where lp(G) is the length of a longest path in the input graph G. We study the problem in the insertion-only and the insertion-deletion streaming models, and we give algorithms as well as space lower bounds for both undirected and directed graphs. Our results are: 1) We show that for undirected graphs, in both the insertion-only and the insertion-deletion models, there are semi-streaming algorithms, i.e., algorithms that use space O(n poly log n), that compute a path of length at least d/3 with high probability, where d is the average degree of the input graph. These algorithms can also yield an α-approximation to Longest Path using space Õ(n²/α). 2) Next, we show that such a result cannot be achieved for directed graphs, even in the insertion-only model. We show that computing a (n^{1-o(1)})-approximation to Longest Path in directed graphs in the insertion-only model requires space Ω(n²). This result is in line with recent results that demonstrate that processing directed graphs is often significantly harder than undirected graphs in the streaming model. 3) We further complement our results with two additional lower bounds. First, we show that semi-streaming space is insufficient for small constant factor approximations to Longest Path for undirected graphs in the insertion-only model. Last, in undirected graphs in the insertion-deletion model, we show that computing an α-approximation requires space Ω(n²/α³).
Cite as

Christian Konrad and Chhaya Trehan. Constructing Long Paths in Graph Streams. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.ESA.2025.22,
  author =	{Konrad, Christian and Trehan, Chhaya},
  title =	{{Constructing Long Paths in Graph Streams}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.22},
  URN =		{urn:nbn:de:0030-drops-244902},
  doi =		{10.4230/LIPIcs.ESA.2025.22},
  annote =	{Keywords: Longest Path Problem, Streaming Algorithms, One-way Two-party Communication Complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.84
Property Testing of Curve Similarity

Authors: Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, and Sampson Wong

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is given access to the input curves via a query oracle: a query returns the set of vertices of the curve that lie within a radius δ of a specified vertex of the other curve. The goal is to use a small number of queries to determine with constant probability whether the two curves are similar (i.e., their discrete Fréchet distance is at most δ) or they are "ε-far" (for 0 < ε < 2) from being similar, i.e., more than an ε-fraction of the two curves must be ignored for them to become similar. We present two algorithms which are sublinear assuming that the curves are t-approximate shortest paths in the ambient metric space, for some t ≪ n. The first algorithm uses O(t/ε log t/ε) queries and is given the value of t in advance. The second algorithm does not have explicit knowledge of the value of t and therefore needs to gain implicit knowledge of the straightness of the input curves through its queries. We show that the discrete Fréchet distance can still be tested using roughly O({t³+t² log n}/ε) queries ignoring logarithmic factors in t. Our algorithms work in a matrix representation of the input and may be of independent interest to matrix testing. Our algorithms use a mild uniform sampling condition that constrains the edge lengths of the curves, similar to a polynomially bounded aspect ratio. Applied to testing the continuous Fréchet distance of t-straight curves, our algorithms can be used for (1+ε')-approximate testing using essentially the same bounds as stated above with an additional factor of poly(1/(ε')).
Cite as

Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, and Sampson Wong. Property Testing of Curve Similarity. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ESA.2025.84,
  author =	{Afshani, Peyman and Buchin, Maike and Driemel, Anne and Richter, Marena and Wong, Sampson},
  title =	{{Property Testing of Curve Similarity}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{84:1--84:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.84},
  URN =		{urn:nbn:de:0030-drops-245522},
  doi =		{10.4230/LIPIcs.ESA.2025.84},
  annote =	{Keywords: Fr\'{e}chet distance, Trajectory Analysis, Curve Similarity, Property Testing, Monotonicity Testing}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.64
Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication

Authors: Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan

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

Abstract
We show that for a randomly sampled unsatisfiable O(log n)-CNF over n variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in n.
Cite as

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, and Weiqiang Yuan. Searching for Falsified Clause in Random (log{n})-CNFs Is Hard for Randomized Communication. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 64:1-64:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{riazanov_et_al:LIPIcs.APPROX/RANDOM.2025.64,
  author =	{Riazanov, Artur and Sofronova, Anastasia and Sokolov, Dmitry and Yuan, Weiqiang},
  title =	{{Searching for Falsified Clause in Random (log\{n\})-CNFs Is Hard for Randomized Communication}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{64:1--64:17},
  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.64},
  URN =		{urn:nbn:de:0030-drops-244306},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.64},
  annote =	{Keywords: communication complexity, proof complexity, random CNF}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.32
Quantum Property Testing in Sparse Directed Graphs

Authors: Simon Apers, Frédéric Magniez, Sayantan Sen, and Dániel Szabó

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

Abstract
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model, the problem of testing k-star-freeness, and more generally k-source-subgraph-freeness, is almost maximally hard for large k. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we show that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the k-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of 3-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.
Cite as

Simon Apers, Frédéric Magniez, Sayantan Sen, and Dániel Szabó. Quantum Property Testing in Sparse Directed Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 32:1-32:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.APPROX/RANDOM.2025.32,
  author =	{Apers, Simon and Magniez, Fr\'{e}d\'{e}ric and Sen, Sayantan and Szab\'{o}, D\'{a}niel},
  title =	{{Quantum Property Testing in Sparse Directed Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{32:1--32:24},
  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.32},
  URN =		{urn:nbn:de:0030-drops-243987},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.32},
  annote =	{Keywords: property testing, quantum computing, bounded-degree directed graphs, dual polynomial method, collision finding}
}
  • Refine by Type
  • 34 Document/PDF
  • 29 Document/HTML

  • Refine by Publication Year
  • 7 2026
  • 22 2025
  • 1 2022
  • 2 2021
  • 1 2020
  • Show More...

  • Refine by Author
  • 4 Newman, Ilan
  • 3 Varma, Nithin
  • 2 Driemel, Anne
  • 1 Afshani, Peyman
  • 1 Amir, Noga
  • Show More...

  • Refine by Series/Journal
  • 34 LIPIcs

  • Refine by Classification
  • 9 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 5 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Computational geometry
  • 3 Theory of computation → Communication complexity
  • 2 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 3 Graph Algorithms
  • 3 Property Testing
  • 3 Property testing
  • 3 property testing
  • 2 Query Complexity
  • 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