Search Results

Documents authored by Shapira, Asaf

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.46
Testing Versus Estimation of Graph Properties, Revisited

Authors: Lior Gishboliner, Nick Kushnir, and Asaf Shapira

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

Abstract
A graph G on n vertices is ε-far from property P if one should add/delete at least ε n² edges to turn G into a graph satisfying P. A distance estimator for P is an algorithm that given G and α, ε > 0 distinguishes between the case that G is (α-ε)-close to 𝒫 and the case that G is α-far from 𝒫. If P has a distance estimator whose query complexity depends only on ε, then P is said to be estimable. Every estimable property is clearly also testable, since testing corresponds to estimating with α = ε. A central result in the area of property testing is the Fischer-Newman theorem, stating that an inverse statement also holds, that is, that every testable property is in fact estimable. The proof of Fischer and Newmann was highly ineffective, since it incurred a tower-type loss when transforming a testing algorithm for P into a distance estimator. This raised the natural problem, studied recently by Fiat-Ron and by Hoppen-Kohayakawa-Lang-Lefmann-Stagni, whether one can find a transformation with a polynomial loss. We obtain the following results. - We show that if P is hereditary, then one can turn a tester for P into a distance estimator with an exponential loss. This is an exponential improvement over the result of Hoppen et. al., who obtained a transformation with a double exponential loss. - We show that for every P, one can turn a testing algorithm for P into a distance estimator with a double exponential loss. This improves over the transformation of Fischer-Newman that incurred a tower-type loss. Our main conceptual contribution in this work is that we manage to turn the approach of Fischer-Newman, which was inherently ineffective, into an efficient one. On the technical level, our main contribution is in establishing certain properties of Frieze-Kannan Weak Regular partitions that are of independent interest.
Cite as

Lior Gishboliner, Nick Kushnir, and Asaf Shapira. Testing Versus Estimation of Graph Properties, Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 46:1-46:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gishboliner_et_al:LIPIcs.APPROX/RANDOM.2023.46,
  author =	{Gishboliner, Lior and Kushnir, Nick and Shapira, Asaf},
  title =	{{Testing Versus Estimation of Graph Properties, Revisited}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{46:1--46:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.46},
  URN =		{urn:nbn:de:0030-drops-188713},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.46},
  annote =	{Keywords: Testing, estimation, weak regularity, randomized algorithms, graph theory, Frieze-Kannan Regularity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.43
Testing Linear Inequalities of Subgraph Statistics

Authors: Lior Gishboliner, Asaf Shapira, and Henrique Stagni

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Property testers are fast randomized algorithms whose task is to distinguish between inputs satisfying some predetermined property ? and those that are far from satisfying it. Since these algorithms operate by inspecting a small randomly selected portion of the input, the most natural property one would like to be able to test is whether the input does not contain certain forbidden small substructures. In the setting of graphs, such a result was obtained by Alon et al., who proved that for any finite family of graphs ℱ, the property of being induced ℱ-free (i.e. not containing an induced copy of any F ∈ ℱ) is testable. It is natural to ask if one can go one step further and prove that more elaborate properties involving induced subgraphs are also testable. One such generalization of the result of Alon et al. was formulated by Goldreich and Shinkar who conjectured that for any finite family of graphs ℱ, and any linear inequality involving the densities of the graphs F ∈ ℱ in the input graph, the property of satisfying this inequality can be tested in a certain restricted model of graph property testing. Our main result in this paper disproves this conjecture in the following strong form: some properties of this type are not testable even in the classical (i.e. unrestricted) model of graph property testing. The proof deviates significantly from prior non-testability results in this area. The main idea is to use a linear inequality relating induced subgraph densities in order to encode the property of being a pseudo-random graph.
Cite as

Lior Gishboliner, Asaf Shapira, and Henrique Stagni. Testing Linear Inequalities of Subgraph Statistics. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 43:1-43:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gishboliner_et_al:LIPIcs.ITCS.2020.43,
  author =	{Gishboliner, Lior and Shapira, Asaf and Stagni, Henrique},
  title =	{{Testing Linear Inequalities of Subgraph Statistics}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{43:1--43:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.43},
  URN =		{urn:nbn:de:0030-drops-117287},
  doi =		{10.4230/LIPIcs.ITCS.2020.43},
  annote =	{Keywords: graph property testing, subgraph statistics}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.54
Efficient Testing without Efficient Regularity

Authors: Lior Gishboliner and Asaf Shapira

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
The regularity lemma of Szemeredi turned out to be the most powerful tool for studying the testability of graph properties in the dense graph model. In fact, as we argue in this paper, this lemma can be used in order to prove (essentially) all the previous results in this area. More precisely, a barrier for obtaining an efficient testing algorithm for a graph property P was having an efficient regularity lemma for graphs satisfying P. The problem is that for many natural graph properties (e.g. triangle freeness) it is known that a graph can satisfy P and still only have regular partitions of tower-type size. This means that there was no viable path for obtaining reasonable bounds on the query complexity of testing such properties. In this paper we consider the property of being induced C_4-free, which also suffers from the fact that a graph might satisfy this property but still have only regular partitions of tower-type size. By developing a new approach for this problem we manage to overcome this barrier and thus obtain a merely exponential bound for testing this property. This is the first substantial progress on a problem raised by Alon in 2001, and more recently by Alon, Conlon and Fox. We thus obtain the first example of an efficient testing algorithm that cannot be derived from an efficient version of the regularity lemma.
Cite as

Lior Gishboliner and Asaf Shapira. Efficient Testing without Efficient Regularity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gishboliner_et_al:LIPIcs.ITCS.2018.54,
  author =	{Gishboliner, Lior and Shapira, Asaf},
  title =	{{Efficient Testing without Efficient Regularity}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.54},
  URN =		{urn:nbn:de:0030-drops-83124},
  doi =		{10.4230/LIPIcs.ITCS.2018.54},
  annote =	{Keywords: Property testing, Induced C\underline4-freeness}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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