29 Search Results for "Steinke, Thomas"

Document
DOI: 10.4230/LIPIcs.FORC.2026.3
Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms

Authors: Charlie Harrison and Pasin Manurangsi

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
Zero-concentrated differential privacy (zCDP) is a variant of differential privacy (DP) that is widely used partly due to its nice composition property. While a tight conversion from ε-DP to zCDP exists for the worst-case mechanism, many common algorithms satisfy stronger guarantees. In this work, we derive tight zCDP characterizations for several fundamental mechanisms. We prove that the tight zCDP bound for the ε-DP Laplace mechanism is exactly ε + e^{-ε} - 1, confirming a recent conjecture by Wang [Yu-Xiang Wang, 2022]. We further provide tight bounds for the discrete Laplace mechanism, k-Randomized Response (for k ≤ 6), and RAPPOR. Lastly, we also provide a tight zCDP bound for the worst case bounded range mechanism.
Cite as

Charlie Harrison and Pasin Manurangsi. Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{harrison_et_al:LIPIcs.FORC.2026.3,
  author =	{Harrison, Charlie and Manurangsi, Pasin},
  title =	{{Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.3},
  URN =		{urn:nbn:de:0030-drops-259741},
  doi =		{10.4230/LIPIcs.FORC.2026.3},
  annote =	{Keywords: Zero-Concentrated Differentially Privacy, Laplace Mechanism, Randomized Response}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.4
Nearly-Optimal Private Selection via Gaussian Mechanism

Authors: Ethan Leeman and Pasin Manurangsi

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
Steinke [2025] recently asked the following intriguing open question: Can we solve the differentially private selection problem with nearly-optimal error by only (adaptively) invoking Gaussian mechanism on low-sensitivity queries? We resolve this question positively. In particular, for a candidate set 𝒴, we achieve error guarantee of Õ(log |𝒴|), which is within a factor of (log log |𝒴|)^{O(1)} of the exponential mechanism [McSherry and Talwar, 2007]. This improves on Steinke’s mechanism which achieves an error of O(log^{3/2} |𝒴|).
Cite as

Ethan Leeman and Pasin Manurangsi. Nearly-Optimal Private Selection via Gaussian Mechanism. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{leeman_et_al:LIPIcs.FORC.2026.4,
  author =	{Leeman, Ethan and Manurangsi, Pasin},
  title =	{{Nearly-Optimal Private Selection via Gaussian Mechanism}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.4},
  URN =		{urn:nbn:de:0030-drops-259750},
  doi =		{10.4230/LIPIcs.FORC.2026.4},
  annote =	{Keywords: Differentially Private Selection, Gaussian Mechanism}
}
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.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
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
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.35
Fooling Near-Maximal Decision Trees

Authors: William M. Hoza and Zelin Lv

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

Abstract
For any constant α > 0, we construct an explicit pseudorandom generator (PRG) that fools n-variate decision trees of size m with error ε and seed length (1 + α) ⋅ log₂ m + O(log(1/ε) + log log n). For context, one can achieve seed length (2 + o(1)) ⋅ log₂ m + O(log(1/ε) + log log n) using well-known constructions and analyses of small-bias distributions, but such a seed length is trivial when m ≥ 2^{n/2}. Our approach is to develop a new variant of the classic concept of almost k-wise independence, which might be of independent interest. We say that a distribution X over {0, 1}ⁿ is k-wise ε-probably uniform if every Boolean function f that depends on only k variables satisfies 𝔼[f(X)] ≥ (1 - ε) ⋅ 𝔼[f]. We show how to sample a k-wise ε-probably uniform distribution using a seed of length (1 + α) ⋅ k + O(log(1/ε) + log log n). Meanwhile, we also show how to construct a set H ⊆ 𝔽₂ⁿ such that every feasible system of k linear equations in n variables over 𝔽₂ has a solution in H. The cardinality of H and the time complexity of enumerating H are at most 2^{k + o(k) + polylog n}, whereas small-bias distributions would give a bound of 2^{2k + O(log(n/k))}. By combining our new constructions with work by Chen and Kabanets (TCS 2016), we obtain nontrivial PRGs and hitting sets for linear-size Boolean circuits. Specifically, we get an explicit PRG with seed length (1 - Ω(1)) ⋅ n that fools circuits of size 2.99 ⋅ n over the U₂ basis, and we get a hitting set with time complexity 2^{(1 - Ω(1)) ⋅ n} for circuits of size 2.49 ⋅ n over the B₂ basis.
Cite as

William M. Hoza and Zelin Lv. Fooling Near-Maximal Decision Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 35:1-35:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hoza_et_al:LIPIcs.APPROX/RANDOM.2025.35,
  author =	{Hoza, William M. and Lv, Zelin},
  title =	{{Fooling Near-Maximal Decision Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{35:1--35:24},
  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.35},
  URN =		{urn:nbn:de:0030-drops-244019},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.35},
  annote =	{Keywords: almost k-wise independence, decision trees, pseudorandom generators}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.28
Implications of Better PRGs for Permutation Branching Programs

Authors: Dean Doron and William M. Hoza

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

Abstract
We study the challenge of derandomizing constant-width standard-order read-once branching programs (ROBPs). Let c ∈ [1, 2) be any constant. We prove that if there are explicit pseudorandom generators (PRGs) for width-6 length-n permutation ROBPs with error 1/n and seed length Õ(log^c n), then there are explicit hitting set generators (HSGs) for width-4 length-n ROBPs with threshold 1/polylog(n) and seed length Õ(log^c n). For context, there are known explicit PRGs that fool constant-width permutation ROBPs with error ε and seed length O(log(n)⋅log(1/ε)) (Koucký, Nimbhorkar, and Pudlák STOC 2011; De CCC 2011; Steinke ECCC 2012). When ε = 1/n, there are known constructions of weighted pseudorandom generators (WPRGs) that fool polynomial-width permutation ROBPs with seed length Õ(log^{3/2} n) (Pyne and Vadhan CCC 2021; Chen, Hoza, Lyu, Tal, and Wu FOCS 2023; Chattopadhyay and Liao ITCS 2024), but unweighted PRGs with seed length o(log² n) remain elusive. Meanwhile, for width-4 ROBPs, there are no known explicit PRGs, WPRGs, or HSGs with seed length o(log²n). Our reduction can be divided into two parts. First, we show that explicit low-error PRGs for width-6 permutation ROBPs with seed length Õ(log^c n) would imply explicit low-error PRGs for width-3 ROBPs with seed length Õ(log^c n). This would improve Meka, Reingold, and Tal’s PRG (STOC 2019), which has seed length o(log²n) only when the error parameter is relatively large. Second, we show that for any w, n, s, and ε, an explicit PRG for width-w ROBPs with error 0.01/n and seed length s would imply an explicit ε-HSG for width-(w + 1) ROBPs with seed length O(s + log(n)⋅log(1/ε)).
Cite as

Dean Doron and William M. Hoza. Implications of Better PRGs for Permutation Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2025.28,
  author =	{Doron, Dean and Hoza, William M.},
  title =	{{Implications of Better PRGs for Permutation Branching Programs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{28:1--28:20},
  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.28},
  URN =		{urn:nbn:de:0030-drops-243946},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.28},
  annote =	{Keywords: hitting set generators, pseudorandom generators, read-once branching programs}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.67
On Sums of INW Pseudorandom Generators

Authors: William M. Hoza and Zelin Lv

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

Abstract
We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). Let X be the n-bit output distribution of the INW PRG (Impagliazzo, Nisan, and Wigderson, STOC 1994), instantiated using expansion parameter λ. We prove that the bitwise XOR of t independent copies of X fools width-w programs with error n^{log(w + 1)} ⋅ (λ⋅log n)^t. Notably, this error bound is meaningful even for relatively large values of λ such as λ = 1/O(log n). Admittedly, our analysis does not yet imply any improvement in the bottom-line overall seed length required for fooling such programs - it just gives a new way of re-proving the well-known O(log² n) bound. Furthermore, we prove that this shortcoming is not an artifact of our analysis, but rather is an intrinsic limitation of our "XOR of INW" approach. That is, no matter how many copies of the INW generator we XOR together, and no matter how we set the expansion parameters, if the generator fools width-3 programs and the proof of correctness does not use any properties of the expander graphs except their spectral expansion, then we prove that the seed length of the generator is inevitably Ω(log² n). Still, we hope that our work might be a step toward constructing near-optimal PRGs fooling constant-width ROBPs. We suggest that one could try running the INW PRG on t correlated seeds, sampled via another PRG, and taking the bitwise XOR of the outputs.
Cite as

William M. Hoza and Zelin Lv. On Sums of INW Pseudorandom Generators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 67:1-67:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hoza_et_al:LIPIcs.APPROX/RANDOM.2025.67,
  author =	{Hoza, William M. and Lv, Zelin},
  title =	{{On Sums of INW Pseudorandom Generators}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{67:1--67:24},
  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.67},
  URN =		{urn:nbn:de:0030-drops-244330},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.67},
  annote =	{Keywords: INW generator, pseudorandomness, space-bounded computation, XOR Lemmas}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.66
Testing Isomorphism of Boolean Functions over Finite Abelian Groups

Authors: Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy

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

Abstract
Let f and g be Boolean functions over a finite Abelian group 𝒢, where g is fully known and f is accessible via queries; that is, given any x ∈ 𝒢, we can obtain the value f(x). We study the problem of tolerant isomorphism testing: given parameters ε ≥ 0 and τ > 0, the goal is to determine, using as few queries as possible, whether there exists an automorphism σ of 𝒢 such that the fractional Hamming distance between f∘σ and g is at most ε, or whether for every automorphism σ, the distance is at least ε + τ. We design an efficient tolerant property testing algorithm for this problem over finite Abelian groups with constant exponent. The exponent of a finite group refers to the largest order of any element in the group. The query complexity of our algorithm is polynomial in s and 1/τ, where s bounds the spectral norm of the function g, and τ is the tolerance parameter. In addition, we present an improved algorithm in the case where g is Fourier sparse, meaning that its Fourier expansion contains only a small number of nonzero coefficients. Our approach draws on key ideas from Abelian group theory and Fourier analysis, including the annihilator of a subgroup, Pontryagin duality, and a pseudo inner product defined over finite Abelian groups. We believe that these techniques will be useful more broadly in the design of property testing algorithms.
Cite as

Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy. Testing Isomorphism of Boolean Functions over Finite Abelian Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 66:1-66:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.APPROX/RANDOM.2025.66,
  author =	{Datta, Swarnalipa and Ghosh, Arijit and Kayal, Chandrima and Paraashar, Manaswi and Roy, Manmatha},
  title =	{{Testing Isomorphism of Boolean Functions over Finite Abelian Groups}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{66:1--66:22},
  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.66},
  URN =		{urn:nbn:de:0030-drops-244328},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.66},
  annote =	{Keywords: Analysis of Boolean functions, Abelian groups, Automorphism group, Function isomorphism, Spectral norm}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.15
RustSAT: A Library for SAT Solving in Rust

Authors: Christoph Jabs

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
State-of-the-art Boolean satisfiability (SAT) solvers constitute a practical and competitive approach for solving various real-world problems. To encourage their widespread adoption, the relatively high barrier of entry following from the low level syntax of SAT and the expert knowledge required to achieve tight integration with SAT solvers should be further reduced. We present RustSAT, a library with the aim of making SAT solving technology readily available in the Rust programming language. RustSAT provides functionality for helping with generating (Max)SAT instances, writing them to, or reading them from files. Furthermore, RustSAT includes interfaces to various state-of-the-art SAT solvers available with a unified Rust API. Lastly, RustSAT implements several encodings for higher level constraints (at-most-one, cardinality, and pseudo-Boolean), which are also available via a C and Python API.
Cite as

Christoph Jabs. RustSAT: A Library for SAT Solving in Rust. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jabs:LIPIcs.SAT.2025.15,
  author =	{Jabs, Christoph},
  title =	{{RustSAT: A Library for SAT Solving in Rust}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.15},
  URN =		{urn:nbn:de:0030-drops-237498},
  doi =		{10.4230/LIPIcs.SAT.2025.15},
  annote =	{Keywords: Rust, library, SAT solvers, constraint encodings}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.9
Pseudorandom Bits for Non-Commutative Programs

Authors: Chin Ho Lee and Emanuele Viola

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows: 1) We consider read-once group-products over a finite group G, i.e., tests of the form ∏_{i=1}^n (g_i)^{x_i} where g_i ∈ G, a special case of read-once permutation branching programs. We give generators with optimal seed length c_G log(n/ε) over any p-group. The proof uses the small-bias plus noise paradigm, but derandomizes the noise to avoid the recursion in previous work. Our generator works when the bits are read in any order. Previously for any non-commutative group the best seed length was ≥ log n log(1/ε), even for a fixed order. 2) We give a reduction that "lifts" suitable generators for group products over G to a generator that fools width-w block products, i.e., tests of the form ∏ (g_i)^{f_i} where the f_i are arbitrary functions on disjoint blocks of w bits. Block products generalize several previously studied classes. The reduction applies to groups that are mixing in a representation-theoretic sense that we identify. 3) Combining (2) with (1) and other works we obtain new generators for block products over the quaternions or over any commutative group, with nearly optimal seed length. In particular, we obtain generators for read-once polynomials modulo any fixed m with nearly optimal seed length. Previously this was known only for m = 2. 4) We give a new generator for products over "mixing groups." The construction departs from previous work and uses representation theory. For constant error, we obtain optimal seed length, improving on previous work (which applied to any group). This paper identifies a challenge in the area that is reminiscent of a roadblock in circuit complexity - handling composite moduli - and points to several classes of groups to be attacked next.
Cite as

Chin Ho Lee and Emanuele Viola. Pseudorandom Bits for Non-Commutative Programs. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.CCC.2025.9,
  author =	{Lee, Chin Ho and Viola, Emanuele},
  title =	{{Pseudorandom Bits for Non-Commutative Programs}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.9},
  URN =		{urn:nbn:de:0030-drops-237039},
  doi =		{10.4230/LIPIcs.CCC.2025.9},
  annote =	{Keywords: Group programs, Space-bounded derandomization, Representation theory}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.77
Minimizing Recourse in an Adaptive Balls and Bins Game

Authors: Adi Fine, Haim Kaplan, and Uri Stemmer

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

Abstract
We consider a simple load-balancing game between an algorithm and an adaptive adversary. In a simplified version of this game, the adversary observes the assignment of jobs to machines and selects a machine to kill. The algorithm must then restart the jobs from the failed machine on other machines. The adversary repeats this process, observing the new assignment and eliminating another machine, and so on. The adversary aims to force the algorithm to perform many restarts, while we seek a robust algorithm that minimizes restarts regardless of the adversary’s strategy. This game was recently introduced by Bhattacharya et al. for designing a 3-spanner with low recourse against an adaptive adversary. We prove that a simple algorithm, which assigns each job to a randomly chosen live bin, incurs O(n log n) recourse against an adaptive adversary. This enables us to construct a much simpler 3-spanner with a recourse that is smaller by a factor of O(log² n) compared to the previous construction, without increasing the update time or the size of the spanner. This motivates a careful examination of the range of attacks an adaptive adversary can deploy against simple algorithms before resorting to more complex ones. As our case study demonstrates, this attack space may not be as large as it initially appears, enabling the development of robust algorithms that are both simpler and easier to analyze.
Cite as

