4 Search Results for "Dixit, Kashyap"

Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2025.2
Let’s Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation (Invited Talk)

Authors: Dana Ron

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
This short paper accompanies an invited talk given at ICALP2025. It is an informal, high-level presentation of tolerant testing and distance approximation. It includes some general results as well as a few specific ones, with the aim of providing a taste of this research direction within the area of sublinear algorithms.
Cite as

Dana Ron. Let’s Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation (Invited Talk). In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ron:LIPIcs.ICALP.2025.2,
  author =	{Ron, Dana},
  title =	{{Let’s Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{2:1--2:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.2},
  URN =		{urn:nbn:de:0030-drops-233798},
  doi =		{10.4230/LIPIcs.ICALP.2025.2},
  annote =	{Keywords: Sublinear Algorithms, Tolerant Property Testing, Distance Approximation}
}
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
DOI: 10.4230/LIPIcs.ITCS.2025.34
Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing

Authors: Deeparnab Chakrabarty and C. Seshadhri

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

Abstract
Motivated by applications to monotonicity testing, Lehman and Ron (JCTA, 2001) proved the existence of a collection of vertex disjoint paths between comparable sub-level sets in the directed hypercube. The main technical contribution of this paper is a new proof method that yields a generalization of their theorem: we prove the existence of two edge-disjoint collections of vertex disjoint paths. Our main conceptual contributions are conjectures on directed hypercube flows with simultaneous vertex and edge capacities of which our generalized Lehman-Ron theorem is a special case. We show that these conjectures imply directed isoperimetric theorems, and in particular, the robust directed Talagrand inequality due to Khot, Minzer, and Safra (SIAM J. on Comp, 2018). These isoperimetric inequalities, that relate the directed surface area (of a set in the hypercube) to its distance to monotonicity, have been crucial in obtaining the best monotonicity testers for Boolean functions. We believe our conjectures pave the way towards combinatorial proofs of these directed isoperimetry theorems.
Cite as

Deeparnab Chakrabarty and C. Seshadhri. Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.ITCS.2025.34,
  author =	{Chakrabarty, Deeparnab and Seshadhri, C.},
  title =	{{Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{34:1--34:15},
  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.34},
  URN =		{urn:nbn:de:0030-drops-226623},
  doi =		{10.4230/LIPIcs.ITCS.2025.34},
  annote =	{Keywords: Monotonicity testing, isoperimetric inequalities, hypercube routing}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.91
Erasure-Resilient Property Testing

Authors: Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Property testers form an important class of sublinear algorithms. In the standard property testing model, an algorithm accesses the input function f:D -> R via an oracle. With very few exceptions, all property testers studied in this model rely on the oracle to provide function values at all queried domain points. However, in many realistic situations, the oracle may be unable to reveal the function values at some domain points due to privacy concerns, or when some of the values get erased by mistake or by an adversary. The testers do not learn anything useful about the property by querying those erased points. Moreover, the knowledge of a tester may enable an adversary to erase some of the values so as to increase the query complexity of the tester arbitrarily or, in some cases, make the tester entirely useless. In this work, we initiate a study of property testers that are resilient to the presence of adversarially erased function values. An alpha-erasure-resilient epsilon-tester is given parameters alpha, epsilon in (0,1), along with oracle access to a function f such that at most an alpha fraction of function values have been erased. The tester does not know whether a value is erased until it queries the corresponding domain point. The tester has to accept with high probability if there is a way to assign values to the erased points such that the resulting function satisfies the desired property P. It has to reject with high probability if, for every assignment of values to the erased points, the resulting function has to be changed in at least an epsilon-fraction of the non-erased domain points to satisfy P. We design erasure-resilient property testers for a large class of properties. For some properties, it is possible to obtain erasure-resilient testers by simply using standard testers as a black box. However, there are more challenging properties for which all known testers rely on querying a specific point. If this point is erased, all these testers break. We give efficient erasure-resilient testers for several important classes of such properties of functions including monotonicity, the Lipschitz property, and convexity. Finally, we show a separation between the standard testing and erasure-resilient testing. Specifically, we describe a property that can be epsilon-tested with O(1/epsilon) queries in the standard model, whereas testing it in the erasure-resilient model requires number of queries polynomial in the input size.
Cite as

Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma. Erasure-Resilient Property Testing. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 91:1-91:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{dixit_et_al:LIPIcs.ICALP.2016.91,
  author =	{Dixit, Kashyap and Raskhodnikova, Sofya and Thakurta, Abhradeep and Varma, Nithin},
  title =	{{Erasure-Resilient Property Testing}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{91:1--91:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.91},
  URN =		{urn:nbn:de:0030-drops-61947},
  doi =		{10.4230/LIPIcs.ICALP.2016.91},
  annote =	{Keywords: Randomized algorithms, property testing, error correction, monotoneand Lipschitz functions}
}
  • Refine by Type
  • 4 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2016

  • Refine by Author
  • 2 Raskhodnikova, Sofya
  • 1 Chakrabarty, Deeparnab
  • 1 Dixit, Kashyap
  • 1 Kelman, Esty
  • 1 Linder, Ephraim
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 1 Distance Approximation
  • 1 Monotonicity testing
  • 1 Offline Adversary
  • 1 Online Adversary
  • 1 Property Testing
  • 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact