7 Search Results for "Peter, Naty"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.60
Space-Efficient Approximate Spherical Range Counting in High Dimensions

Authors: Andreas Kalavas and Ioannis Psarros

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

Abstract
We study the following range searching problem in high-dimensional Euclidean spaces: given a finite set P ⊂ ℝ^d, where each p ∈ P is assigned a weight w_p, and radius r > 0, we need to preprocess P into a data structure such that when a new query point q ∈ ℝ^d arrives, the data structure reports the cumulative weight of points of P within Euclidean distance r from q. Solving the problem exactly seems to require space usage that is exponential to the dimension, a phenomenon known as the curse of dimensionality. Thus, we focus on approximate solutions where points up to (1+ε)r away from q may be taken into account, where ε > 0 is an input parameter known during preprocessing. We build a data structure with near-linear space usage, and query time in n^{1-Θ(ε⁴/log(1/ε))}+t_q^ϱ⋅n^{1-ϱ}, for some ϱ = Θ(ε²), where t_q is the number of points of P in the ambiguity zone, i.e., at distance between r and (1+ε)r from the query q. To the best of our knowledge, this is the first data structure with efficient space usage (subquadratic or near-linear for any ε > 0) and query time that remains sublinear for any sublinear t_q. We supplement our worst-case bounds with a query-driven preprocessing algorithm to build data structures that are well-adapted to the query distribution.
Cite as