Adi Fine, Haim Kaplan, and Uri Stemmer. Minimizing Recourse in an Adaptive Balls and Bins Game. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 77:1-77:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fine_et_al:LIPIcs.ICALP.2025.77,
  author =	{Fine, Adi and Kaplan, Haim and Stemmer, Uri},
  title =	{{Minimizing Recourse in an Adaptive Balls and Bins Game}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{77:1--77:19},
  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.77},
  URN =		{urn:nbn:de:0030-drops-234544},
  doi =		{10.4230/LIPIcs.ICALP.2025.77},
  annote =	{Keywords: Adaptive adversary, load-balancing game, balls-and-bins, randomized algorithms, dynamic 3-spanner, dynamic graph algorithms, adversarial robustness}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.3
Private Estimation When Data and Privacy Demands Are Correlated

Authors: Syomantak Chaudhuri and Thomas A. Courtade

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
Differential Privacy (DP) is the current gold-standard for ensuring privacy for statistical queries. Estimation problems under DP constraints appearing in the literature have largely focused on providing equal privacy to all users. We consider the problems of empirical mean estimation for univariate data and frequency estimation for categorical data, both subject to heterogeneous privacy constraints. Each user, contributing a sample to the dataset, is allowed to have a different privacy demand. The dataset itself is assumed to be worst-case and we study both problems under two different formulations - first, where privacy demands and data may be correlated, and second, where correlations are weakened by random permutation of the dataset. We establish theoretical performance guarantees for our proposed algorithms, under both PAC error and mean-squared error. These performance guarantees translate to minimax optimality in several instances, and experiments confirm superior performance of our algorithms over other baseline techniques.
Cite as

Syomantak Chaudhuri and Thomas A. Courtade. Private Estimation When Data and Privacy Demands Are Correlated. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chaudhuri_et_al:LIPIcs.FORC.2025.3,
  author =	{Chaudhuri, Syomantak and Courtade, Thomas A.},
  title =	{{Private Estimation When Data and Privacy Demands Are Correlated}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.3},
  URN =		{urn:nbn:de:0030-drops-231305},
  doi =		{10.4230/LIPIcs.FORC.2025.3},
  annote =	{Keywords: Differential Privacy, Personalized Privacy, Heterogeneous Privacy, Correlations in Privacy}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.10
Count on Your Elders: Laplace vs Gaussian Noise

