61 Search Results for "Rothblum, Guy N."

Volume

LIPIcs, Volume 295

5th Symposium on Foundations of Responsible Computing (FORC 2024)

FORC 2024, June 12-14, 2024, Harvard University, Cambridge, MA, USA

Editors: Guy N. Rothblum

Document
DOI: 10.4230/LIPIcs.STACS.2026.66
Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds

Authors: Yupan Liu

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We investigate the computational hardness of estimating the quantum α-Rényi entropy S^𝚁_α(ρ) = (ln Tr(ρ^α))/(1-α) and the quantum q-Tsallis entropy S^𝚃_q(ρ) = (1-Tr(ρ^q))/(q-1), both converging to the von Neumann entropy as the order approaches 1. The promise problems Quantum α-Rényi Entropy Approximation (RényiQEA_α) and Quantum q-Tsallis Entropy Approximation (TsallisQEA_q) ask whether S^𝚁_α(ρ) or S^𝚃_q(ρ), respectively, is at least τ_Y or at most τ_N, where τ_Y - τ_N is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 1) and some cases of the quantum q-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real orders, the rank-2 variants Rank2RényiQEA_α and Rank2TsallisQEA_q are BQP-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), our results imply: - For all real order α > 0 and 0 < q ≤ 1, LowRankRényiQEA_α and LowRankTsallisQEA_q are BQP-complete, where both are restricted versions of RényiQEA_α and TsallisQEA_q with ρ of polynomial rank. - For all real order q > 1, TsallisQEA_q is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the α-Rényi or q-Tsallis binary entropies of different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.
Cite as

