3 Search Results for "Kalemaj, Iden"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.25
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

Authors: Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions f:{0,1}^d → ℝ. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function f over an arbitrary partially ordered domain as a collection of Boolean functions over the same domain, roughly capturing the distance of f to monotonicity and the structure of violations of f to monotonicity. We apply our generalized isoperimetric inequality to improve algorithms for testing monotonicity and approximating the distance to monotonicity for real-valued functions. Our tester for monotonicity has query complexity Õ(min(r √d,d)), where r is the size of the image of the input function. (The best previously known tester makes O(d) queries, as shown by Chakrabarty and Seshadhri (STOC 2013).) Our tester is nonadaptive and has 1-sided error. We prove a matching lower bound for nonadaptive, 1-sided error testers for monotonicity. We also show that the distance to monotonicity of real-valued functions that are α-far from monotone can be approximated nonadaptively within a factor of O(√{d log d}) with query complexity polynomial in 1/α and the dimension d. This query complexity is known to be nearly optimal for nonadaptive algorithms even for the special case of Boolean functions. (The best previously known distance approximation algorithm for real-valued functions, by Fattal and Ron (TALG 2010) achieves O(d log r)-approximation.)
Cite as

Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 25:1-25:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{black_et_al:LIPIcs.ICALP.2023.25,
  author =	{Black, Hadley and Kalemaj, Iden and Raskhodnikova, Sofya},
  title =	{{Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel 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.2023.25},
  URN =		{urn:nbn:de:0030-drops-180774},
  doi =		{10.4230/LIPIcs.ICALP.2023.25},
  annote =	{Keywords: Isoperimetric inequalities, property testing, monotonicity testing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.52
Triangle Counting with Local Edge Differential Privacy

Authors: Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, and Adam Smith

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study triangle counting in the noninteractive and interactive local model with edge differential privacy (that, intuitively, requires that the outputs of the algorithm on graphs that differ in one edge be indistinguishable). In this model, each party’s local view consists of the adjacency list of one vertex. In the noninteractive model, we prove that additive Ω(n²) error is necessary, where n is the number of nodes. This lower bound is our main technical contribution. It uses a reconstruction attack with a new class of linear queries and a novel mix-and-match strategy of running the local randomizers with different completions of their adjacency lists. It matches the additive error of the algorithm based on Randomized Response, proposed by Imola, Murakami and Chaudhuri (USENIX2021) and analyzed by Imola, Murakami and Chaudhuri (CCS2022) for constant ε. We use a different postprocessing of Randomized Response and provide tight bounds on the variance of the resulting algorithm. In the interactive setting, we prove a lower bound of Ω(n^{3/2}) on the additive error. Previously, no hardness results were known for interactive, edge-private algorithms in the local model, except for those that follow trivially from the results for the central model. Our work significantly improves on the state of the art in differentially private graph analysis in the local model.
Cite as

Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, and Adam Smith. Triangle Counting with Local Edge Differential Privacy. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 52:1-52:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.ICALP.2023.52,
  author =	{Eden, Talya and Liu, Quanquan C. and Raskhodnikova, Sofya and Smith, Adam},
  title =	{{Triangle Counting with Local Edge Differential Privacy}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{52:1--52:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel 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.2023.52},
  URN =		{urn:nbn:de:0030-drops-181048},
  doi =		{10.4230/LIPIcs.ICALP.2023.52},
  annote =	{Keywords: local differential privacy, reconstruction attacks, lower bounds, triangle counting}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.90
Sublinear-Time Computation in the Presence of Online Erasures

Authors: Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We initiate the study of sublinear-time algorithms that access their input via an online adversarial erasure oracle. After answering each query to the input object, such an oracle can erase t input values. Our goal is to understand the complexity of basic computational tasks in extremely adversarial situations, where the algorithm’s access to data is blocked during the execution of the algorithm in response to its actions. Specifically, we focus on property testing in the model with online erasures. We show that two fundamental properties of functions, linearity and quadraticity, can be tested for constant t with asymptotically the same complexity as in the standard property testing model. For linearity testing, we prove tight bounds in terms of t, showing that the query complexity is Θ(log t). In contrast to linearity and quadraticity, some other properties, including sortedness and the Lipschitz property of sequences, cannot be tested at all, even for t = 1. Our investigation leads to a deeper understanding of the structure of violations of linearity and other widely studied properties.
Cite as

Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma. Sublinear-Time Computation in the Presence of Online Erasures. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 90:1-90:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kalemaj_et_al:LIPIcs.ITCS.2022.90,
  author =	{Kalemaj, Iden and Raskhodnikova, Sofya and Varma, Nithin},
  title =	{{Sublinear-Time Computation in the Presence of Online Erasures}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{90:1--90:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.90},
  URN =		{urn:nbn:de:0030-drops-156867},
  doi =		{10.4230/LIPIcs.ITCS.2022.90},
  annote =	{Keywords: Randomized algorithms, property testing, Fourier analysis, linear functions, quadratic functions, Lipschitz and monotone functions, sorted sequences}
}
  • Refine by Author
  • 3 Raskhodnikova, Sofya
  • 2 Kalemaj, Iden
  • 1 Black, Hadley
  • 1 Eden, Talya
  • 1 Liu, Quanquan C.
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 property testing
  • 1 Fourier analysis
  • 1 Isoperimetric inequalities
  • 1 Lipschitz and monotone functions
  • 1 Randomized algorithms
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2023
  • 1 2022

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact