Search Results

Documents authored by Sen, Sayantan

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.27
Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing

Authors: Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen

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

Abstract
The framework of distribution testing is currently ubiquitous in the field of property testing. In this model, the input is a probability distribution accessible via independently drawn samples from an oracle. The testing task is to distinguish a distribution that satisfies some property from a distribution that is far in some distance measure from satisfying it. The task of tolerant testing imposes a further restriction, that distributions close to satisfying the property are also accepted. This work focuses on the connection between the sample complexities of non-tolerant testing of distributions and their tolerant testing counterparts. When limiting our scope to label-invariant (symmetric) properties of distributions, we prove that the gap is at most quadratic, ignoring poly-logarithmic factors. Conversely, the property of being the uniform distribution is indeed known to have an almost-quadratic gap. When moving to general, not necessarily label-invariant properties, the situation is more complicated, and we show some partial results. We show that if a property requires the distributions to be non-concentrated, that is, the probability mass of the distribution is sufficiently spread out, then it cannot be non-tolerantly tested with o(√n) many samples, where n denotes the universe size. Clearly, this implies at most a quadratic gap, because a distribution can be learned (and hence tolerantly tested against any property) using 𝒪(n) many samples. Being non-concentrated is a strong requirement on properties, as we also prove a close to linear lower bound against their tolerant tests. Apart from the case where the distribution is non-concentrated, we also show if an input distribution is very concentrated, in the sense that it is mostly supported on a subset of size s of the universe, then it can be learned using only 𝒪(s) many samples. The learning procedure adapts to the input, and works without knowing s in advance.
Cite as

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen. Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 27:1-27:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.APPROX/RANDOM.2022.27,
  author =	{Chakraborty, Sourav and Fischer, Eldar and Ghosh, Arijit and Mishra, Gopinath and Sen, Sayantan},
  title =	{{Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{27:1--27:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.27},
  URN =		{urn:nbn:de:0030-drops-171497},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.27},
  annote =	{Keywords: Distribution Testing, Tolerant Testing, Non-tolerant Testing, Sample Complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.69
Tolerant Bipartiteness Testing in Dense Graphs

Authors: Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, and Sayantan Sen

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser, and Ron. Though the non-tolerant version of bipartite testing has been extensively studied in the literature, the tolerant variant is not well understood. In this paper, we consider the following version of tolerant bipartite testing problem: Given two parameters ε, δ ∈ (0,1), with δ > ε, and access to the adjacency matrix of a graph G, we have to decide whether G can be made bipartite by editing at most ε n² entries of the adjacency matrix of G, or we have to edit at least δ n² entries of the adjacency matrix to make G bipartite. In this paper, we prove that for δ = (2+Ω(1))ε, tolerant bipartite testing can be decided by performing 𝒪̃(1/ε³) many adjacency queries and in 2^𝒪̃(1/ε) time complexity. This improves upon the state-of-the-art query and time complexities of this problem of 𝒪̃(1/ε⁶) and 2^𝒪̃(1/ε²), respectively, due to Alon, Fernandez de la Vega, Kannan and Karpinski, where 𝒪̃(⋅) hides a factor polynomial in log (1/ε).
Cite as

Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, and Sayantan Sen. Tolerant Bipartiteness Testing in Dense Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 69:1-69:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.ICALP.2022.69,
  author =	{Ghosh, Arijit and Mishra, Gopinath and Raychaudhury, Rahul and Sen, Sayantan},
  title =	{{Tolerant Bipartiteness Testing in Dense Graphs}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{69:1--69:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.69},
  URN =		{urn:nbn:de:0030-drops-164101},
  doi =		{10.4230/LIPIcs.ICALP.2022.69},
  annote =	{Keywords: Tolerant Testing, Bipartite Testing, Query Complexity, Graph Property Testing}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.34
Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds

Authors: Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen

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

Abstract
The graph isomorphism distance between two graphs G_u and G_k is the fraction of entries in the adjacency matrix that has to be changed to make G_u isomorphic to G_k. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in the query model. In other words, if G_k is a known graph and G_u is an unknown graph whose adjacency matrix has to be accessed by querying the entries, what is the query complexity for testing whether the graph isomorphism distance between G_u and G_k is less than γ₁ or more than γ₂, where γ₁ and γ₂ are two constants with 0 ≤ γ₁ < γ₂ ≤ 1. It is also called the tolerant property testing of graph isomorphism in the dense graph model. The non-tolerant version (where γ₁ is 0) has been studied by Fischer and Matsliah (SICOMP'08). In this paper, we prove a (interesting) connection between tolerant graph isomorphism testing and tolerant testing of the well studied Earth Mover’s Distance (EMD). We prove that deciding tolerant graph isomorphism is equivalent to deciding tolerant EMD testing between multi-sets in the query setting. Moreover, the reductions between tolerant graph isomorphism and tolerant EMD testing (in query setting) can also be extended directly to work in the two party Alice-Bob communication model (where Alice and Bob have one graph each and they want to solve tolerant graph isomorphism problem by communicating bits), and possibly in other sublinear models as well. Testing tolerant EMD between two probability distributions is equivalent to testing EMD between two multi-sets, where the multiplicity of each element is taken appropriately, and we sample elements from the unknown multi-set with replacement. In this paper, our (main) contribution is to introduce the problem of {(tolerant) EMD testing between multi-sets (over Hamming cube) when we get samples from the unknown multi-set without replacement} and to show that this variant of tolerant testing of EMD is as hard as tolerant testing of graph isomorphism between two graphs. {Thus, while testing of equivalence between distributions is at the heart of the non-tolerant testing of graph isomorphism, we are showing that the estimation of the EMD over a Hamming cube (when we are allowed to sample without replacement) is at the heart of tolerant graph isomorphism.} We believe that the introduction of the problem of testing EMD between multi-sets (when we get samples without replacement) opens an entirely new direction in the world of testing properties of distributions.
Cite as

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen. Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.APPROX/RANDOM.2021.34,
  author =	{Chakraborty, Sourav and Ghosh, Arijit and Mishra, Gopinath and Sen, Sayantan},
  title =	{{Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{34:1--34:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.34},
  URN =		{urn:nbn:de:0030-drops-147273},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.34},
  annote =	{Keywords: Graph Isomorphism, Earth Mover Distance, Query Complexity}
}
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 About DROPS Imprint Privacy Contact