Andreas Kalavas and Ioannis Psarros. Space-Efficient Approximate Spherical Range Counting in High Dimensions. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kalavas_et_al:LIPIcs.SoCG.2026.60,
  author =	{Kalavas, Andreas and Psarros, Ioannis},
  title =	{{Space-Efficient Approximate Spherical Range Counting in High Dimensions}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{60:1--60: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.60},
  URN =		{urn:nbn:de:0030-drops-258670},
  doi =		{10.4230/LIPIcs.SoCG.2026.60},
  annote =	{Keywords: Approximate range counting, partition trees, high dimensions}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.11
New Results in Share Conversion, with Applications to Evolving Access Structures

Authors: Tamar Ben David, Varun Narayanan, Olga Nissenbaum, and Anat Paskin-Cherniavsky

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
We say there is a share conversion from a secret-sharing scheme Π to another scheme Π' implementing the same access structure if each party can locally apply a deterministic function to their share to transform any valid secret-sharing under Π to a valid (but not necessarily random) secret-sharing under Π' of the same secret. If such a conversion exists, we say that Π ≥ Π'. This notion was introduced by Cramer et al. (TCC'05), where they particularly proved that for any access structure, any linear secret-sharing scheme over a given field 𝔽, has a conversion from a CNF scheme, and is convertible to a DNF scheme. In this work, we initiate a systematic study of convertability between secret-sharing schemes, and present a number of results with implications to the understanding of the convertibility landscape. - In the context of linear schemes, we present two key theorems providing necessary conditions for convertibility, proved using linear-algebraic tools. It has several implications, such as the fact that Shamir secret-sharing scheme can be neither maximal or minimal. Another implication of it is that a scheme may be minimal if its share complexity is at least as high as that of DNF. - Our second key result is a necessary condition for convertibility to CNF from a broad class of (not necessarily linear) schemes. This result is proved via information-theoretic techniques and implies non-maximality for schemes with share complexity smaller than that of CNF. We also provide a condition which is both necessary and sufficient for the existence of a share conversion to some linear scheme. The condition is stated as a system of linear equations, such that a conversion exists if and only if a solution to the linear system exists. We note that the impossibility results for linear schemes may be viewed as identifying a subset of contradicting equations in the system. Another contribution of our paper, is in defining and studying share conversion for evolving secret-sharing schemes. In such a schemes, recently introduced by Komargodski et al. {(IEEE ToIT'18)}, the number of parties is not bounded apriori, and every party receives a share as it arrives, which never changes in the sequel. Our impossibility results have implications to the evolving setting as well. Interestingly, unlike in the standard setting, there is no maximum or minimum in a broad class of evolving schemes, even without any restriction on the share size. Finally, we show that, generally, there is no conversion between additive schemes over different fields, even from CNF to DNF! However by relaxing from perfect to statistical security, it may be possible to convert, and exemplify this for (n,n)-threshold access structures.
Cite as

Tamar Ben David, Varun Narayanan, Olga Nissenbaum, and Anat Paskin-Cherniavsky. New Results in Share Conversion, with Applications to Evolving Access Structures. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.ITC.2025.11,
  author =	{Ben David, Tamar and Narayanan, Varun and Nissenbaum, Olga and Paskin-Cherniavsky, Anat},
  title =	{{New Results in Share Conversion, with Applications to Evolving Access Structures}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.11},
  URN =		{urn:nbn:de:0030-drops-243610},
  doi =		{10.4230/LIPIcs.ITC.2025.11},
  annote =	{Keywords: secret sharing, linear secret sharing, evolving access structures, share conversion, feasibility}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.11
CluStRE: Streaming Graph Clustering with Multi-Stage Refinement

Authors: Adil Chhabra, Shai Dorian Peretz, and Christian Schulz

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
We present CluStRE, a novel streaming graph clustering algorithm that balances computational efficiency with high-quality clustering using multi-stage refinement. Unlike traditional in-memory clustering approaches, CluStRE processes graphs in a streaming setting, significantly reducing memory overhead while leveraging re-streaming and evolutionary heuristics to improve solution quality. Our method dynamically constructs a quotient graph, enabling modularity-based optimization while efficiently handling large-scale graphs. We introduce multiple configurations of CluStRE to provide trade-offs between speed, memory consumption, and clustering quality. Experimental evaluations demonstrate that CluStRE improves solution quality by 89.8%, operates 2.6× faster, and uses less than two-thirds of the memory required by the state-of-the-art streaming clustering algorithm on average. Moreover, our strongest mode enhances solution quality by up to 150% on average. With this, CluStRE achieves comparable solution quality to in-memory algorithms, i.e. over 96% of the quality of clustering approaches, including Louvain, effectively bridging the gap between streaming and traditional clustering methods.
Cite as

Adil Chhabra, Shai Dorian Peretz, and Christian Schulz. CluStRE: Streaming Graph Clustering with Multi-Stage Refinement. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chhabra_et_al:LIPIcs.SEA.2025.11,
  author =	{Chhabra, Adil and Dorian Peretz, Shai and Schulz, Christian},
  title =	{{CluStRE: Streaming Graph Clustering with Multi-Stage Refinement}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra 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.SEA.2025.11},
  URN =		{urn:nbn:de:0030-drops-232493},
  doi =		{10.4230/LIPIcs.SEA.2025.11},
  annote =	{Keywords: graph clustering, community, streaming, online, memetic, evolutionary}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.19
Differential Privacy and Sublinear Time Are Incompatible Sometimes

Authors: Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu, and Tamalika Mukherjee

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

Abstract
Differential privacy and sublinear algorithms are both rapidly emerging algorithmic themes in times of big data analysis. Although recent works have shown the existence of differentially private sublinear algorithms for many problems including graph parameter estimation and clustering, little is known regarding hardness results on these algorithms. In this paper, we initiate the study of lower bounds for problems that aim for both differentially-private and sublinear-time algorithms. Our main result is the incompatibility of both the desiderata in the general case. In particular, we prove that a simple problem based on one-way marginals yields both a differentially-private algorithm, as well as a sublinear-time algorithm, but does not admit a "strictly" sublinear-time algorithm that is also differentially private.
Cite as

Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu, and Tamalika Mukherjee. Differential Privacy and Sublinear Time Are Incompatible Sometimes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blocki_et_al:LIPIcs.ITCS.2025.19,
  author =	{Blocki, Jeremiah and Fichtenberger, Hendrik and Grigorescu, Elena and Mukherjee, Tamalika},
  title =	{{Differential Privacy and Sublinear Time Are Incompatible Sometimes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{19:1--19: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.19},
  URN =		{urn:nbn:de:0030-drops-226473},
  doi =		{10.4230/LIPIcs.ITCS.2025.19},
  annote =	{Keywords: differential privacy, sublinear algorithms, sublinear-time algorithms, one-way marginals, lower bounds}
}
Document
DOI: 10.4230/OASIcs.Tannen.5
Chasing Parallelism in Aggregating Graph Queries

Authors: Alin Deutsch

Published in: OASIcs, Volume 119, The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen (2024)

Abstract
In practice, one frequently encounters queries that extract tabular results from graph databases by employing grouping and aggregation. This paper introduces a technique for rewriting the group-by list of graph queries in order to increase aggregation parallelism in graph engines that conform to a modern instantiation of the Bulk-Synchronous-Parallel computation model.
Cite as

Alin Deutsch. Chasing Parallelism in Aggregating Graph Queries. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{deutsch:OASIcs.Tannen.5,
  author =	{Deutsch, Alin},
  title =	{{Chasing Parallelism in Aggregating Graph Queries}},
  booktitle =	{The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen},
  pages =	{5:1--5:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-320-1},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{119},
  editor =	{Amarilli, Antoine and Deutsch, Alin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.5},
  URN =		{urn:nbn:de:0030-drops-201011},
  doi =		{10.4230/OASIcs.Tannen.5},
  annote =	{Keywords: Graph Databases, Grouping and Aggregation, Parallel Graph Computation Models, Rewriting, Constraint-based Minimization}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.8
Secret Sharing, Slice Formulas, and Monotone Real Circuits

Authors: Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, and Toniann Pitassi

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

Abstract
A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined "authorized" sets of parties can reconstruct the secret s, and all other "unauthorized" sets learn nothing about s. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size 2^{n-o(n)} and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to 2^{0.994n+o(n)}, and this was further improved by several follow-ups accumulating in an upper bound of 1.5^{n+o(n)} (Applebaum and Nir, CRYPTO 2021). Following these advances, it is natural to ask whether these new approaches can lead to a truly sub-exponential upper-bound of 2^{n^{1-ε}} for some constant ε > 0, or even all the way down to polynomial upper-bounds. In this paper, we relate this question to the complexity of computing monotone Boolean functions by monotone real circuits (MRCs) - a computational model that was introduced by Pudlák (J. Symb. Log., 1997) in the context of proof complexity. We introduce a new notion of "separable" MRCs that lies between monotone real circuits and monotone real formulas (MRFs). As our main results, we show that recent constructions of general secret-sharing schemes implicitly give rise to separable MRCs for general monotone functions of similar complexity, and that some monotone functions (in monotone NP) cannot be computed by sub-exponential size separable MRCs. Interestingly, it seems that proving similar lower-bounds for general MRCs is beyond the reach of current techniques. We use this connection to obtain lower-bounds against a natural family of secret-sharing schemes, as well as new non-trivial upper-bounds for MRCs. Specifically, we conclude that recent approaches for secret-sharing schemes cannot achieve sub-exponential share size and that every monotone function can be realized by an MRC (or even MRF) of complexity 1.5^{n+o(n)}. To the best of our knowledge, this is the first improvement over the trivial 2^{n-o(n)} upper-bound. Along the way, we show that the recent constructions of general secret-sharing schemes implicitly give rise to Boolean formulas over slice functions and prove that such formulas can be simulated by separable MRCs of similar size. On a conceptual level, our paper continues the rich line of study that relates the share size of secret-sharing schemes to monotone complexity measures.
Cite as

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, and Toniann Pitassi. Secret Sharing, Slice Formulas, and Monotone Real Circuits. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{applebaum_et_al:LIPIcs.ITCS.2022.8,
  author =	{Applebaum, Benny and Beimel, Amos and Nir, Oded and Peter, Naty and Pitassi, Toniann},
  title =	{{Secret Sharing, Slice Formulas, and Monotone Real Circuits}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{8:1--8:23},
  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.8},
  URN =		{urn:nbn:de:0030-drops-156046},
  doi =		{10.4230/LIPIcs.ITCS.2022.8},
  annote =	{Keywords: Secret Sharing Schemes, Monotone Real Circuits}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.13
One-One Constrained Pseudorandom Functions

Authors: Naty Peter, Rotem Tsabary, and Hoeteck Wee

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
We define and study a new cryptographic primitive, named One-One Constrained Pseudorandom Functions. In this model there are two parties, Alice and Bob, that hold a common random string K, where Alice in addition holds a predicate f:[N] → {0,1} and Bob in addition holds an input x ∈ [N]. We then let Alice generate a key K_f based on f and K, and let Bob evaluate a value K_x based on x and K. We consider a third party that sees the values (x,f,K_f) and the goal is to allow her to reconstruct K_x whenever f(x)=1, while keeping K_x pseudorandom whenever f(x)=0. This primitive can be viewed as a relaxation of constrained PRFs, such that there is only a single key query and a single evaluation query. We focus on the information-theoretic setting, where the one-one cPRF has perfect correctness and perfect security. Our main results are as follows. 1) A Lower Bound. We show that in the information-theoretic setting, any one-one cPRF for punctured predicates is of exponential complexity (and thus the lower bound meets the upper bound that is given by a trivial construction). This stands in contrast with the well known GGM-based punctured PRF from OWF, which is in particular a one-one cPRF. This also implies a similar lower bound for all NC1. 2) New Constructions. On the positive side, we present efficient information-theoretic constructions of one-one cPRFs for a few other predicate families, such as equality predicates, inner-product predicates, and subset predicates. We also show a generic AND composition lemma that preserves complexity. 3) An Amplification to standard cPRF. We show that all of our one-one cPRF constructions can be amplified to a standard (single-key) cPRF via any key-homomorphic PRF that supports linear computations. More generally, we suggest a new framework that we call the double-key model which allows to construct constrained PRFs via key-homomorphic PRFs. 4) Relation to CDS. We show that one-one constrained PRFs imply conditional disclosure of secrets (CDS) protocols. We believe that this simple model can be used to better understand constrained PRFs and related cryptographic primitives, and that further applications of one-one constrained PRFs and our double-key model will be found in the future, in addition to those we show in this paper.
Cite as

Naty Peter, Rotem Tsabary, and Hoeteck Wee. One-One Constrained Pseudorandom Functions. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{peter_et_al:LIPIcs.ITC.2020.13,
  author =	{Peter, Naty and Tsabary, Rotem and Wee, Hoeteck},
  title =	{{One-One Constrained Pseudorandom Functions}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{13:1--13:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.13},
  URN =		{urn:nbn:de:0030-drops-121188},
  doi =		{10.4230/LIPIcs.ITC.2020.13},
  annote =	{Keywords: Constrained pseudorandom functions, function secret-sharing, conditional disclosure of secrets}
}
  • Refine by Type
  • 7 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 1 2024
  • 1 2022
  • 1 2020

  • Refine by Author
  • 2 Peter, Naty
  • 1 Applebaum, Benny
  • 1 Beimel, Amos
  • 1 Ben David, Tamar
  • 1 Blocki, Jeremiah
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 2 Security and privacy → Information-theoretic techniques
  • 2 Theory of computation → Cryptographic primitives
  • 2 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 1 Information systems → Graph-based database models
  • 1 Information systems → Query optimization
  • Show More...

  • Refine by Keyword
  • 1 Approximate range counting
  • 1 Constrained pseudorandom functions
  • 1 Constraint-based Minimization
  • 1 Graph Databases
  • 1 Grouping and Aggregation
  • 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