Yupan Liu. Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 66:1-66:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.STACS.2026.66,
  author =	{Liu, Yupan},
  title =	{{Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{66:1--66:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.66},
  URN =		{urn:nbn:de:0030-drops-255550},
  doi =		{10.4230/LIPIcs.STACS.2026.66},
  annote =	{Keywords: computational hardness, quantum state testing, quantum R\'{e}nyi entropy, quantum Tsallis entropy, von Neumann entropy}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.40
A Simple and Robust Protocol for Distributed Counting

Authors: Edith Cohen, Moshe Shechner, and Uri Stemmer

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across k sites while minimizing communication. The communication complexity of this problem is known to be Θ(k/(ε)log N) for deterministic protocols. Huang, Yi, and Zhang (2012) showed that randomization can reduce this to Θ((√k)/ε log N), but their analysis is restricted to the oblivious setting, where the stream of events is independent of the protocol’s outputs. Xiong, Zhu, and Huang (2023) presented a robust protocol for distributed counting that removes the oblivious assumption. However, their communication complexity is suboptimal by a polylog(k) factor and their protocol is substantially more complex than the oblivious protocol of Huang et al. (2012). This left open a natural question: could it be that the simple protocol of Huang et al. (2012) is already robust? We resolve this question with two main contributions. First, we show that the protocol of Huang et al. (2012) is itself not robust by constructing an explicit adaptive attack that forces it to lose its accuracy. Second, we present a new, surprisingly simple, robust protocol for distributed counting that achieves the optimal communication complexity of O((√k)/ε log N). Our protocol is simpler than that of Xiong et al. (2023), perhaps even simpler than that of Huang et al. (2012), and is the first to match the optimal oblivious complexity in the adaptive setting.
Cite as

Edith Cohen, Moshe Shechner, and Uri Stemmer. A Simple and Robust Protocol for Distributed Counting. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ITCS.2026.40,
  author =	{Cohen, Edith and Shechner, Moshe and Stemmer, Uri},
  title =	{{A Simple and Robust Protocol for Distributed Counting}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{40:1--40:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.40},
  URN =		{urn:nbn:de:0030-drops-253272},
  doi =		{10.4230/LIPIcs.ITCS.2026.40},
  annote =	{Keywords: Distributed Streaming, Adversarial Streaming}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.42
Time and Space Efficient Deterministic List Decoding

Authors: Joshua Cook and Dana Moshkovitz

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Error correcting codes encode messages by codewords in such a way that even if some of the codeword is corrupted, the message can be decoded. Typical decoding algorithms for error correcting codes either use linear space or quadratic time. A natural question is whether codes can be decoded in near-linear time and sub-linear space simultaneously. A recent result by Cook and Moshkovitz gave efficient decoders that can uniquely decode Reed-Muller and other codes from a constant fraction (less than half) of corruption. In this work, we address the problem of list decoding in near-linear time and sub-linear space. In the list decoding setting, most of the codeword is corrupted, and one wants to output a short list of potential messages that contains the true message. For any constants γ, τ > 0, we give decoders for Reed-Muller codes that can decode from 1-γ fraction of corruptions in time n^{1+τ} and space n^{τ}. Our decoders work by extending the iterative correction technique of Cook and Moshkovitz. However, that technique, which gradually decreases the number of corruptions in the message, was tailored to the unique decoding setting. We first identify an intermediate problem, codewords list recovery, for which we can make iterative correction work. We then show how to reduce general list decoding to the codewords list recovery problem in efficient time and space. The reduction relies on local correction and testing. In the codewords list recovery problem, the input consists of n unordered lists containing exactly the symbols from L codewords, where a small fraction of the lists is corrupted. The goal is to find the L codewords. In addition, we prove that any linear code with time-space efficient encoding or decoding must be local, in the sense that the codewords satisfy a local linear constraint. This rules out codes like Reed-Solomon from having time-space efficient encoding or decoding.
Cite as

Joshua Cook and Dana Moshkovitz. Time and Space Efficient Deterministic List Decoding. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 42:1-42:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cook_et_al:LIPIcs.ITCS.2026.42,
  author =	{Cook, Joshua and Moshkovitz, Dana},
  title =	{{Time and Space Efficient Deterministic List Decoding}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{42:1--42:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.42},
  URN =		{urn:nbn:de:0030-drops-253292},
  doi =		{10.4230/LIPIcs.ITCS.2026.42},
  annote =	{Keywords: Reed-Muller code, local correction, local testing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.21
Differential Privacy from Axioms

Authors: Guy Blanc, William Pires, and Toniann Pitassi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Differential privacy (DP) is the de facto notion of privacy both in theory and in practice. However, despite its popularity, DP imposes strict requirements which guard against strong worst-case scenarios. For example, it guards against seemingly unrealistic scenarios where an attacker has full information about all but one point in the data set, and still nothing can be learned about the remaining point. While preventing such a strong attack is desirable, many works have explored whether average-case relaxations of DP are easier to satisfy [Hall et al., 2013; Wang et al., 2016; Bassily and Freund, 2016; Liu et al., 2023]. In this work, we are motivated by the question of whether alternate, weaker notions of privacy are possible: can a weakened privacy notion still guarantee some basic level of privacy, and on the other hand, achieve privacy more efficiently and/or for a substantially broader set of tasks? Our main result shows the answer is no: even in the statistical setting, any reasonable measure of privacy satisfying nontrivial composition is equivalent to DP. To prove this, we identify a core set of four axioms or desiderata: pre-processing invariance, prohibition of blatant non-privacy, strong composition, and linear scalability. Our main theorem shows that any privacy measure satisfying our axioms is equivalent to DP, up to polynomial factors in sample complexity. We complement this result by showing our axioms are minimal: removing any one of our axioms enables ill-behaved measures of privacy.
Cite as

Guy Blanc, William Pires, and Toniann Pitassi. Differential Privacy from Axioms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blanc_et_al:LIPIcs.ITCS.2026.21,
  author =	{Blanc, Guy and Pires, William and Pitassi, Toniann},
  title =	{{Differential Privacy from Axioms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.21},
  URN =		{urn:nbn:de:0030-drops-253081},
  doi =		{10.4230/LIPIcs.ITCS.2026.21},
  annote =	{Keywords: Differential Privacy, Privacy Amplification, Composition}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.69
Computing Equilibrium Points of Electrostatic Potentials

Authors: Abheek Ghosh, Paul W. Goldberg, and Alexandros Hollender

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study the computation of equilibrium points of electrostatic potentials: locations in space where the electrostatic force arising from a collection of charged particles vanishes. This is a novel scenario of optimization in which solutions are guaranteed to exist due to a nonconstructive argument, but gradient descent is unreliable due to the presence of singularities. We present an algorithm based on piecewise approximation of the potential function by Taylor series. The main insight is to divide the domain into a grid with variable coarseness, where grid cells are exponentially smaller in regions where the function changes rapidly compared to regions where it changes slowly. Our algorithm finds approximate equilibrium points in time poly-logarithmic in the approximation parameter, but these points are not guaranteed to be close to exact solutions. Nevertheless, we show that such points can be computed efficiently under a mild assumption that we call "strong non-degeneracy". We complement these algorithmic results by studying a generalization of this problem and showing that it is CLS-hard and in PPAD, leaving its precise classification as an intriguing open problem.
Cite as

Abheek Ghosh, Paul W. Goldberg, and Alexandros Hollender. Computing Equilibrium Points of Electrostatic Potentials. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 69:1-69:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghosh_et_al:LIPIcs.ITCS.2026.69,
  author =	{Ghosh, Abheek and Goldberg, Paul W. and Hollender, Alexandros},
  title =	{{Computing Equilibrium Points of Electrostatic Potentials}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{69:1--69:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.69},
  URN =		{urn:nbn:de:0030-drops-253566},
  doi =		{10.4230/LIPIcs.ITCS.2026.69},
  annote =	{Keywords: Total search problems, TFNP, PPAD, CLS, polynomial equations}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.117
On the Power of Computationally Sound Interactive Proofs of Proximity

Authors: Hadar Strauss

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Interactive proofs of proximity (IPPs) are a relaxation of interactive proofs, analogous to property testing, in which soundness is required to hold only for inputs that are ε-far from the property being verified, where ε > 0 is a proximity parameter. In such proof systems, the verifier has oracle access to the input, and it engages in two types of activities before making its decision: querying the input oracle and communicating with the prover. The main objective is to achieve protocols where both the query and communication complexities are extremely low. In this work, we focus on computationally sound IPPs (cs-IPPs). We study their power in two aspects: - Query complexity: We show that, assuming the existence of collision-resistant hashing functions (CRHFs), any public-coin cs-IPP that has query complexity q can be transformed into a cs-IPP that makes only O(1/ε) queries, while increasing the communication complexity by roughly q. If we further assume the existence of a good computational PIR (private information retrieval) scheme, then a similar transformation holds for general (i.e., possibly private-coin) cs-IPPs. - Coordination: Aside from the low query complexity, the resulting cs-IPP has only minimal coordination between the verifier’s two activities. The general definition of IPPs allows the verifier to fully coordinate its interaction with the prover and its queries to the input oracle. Goldreich, Rothblum, and Skverer (ITCS 2023) introduced two restricted models of IPPs that are minimally coordinated: The pre-coordinated model, where no information flows between the querying and interacting activities, but they may use a common source of randomness, and the isolated model, where the two activities are fully independent, each operating with a separate source of randomness. Our transformation shows that (under the aforementioned computational assumptions) any cs-IPP can be made to be in the pre-coordinated model, while preserving its efficiency. Hence, pre-coordinated cs-IPPs are essentially as powerful as general cs-IPPs. In contrast, we show that cs-IPPs in the isolated model are extremely limited, offering almost no advantage over property testers. Specifically, extending on a result shown by Goldreich et al. for unconditionally sound IPPs in the isolated model, we show that if a property has a cs-IPP in the isolated model that makes q queries and uses c > 0 bits of communication, then it has a tester with query complexity O(c⋅ q).
Cite as

Hadar Strauss. On the Power of Computationally Sound Interactive Proofs of Proximity. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 117:1-117:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{strauss:LIPIcs.ITCS.2026.117,
  author =	{Strauss, Hadar},
  title =	{{On the Power of Computationally Sound Interactive Proofs of Proximity}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{117:1--117:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.117},
  URN =		{urn:nbn:de:0030-drops-254047},
  doi =		{10.4230/LIPIcs.ITCS.2026.117},
  annote =	{Keywords: Interactive Proofs of Proximity, Computational Soundness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.33
Uniformity Testing Under User-Level Local Privacy

Authors: Clément L. Canonne, Abigail Gentle, and Vikrant Singhal

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We initiate the study of distribution testing under user-level local differential privacy, where each of n users contributes m samples from the unknown underlying distribution. This setting, albeit very natural, is significantly more challenging than the usual locally private setting, as for the same parameter ε the privacy guarantee must now apply to a full batch of m data points. While some recent work considers distribution learning in this user-level setting, nothing was known for even the most fundamental testing task, uniformity testing (and its generalization, identity testing). We address this gap, by providing (nearly) sample-optimal user-level LDP algorithms for uniformity and identity testing. Motivated by practical considerations, our main focus is on the private-coin, symmetric setting, which does not require users to share a common random seed nor to have been assigned a globally unique identifier.
Cite as

Clément L. Canonne, Abigail Gentle, and Vikrant Singhal. Uniformity Testing Under User-Level Local Privacy. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 33:1-33:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{canonne_et_al:LIPIcs.ITCS.2026.33,
  author =	{Canonne, Cl\'{e}ment L. and Gentle, Abigail and Singhal, Vikrant},
  title =	{{Uniformity Testing Under User-Level Local Privacy}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{33:1--33:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.33},
  URN =		{urn:nbn:de:0030-drops-253201},
  doi =		{10.4230/LIPIcs.ITCS.2026.33},
  annote =	{Keywords: Differential Privacy, Local Differential Privacy, Uniformity Testing, Identity Testing, Hypothesis Testing, User-Level Differential Privacy, Person-Level Differential Privacy}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.18
Interactive Proofs for Distribution Testing with Conditional Oracles

Authors: Ari Biswas, Mark Bun, Clément L. Canonne, and Satchit Sivakumar

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We revisit the framework of interactive proofs for distribution testing, first introduced by Chiesa and Gur (ITCS 2018), which has recently experienced a surge in interest, accompanied by notable progress (e.g., Herman and Rothblum, STOC 2022, FOCS 2023; Herman, RANDOM 2024). In this model, a data-poor verifier determines whether a probability distribution has a property of interest by interacting with an all-powerful, data-rich but untrusted prover bent on convincing them that it has the property. While prior work gave sample-, time-, and communication-efficient protocols for testing and estimating a range of distribution properties, they all suffer from an inherent issue: for most interesting properties of distributions over a domain of size N, the verifier must draw at least Ω(√N) samples of its own. While sublinear in N, this is still prohibitive for large domains encountered in practice. In this work, we circumvent this limitation by augmenting the verifier with the ability to perform an exponentially smaller number of more powerful (but reasonable) pairwise conditional queries, effectively enabling them to perform "local comparison checks" of the prover’s claims. We systematically investigate the landscape of interactive proofs in this new setting, giving poly-logarithmic query and sample protocols for (tolerantly) testing all label-invariant properties, thus demonstrating exponential savings without compromising on communication, for this large and fundamental class of testing tasks.
Cite as

Ari Biswas, Mark Bun, Clément L. Canonne, and Satchit Sivakumar. Interactive Proofs for Distribution Testing with Conditional Oracles. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{biswas_et_al:LIPIcs.ITCS.2026.18,
  author =	{Biswas, Ari and Bun, Mark and Canonne, Cl\'{e}ment L. and Sivakumar, Satchit},
  title =	{{Interactive Proofs for Distribution Testing with Conditional Oracles}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.18},
  URN =		{urn:nbn:de:0030-drops-253059},
  doi =		{10.4230/LIPIcs.ITCS.2026.18},
  annote =	{Keywords: Distribution Testing, Interactive Proofs}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.38
Fairness and Efficiency in Two-Sided Matching Markets

Authors: Pallavi Jain, Palash Jha, and Shubham Solanki

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We propose a new fairness notion, motivated by the practical challenge of allocating teaching assistants (TAs) to courses in a department. Each course requires a certain number of TAs and each TA has preferences over the courses they want to assist. Similarly, each course instructor has preferences over the TAs who applied for their course. We demand fairness and efficiency for both sides separately, giving rise to the following criteria: (i) every course gets the required number of TAs and the average utility of the assigned TAs meets a threshold; (ii) the allocation of courses to TAs is envy-free, where a TA envies another TA if the former prefers the latter’s course and has a higher or equal grade in that course. Note that the definition of envy-freeness here differs from the one in the literature, and we call it merit-based envy-freeness. We show that the problem of finding a merit-based envy-free and efficient matching is NP-hard even for very restricted settings, such as two courses and uniform valuations; constant degree, constant capacity of TAs for every course, valuations in the range {0,1,2,3}, identical valuations from TAs, and even more. To find tractable results, we consider some restricted instances, such as, strict valuation of TAs for courses, the difference between the number of positively valued TAs for a course and the capacity, the number of positively valued TAs/courses, types of valuation functions, and obtained some polynomial-time solvable cases, showing the contrast with intractable results. We further studied the problem in the paradigm of parameterized algorithms and designed some exact and approximation algorithms.
Cite as

Pallavi Jain, Palash Jha, and Shubham Solanki. Fairness and Efficiency in Two-Sided Matching Markets. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.FSTTCS.2025.38,
  author =	{Jain, Pallavi and Jha, Palash and Solanki, Shubham},
  title =	{{Fairness and Efficiency in Two-Sided Matching Markets}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.38},
  URN =		{urn:nbn:de:0030-drops-251186},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.38},
  annote =	{Keywords: Fair Matching, Envy-Freeness, Efficiency}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.31
Trustless Bridges via Random Sampling Light Clients

Authors: Bhargav Nagaraja Bhatt, Fatemeh Shirazi, and Alistair Stewart

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
The increasing number of blockchain projects introduced annually has led to a pressing need for secure and efficient interoperability solutions. Currently, the lack of such solutions forces end-users to rely on centralized intermediaries, contradicting the core principle of decentralization and trust minimization in blockchain technology. We propose a decentralized and efficient interoperability solution (aka Bridge Protocol) that operates without additional trust assumptions, relying solely on the Byzantine Fault Tolerance (BFT) properties of the two chains being connected. In particular, relayers (actors that exchange messages between networks) are permissionless and decentralized, hence eliminating any single point of failure. We introduce Random Sampling, a novel technique for on-chain light clients to efficiently follow the history of PoS blockchains by reducing the signature verifications required. Here, the randomness is drawn on-chain, for example, using Ethereum’s RANDAO. We analyze the security of the bridge from a crypto- economic perspective and provide a framework to derive the security parameters. This includes handling subtle concurrency issues and randomness bias in strawman designs. While the protocol is applicable to various PoS chains, we demonstrate the protocol’s practical feasibility by showcasing an instantiated bridge between Polkadot and Ethereum (currently deployed), and discuss some practical security challenges. Furthermore, we evaluate the efficiency of our on-chain light client verifier (implemented as an Ethereum smart contract) against SNARK-based approaches, demonstrating significantly lower gas costs for signature verification - even for validator sets up to 10⁶.
Cite as

Bhargav Nagaraja Bhatt, Fatemeh Shirazi, and Alistair Stewart. Trustless Bridges via Random Sampling Light Clients. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 31:1-31:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhatt_et_al:LIPIcs.AFT.2025.31,
  author =	{Bhatt, Bhargav Nagaraja and Shirazi, Fatemeh and Stewart, Alistair},
  title =	{{Trustless Bridges via Random Sampling Light Clients}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{31:1--31:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.31},
  URN =		{urn:nbn:de:0030-drops-247503},
  doi =		{10.4230/LIPIcs.AFT.2025.31},
  annote =	{Keywords: PoS Blockchains, Trustless Bridges, Light Clients, Decentralised Relayers, RANDAO Bias}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ESA.2025.2
Securing Dynamic Data: A Primer on Differentially Private Data Structures (Invited Talk)

Authors: Monika Henzinger and Roodabeh Safavi

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We give an introduction into differential privacy in the dynamic setting, called the continual observation setting.
Cite as

Monika Henzinger and Roodabeh Safavi. Securing Dynamic Data: A Primer on Differentially Private Data Structures (Invited Talk). In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.ESA.2025.2,
  author =	{Henzinger, Monika and Safavi, Roodabeh},
  title =	{{Securing Dynamic Data: A Primer on Differentially Private Data Structures}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.2},
  URN =		{urn:nbn:de:0030-drops-244702},
  doi =		{10.4230/LIPIcs.ESA.2025.2},
  annote =	{Keywords: Differential privacy, continual observation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.95
The Planted Orthogonal Vectors Problem

Authors: David Kühnemann, Adam Polak, and Alon Rosen

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In the k-Orthogonal Vectors (k-OV) problem we are given k sets, each containing n binary vectors of dimension d = n^o(1), and our goal is to pick one vector from each set so that at each coordinate at least one vector has a zero. It is a central problem in fine-grained complexity, conjectured to require n^{k-o(1)} time in the worst case. We propose a way to plant a solution among vectors with i.i.d. p-biased entries, for appropriately chosen p, so that the planted solution is the unique one. Our conjecture is that the resulting k-OV instances still require time n^{k-o(1)} to solve, on average. Our planted distribution has the property that any subset of strictly less than k vectors has the same marginal distribution as in the model distribution, consisting of i.i.d. p-biased random vectors. We use this property to give average-case search-to-decision reductions for k-OV.
Cite as

David Kühnemann, Adam Polak, and Alon Rosen. The Planted Orthogonal Vectors Problem. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 95:1-95:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kuhnemann_et_al:LIPIcs.ESA.2025.95,
  author =	{K\"{u}hnemann, David and Polak, Adam and Rosen, Alon},
  title =	{{The Planted Orthogonal Vectors Problem}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{95:1--95:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.95},
  URN =		{urn:nbn:de:0030-drops-245640},
  doi =		{10.4230/LIPIcs.ESA.2025.95},
  annote =	{Keywords: Average-case complexity, fine-grained complexity, orthogonal vectors}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.91
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism

Authors: Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the k-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of n due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. When applied to vectors with n dimensions, we solve a number of important graph problems with better bounds than previous work. Specifically, we apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including k-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge differentially private (LEDP) algorithm for k-core decomposition that results in an approximation with O(ε^{-1} log n) additive error and no multiplicative error in O(n) rounds. We also give a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in O(log² n) rounds for any constant η > 0. Both of these results are asymptotically tight against our new lower bound of Ω(log n) for any constant-factor approximation algorithm for k-core decomposition. Our new algorithms for k-core decomposition also directly lead to new algorithms for the related problems of densest subgraph and low out-degree ordering. Finally, we give novel LEDP differentially private defective coloring algorithms that use number of colors given in terms of the arboricity of the graph.
Cite as

Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu. Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 91:1-91:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dhulipala_et_al:LIPIcs.ESA.2025.91,
  author =	{Dhulipala, Laxman and Henzinger, Monika and Li, George Z. and Liu, Quanquan C. and Sricharan, A. R. and Zhu, Leqi},
  title =	{{Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{91:1--91:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.91},
  URN =		{urn:nbn:de:0030-drops-245601},
  doi =		{10.4230/LIPIcs.ESA.2025.91},
  annote =	{Keywords: differential privacy, abovethreshold, densest subgraph}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.40
Sublinear Space Graph Algorithms in the Continual Release Model

Authors: Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, and Felix Zhou

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

Abstract
The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of edge updates where new private solutions are released after each update. Thus far, previously known edge-differentially private algorithms for most graph problems including densest subgraph and matchings in the continual release setting only output real-value estimates (not vertex subset solutions) and do not use sublinear space. Instead, they rely on computing exact graph statistics on the input [Hendrik Fichtenberger et al., 2021; Shuang Song et al., 2018]. In this paper, we leverage sparsification to address the above shortcomings for edge-insertion streams. Our edge-differentially private algorithms use sublinear space with respect to the number of edges in the graph while some also achieve sublinear space in the number of vertices in the graph. In addition, for the densest subgraph problem, we also output edge-differentially private vertex subset solutions; no previous graph algorithms in the continual release model output such subsets. We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms literature to achieve new results in the sublinear space, continual release setting. This includes algorithms for densest subgraph, maximum matching, as well as the first continual release k-core decomposition algorithm. We also develop a novel sparse level data structure for k-core decomposition that may be of independent interest. To complement our insertion-only algorithms, we conclude with polynomial additive error lower bounds for edge-privacy in the fully dynamic setting, where only logarithmic lower bounds were previously known.
Cite as

Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, and Felix Zhou. Sublinear Space Graph Algorithms in the Continual Release Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 40:1-40:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{epasto_et_al:LIPIcs.APPROX/RANDOM.2025.40,
  author =	{Epasto, Alessandro and Liu, Quanquan C. and Mukherjee, Tamalika and Zhou, Felix},
  title =	{{Sublinear Space Graph Algorithms in the Continual Release Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{40:1--40:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.40},
  URN =		{urn:nbn:de:0030-drops-244064},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.40},
  annote =	{Keywords: Differential Privacy, Continual Release, Densest Subgraph, k-Core Decomposition, Maximum Matching}
}
  • Refine by Type
  • 60 Document/PDF
  • 35 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 8 2026
  • 28 2025
  • 13 2024
  • 3 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 13 Rothblum, Guy N.
  • 3 Dwork, Cynthia
  • 3 Goldreich, Oded
  • 3 Yona, Gal
  • 2 Canonne, Clément L.
  • Show More...

  • Refine by Series/Journal
  • 60 LIPIcs

  • Refine by Classification
  • 7 Security and privacy
  • 7 Theory of computation → Computational complexity and cryptography
  • 7 Theory of computation → Interactive proof systems
  • 6 Theory of computation → Theory of database privacy and security
  • 5 Theory of computation
  • Show More...

  • Refine by Keyword
  • 6 algorithmic fairness
  • 5 Differential Privacy
  • 5 differential privacy
  • 3 Differential privacy
  • 3 Interactive Proofs
  • 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