Authors: Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner, and Sahel Torkamani

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
In recent years, Gaussian noise has become a popular tool in differentially private algorithms, often replacing Laplace noise which dominated the early literature on differential privacy. Gaussian noise is the standard approach to approximate differential privacy, often resulting in much higher utility than traditional (pure) differential privacy mechanisms. In this paper we argue that Laplace noise may in fact be preferable to Gaussian noise in many settings, in particular when we seek to achieve (ε,δ)-differential privacy for small values of δ. We consider two scenarios: First, we consider the problem of counting under continual observation and present a new generalization of the binary tree mechanism that uses a k-ary number system with negative digits to improve the privacy-accuracy trade-off. Our mechanism uses Laplace noise and whenever δ is sufficiently small it improves the mean squared error over the best possible (ε,δ)-differentially private factorization mechanisms based on Gaussian noise. Specifically, using k = 19 we get an asymptotic improvement over the bound given in the work by Henzinger, Upadhyay and Upadhyay (SODA 2023) when δ = O(T^{-0.92}). Second, we show that the noise added by the Gaussian mechanism can always be replaced by Laplace noise of comparable variance for the same (ε, δ)-differential privacy guarantee, and in fact for sufficiently small δ the variance of the Laplace noise becomes strictly better. This challenges the conventional wisdom that Gaussian noise should be used for high-dimensional noise. Finally, we study whether counting under continual observation may be easier in an average-case sense than in a worst-case sense. We show that, under pure differential privacy, the expected worst-case error for a random input must be Ω(log(T)/ε), matching the known lower bound for worst-case inputs.
Cite as

Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner, and Sahel Torkamani. Count on Your Elders: Laplace vs Gaussian Noise. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{andersson_et_al:LIPIcs.FORC.2025.10,
  author =	{Andersson, Joel Daniel and Pagh, Rasmus and Steiner, Teresa Anna and Torkamani, Sahel},
  title =	{{Count on Your Elders: Laplace vs Gaussian Noise}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{10:1--10:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.10},
  URN =		{urn:nbn:de:0030-drops-231376},
  doi =		{10.4230/LIPIcs.FORC.2025.10},
  annote =	{Keywords: differential privacy, continual observation, streaming, prefix sums, trees}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.6
Near-Universally-Optimal Differentially Private Minimum Spanning Trees

Authors: Richard Hladík and Jakub Tětek

Published in: LIPIcs, Volume 329, 6th Symposium on Foundations of Responsible Computing (FORC 2025)

Abstract
Devising mechanisms with good beyond-worst-case input-dependent performance has been an important focus of differential privacy, with techniques such as smooth sensitivity, propose-test-release, or inverse sensitivity mechanism being developed to achieve this goal. This makes it very natural to use the notion of universal optimality in differential privacy. Universal optimality is a strong instance-specific optimality guarantee for problems on weighted graphs, which roughly states that for any fixed underlying (unweighted) graph, the algorithm is optimal in the worst-case sense, with respect to the possible setting of the edge weights. In this paper, we give the first such result in differential privacy. Namely, we prove that a simple differentially private mechanism for approximately releasing the minimum spanning tree is near-optimal in the sense of universal optimality for the 𝓁₁ neighbor relation. Previously, it was only known that this mechanism is nearly optimal in the worst case. We then focus on the 𝓁_∞ neighbor relation, for which the described mechanism is not optimal. We show that one may implement the exponential mechanism for MST in polynomial time, and that this results in universal near-optimality for both the 𝓁₁ and the 𝓁_∞ neighbor relations.
Cite as

Richard Hladík and Jakub Tětek. Near-Universally-Optimal Differentially Private Minimum Spanning Trees. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hladik_et_al:LIPIcs.FORC.2025.6,
  author =	{Hlad{\'\i}k, Richard and T\v{e}tek, Jakub},
  title =	{{Near-Universally-Optimal Differentially Private Minimum Spanning Trees}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-367-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{329},
  editor =	{Bun, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2025.6},
  URN =		{urn:nbn:de:0030-drops-231337},
  doi =		{10.4230/LIPIcs.FORC.2025.6},
  annote =	{Keywords: differential privacy, universal optimality, minimum spanning trees}
}
  • Refine by Type
  • 29 Document/PDF
  • 22 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 19 2025
  • 2 2024
  • 1 2023
  • 1 2021
  • Show More...

  • Refine by Author
  • 5 Manurangsi, Pasin
  • 4 Steinke, Thomas
  • 3 Hoza, William M.
  • 3 Stemmer, Uri
  • 2 Cohen, Edith
  • Show More...

  • Refine by Series/Journal
  • 28 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 6 Security and privacy
  • 6 Theory of computation → Theory of database privacy and security
  • 5 Security and privacy → Privacy-preserving protocols
  • 5 Theory of computation → Pseudorandomness and derandomization
  • 2 Theory of computation
  • Show More...

  • Refine by Keyword
  • 6 Differential Privacy
  • 6 differential privacy
  • 3 Differential privacy
  • 3 pseudorandom generators
  • 2 Pseudorandomness
  • 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