22 Search Results for "Blasiok, Jaroslaw"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.32
Semirandom Planted Bipartite Subgraphs

Authors: Anand Louis and Kirtan Vora

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
There have been many recent works studying planted subgraphs problems. The semirandom planted bipartite subgraph problem is defined as follows. Starting with a vertex set V, an arbitrary subset S ⊂ V of size k is chosen, then an arbitrary bipartite graph is added on S. After this between each pair of vertices in S × (V ⧵ S) an edge is added independently with probability p, then an arbitrary graph is added on V⧵ S. The analogous semirandom planted clique problem, where S forms a clique, has been studied starting with the work of Fiege and Kilian [Uriel Feige and Joe Kilian, 2001]; recent work by [Blasiok et al., 2024; Venkatesan Guruswami and Hsin-Po Wang, 2025] gave an algorithm for this problem when k = Ω(√{n log n}). We give an algorithm for semirandom planted bipartite subgraph problem when k = Ω(√{n log n}) and the two color classes are roughly balanced. Our algorithms are essentially the same as the elegant greedy algorithm of [Blasiok et al., 2024]. We generalize their idea to our setting. Handling the arbitrary nature of the bipartite graph requires some new technical ideas and is our main technical contribution.
Cite as

Anand Louis and Kirtan Vora. Semirandom Planted Bipartite Subgraphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{louis_et_al:LIPIcs.SWAT.2026.32,
  author =	{Louis, Anand and Vora, Kirtan},
  title =	{{Semirandom Planted Bipartite Subgraphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.32},
  URN =		{urn:nbn:de:0030-drops-260681},
  doi =		{10.4230/LIPIcs.SWAT.2026.32},
  annote =	{Keywords: Semirandom Models, Spectral Algorithms, Planted Subgraphs, Random Graphs, Approximate Recovery Algorithms}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.21
The Importance of Being Smoothly Calibrated

Authors: Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, and Pranay Tankala

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

Abstract
Recent work has highlighted the centrality of smooth calibration [Sham Kakade and Dean Foster, 2008] as a robust measure of calibration error. We generalize, unify, and extend previous results on smooth calibration, both as a robust calibration measure, and as a step towards omniprediction, which enables predictions with low regret for downstream decision makers seeking to optimize some proper loss unknown to the predictor. - We present a new omniprediction guarantee for smoothly calibrated predictors, for the class of all bounded proper losses. We smooth the predictor by adding some noise to it, and compete against smoothed versions of any benchmark predictor on the space, where we add some noise to the predictor and then post-process it arbitrarily. The omniprediction error is bounded by the smooth calibration error of the predictor and the earth mover’s distance from the benchmark. We exhibit instances showing that this dependence cannot, in general, be improved. We show how this unifies and extends prior results [Dean P. Foster and Rakesh V. Vohra, 1998; Jason D. Hartline et al., 2025] on omniprediction from smooth calibration. - We present a crisp new characterization of smooth calibration in terms of the earth mover’s distance to the closest perfectly calibrated joint distribution of predictions and labels. This also yields a simpler proof of the relation to the lower distance to calibration from [Jaroslaw Blasiok et al., 2023]. - We use this to show that the upper distance to calibration cannot be estimated within a quadratic factor with sample complexity independent of the support size of the predictions. This is in contrast to the distance to calibration, where the corresponding problem was known to be information-theoretically impossible: no finite number of samples suffice [Jaroslaw Blasiok et al., 2023].
Cite as

Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, and Pranay Tankala. The Importance of Being Smoothly Calibrated. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gopalan_et_al:LIPIcs.FORC.2026.21,
  author =	{Gopalan, Parikshit and Stavropoulos, Konstantinos and Talwar, Kunal and Tankala, Pranay},
  title =	{{The Importance of Being Smoothly Calibrated}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{21:1--21:22},
  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.21},
  URN =		{urn:nbn:de:0030-drops-259945},
  doi =		{10.4230/LIPIcs.FORC.2026.21},
  annote =	{Keywords: Smooth Calibration, Omniprediction, Distance to Calibration}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.28
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank

Authors: Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Arina Smirnova

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

Abstract
Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform (algorithm) lower bounds and nonuniform (circuit) lower bounds in restricted circuit models. About a decade ago, Williams (STOC 2010) showed how to derive nonuniform lower bounds from uniform upper bounds: roughly, by designing a fast algorithm for checking satisfiability of circuits, one gets a lower bound for this circuit class. Since then, a number of results of this kind have been proved. For example, Jahanjou et al. (ICALP 2015) and Carmosino et al. (ITCS 2016) proved that if NSETH fails, then E^{NP} has series-parallel circuit size ω(n). One can also derive nonuniform lower bounds from nondeterministic uniform lower bounds. Perhaps the most well-known example is the Karp-Lipton theorem (STOC 1980): if Σ₂ ≠ Π₂, then NP ⊄ P/poly. Some recent examples include the following. Nederlof (STOC 2020) proved a lower bound on the matrix multiplication tensor rank under an assumption that TSP cannot be solved faster than in 2ⁿ time. Belova et al. (SODA 2024) proved that there exists an explicit polynomial family of arithmetic circuit size Ω(n^{δ}), for any δ > 0, assuming that MAX-3-SAT cannot be solved faster than in 2ⁿ nondeterministic time. Williams (FOCS 2024) proved an exponential lower bound for ETHR ∘ ETHR circuits under the Orthogonal Vectors conjecture. Whereas all the lower bounds above are proved under strong assumptions that might eventually be refuted, the revealed connections are of great interest and may still give further insights: one may be able to weaken the used assumptions or to construct generators from other fine-grained reductions. In this paper, we continue developing this line of research and show how uniform nondeterministic lower bounds can be used to construct generators of various types of combinatorial objects that are notoriously hard to analyze: Boolean functions of high circuit size, matrices of high rigidity, and tensors of high rank. Specifically, we prove the following. - If, for some ε and k, k-SAT cannot be solved in input-oblivious co-nondeterministic time O(2^{(1/2+ε)n}), then there exists a monotone Boolean function family in coNP of monotone circuit size 2^{Ω(n / log n)}. Combining this with the result above, we get win-win circuit lower bounds: either E^{NP{}} requires series-parallel circuits of size ω(n) or coNP requires monotone circuits of size 2^{Ω(n / log n)}. - If, for all ε > 0, MAX-3-SAT cannot be solved in co-nondeterministic time O(2^{(1 - ε)n}), then there exist small families of matrices with rigidity exceeding the best known constructions as well as small families of three-dimensional tensors of rank n^{1+Δ}, for some Δ > 0.
Cite as

Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, and Arina Smirnova. Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chukhin_et_al:LIPIcs.STACS.2026.28,
  author =	{Chukhin, Nikolai and Kulikov, Alexander S. and Mihajlin, Ivan and Smirnova, Arina},
  title =	{{Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{28:1--28:21},
  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.28},
  URN =		{urn:nbn:de:0030-drops-255177},
  doi =		{10.4230/LIPIcs.STACS.2026.28},
  annote =	{Keywords: computational complexity, circuit complexity, lower bounds, conditional lower bounds, monotone circuits, matrix rigidity, tensor rank, arithmetic circuits, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.4
Hardness of Clique Approximation for Monotone Circuits

Authors: Jarosław Błasiok and Linus Meierhöfer

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

Abstract
We consider a problem of approximating the size of the largest clique in a graph, using a monotone circuit. Concretely, we focus on distinguishing a random Erdős–Rényi graph 𝒢_{n,p}, with p = n^{-2/(α-1)} chosen st. with high probability it does not even contain an α-clique, from a random clique on β vertices (where α ≤ β). Using the approximation method of Razborov, Alon and Boppana showed in their influential work in 1987 that as long as √{α} β < n^{1-δ}/log n, this problem requires a monotone circuit of size n^Ω(δ√α), implying a lower bound of 2^Ω̃(n^{1/3}) for the exact version of the problem Clique_k when k≈ n^{2/3}. Recently, Cavalar, Kumar, and Rossman improved their result by showing a tight lower bound n^Ω(k), in a limited range k ≤ n^{1/3}, implying a comparable 2^Ω̃(n^{1/3}) lower bound after choosing the largest admissible k. We combine the ideas of Cavalar, Kumar and Rossman with recent breakthrough results on sunflower conjecture by Alweiss, Lovett, Wu, and Zhang to show that as long as α β < n^{1-δ}/log n, any monotone circuit rejecting 𝒢_{n,p} graph while accepting a β-clique needs to have size at least n^Ω(δ²α); this implies a stronger 2^Ω̃(√n) lower bound for the unrestricted version of the problem. We complement this result with a construction of an explicit monotone circuit of size O(n^{δ² α/2}) which rejects 𝒢_{n,p}, and accepts any graph containing β-clique whenever β > n^{1-δ}. In particular, those two theorems give a precise characterization of the smallest β-clique that can be distinguished from 𝒢_{n, 1/2}: when β > n / 2^{C √{log n}}, there is a polynomial-size circuit that solves it, while for β < n / 2^ω(√{log n}) every circuit needs size n^ω(1).
Cite as

Jarosław Błasiok and Linus Meierhöfer. Hardness of Clique Approximation for Monotone Circuits. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blasiok_et_al:LIPIcs.CCC.2025.4,
  author =	{B{\l}asiok, Jaros{\l}aw and Meierh\"{o}fer, Linus},
  title =	{{Hardness of Clique Approximation for Monotone Circuits}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{4:1--4:20},
  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.4},
  URN =		{urn:nbn:de:0030-drops-236987},
  doi =		{10.4230/LIPIcs.CCC.2025.4},
  annote =	{Keywords: circuit lower bounds, monotone circuits, sunflower conjecture}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.6
Near-Optimal Averaging Samplers and Matrix Samplers

Authors: Zhiyang Xun and David Zuckerman

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

Abstract
We present the first efficient averaging sampler that achieves asymptotically optimal randomness complexity and near-optimal sample complexity. For any δ < ε and any constant α > 0, our sampler uses m + O(log (1 / δ)) random bits to output t = O((1/ε² log 1/δ)^{1 + α}) samples Z_1, … , Z_t ∈ {0, 1}^m such that for any function f: {0, 1}^m → [0, 1], Pr[|1/t∑_{i=1}^t f(Z_i) - 𝔼[f]| ≤ ε] ≥ 1 - δ. The randomness complexity is optimal up to a constant factor, and the sample complexity is optimal up to the O((1/(ε²) log 1/(δ))^α) factor. Our technique generalizes to matrix samplers. A matrix sampler is defined similarly, except that f: {0, 1}^m → ℂ^{d×d} and the absolute value is replaced by the spectral norm. Our matrix sampler achieves randomness complexity m + Õ(log(d / δ)) and sample complexity O((1/ε² log d/δ)^{1 + α}) for any constant α > 0, both near-optimal with only a logarithmic factor in randomness complexity and an additional α exponent on the sample complexity. We use known connections with randomness extractors and list-decodable codes to give applications to these objects. Specifically, we give the first extractor construction with optimal seed length up to an arbitrarily small constant factor above 1, when the min-entropy k = β n for a large enough constant β < 1. Finally, we generalize the definition of averaging sampler to any normed vector space.
Cite as

Zhiyang Xun and David Zuckerman. Near-Optimal Averaging Samplers and Matrix Samplers. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 6:1-6:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{xun_et_al:LIPIcs.CCC.2025.6,
  author =	{Xun, Zhiyang and Zuckerman, David},
  title =	{{Near-Optimal Averaging Samplers and Matrix Samplers}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{6:1--6:28},
  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.6},
  URN =		{urn:nbn:de:0030-drops-237001},
  doi =		{10.4230/LIPIcs.CCC.2025.6},
  annote =	{Keywords: Pseudorandomness, Averaging Samplers, Randomness Extractors}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.36
Lifting with Colourful Sunflowers

Authors: Susanna F. de Rezende and Marc Vinyals

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

Abstract
We show that a generalization of the DAG-like query-to-communication lifting theorem, when proven using sunflowers over non-binary alphabets, yields lower bounds on the monotone circuit complexity and proof complexity of natural functions and formulas that are better than previously known results obtained using the approximation method. These include an n^Ω(k) lower bound for the clique function up to k ≤ n^{1/2-ε}, and an exp(Ω(n^{1/3-ε})) lower bound for a function in P.
Cite as

Susanna F. de Rezende and Marc Vinyals. Lifting with Colourful Sunflowers. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derezende_et_al:LIPIcs.CCC.2025.36,
  author =	{de Rezende, Susanna F. and Vinyals, Marc},
  title =	{{Lifting with Colourful Sunflowers}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{36:1--36:19},
  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.36},
  URN =		{urn:nbn:de:0030-drops-237303},
  doi =		{10.4230/LIPIcs.CCC.2025.36},
  annote =	{Keywords: lifting, sunflower, clique, colouring, monotone circuit, cutting planes}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.75
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model

Authors: Shiyuan Feng, William Swartworth, and David Woodruff

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

Abstract
We consider the heavy-hitters and F_p moment estimation problems in the sliding window model. For F_p moment estimation with 1 < p ≤ 2, we show that it is possible to give a (1± ε) multiplicative approximation to the F_p moment with 2/3 probability on any given window of size n using Õ(1/(ε^p)log² n + 1/(ε²)log n) bits of space. We complement this result with a lower bound showing that our algorithm gives tight bounds up to factors of log log n and log1/(ε). As a consequence of our F₂ moment estimation algorithm, we show that the heavy-hitters problem can be solved on an arbitrary window using O(1/(ε²)log² n) space which is tight.
Cite as

Shiyuan Feng, William Swartworth, and David Woodruff. Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 75:1-75:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.ICALP.2025.75,
  author =	{Feng, Shiyuan and Swartworth, William and Woodruff, David},
  title =	{{Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{75:1--75: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.75},
  URN =		{urn:nbn:de:0030-drops-234524},
  doi =		{10.4230/LIPIcs.ICALP.2025.75},
  annote =	{Keywords: sketching, streaming, heavy hitters, sliding window, moment estimation}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.16
Smooth Calibration and Decision Making

Authors: Jason Hartline, Yifan Wu, and Yunran Yang

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

Abstract
Calibration requires predictor outputs to be consistent with their Bayesian posteriors. For machine learning predictors that do not distinguish between small perturbations, calibration errors are continuous in predictions, e.g. smooth calibration error [Foster and Hart, 2018], distance to calibration [Błasiok et al., 2023]. On the contrary, decision-makers who use predictions make optimal decisions discontinuously in probabilistic space, experiencing loss from miscalibration discontinuously. Calibration errors for decision-making are thus discontinuous, e.g., Expected Calibration Error [Foster and Vohra, 1997], and Calibration Decision Loss [Hu and Wu, 2024]. Thus, predictors with a low calibration error for machine learning may suffer a high calibration error for decision-making, i.e. they may not be trustworthy for decision-makers optimizing assuming their predictions are correct. It is natural to ask if post-processing a predictor with a low calibration error for machine learning is without loss to achieve a low calibration error for decision-making. In our paper, we show post-processing an online predictor with ε distance to calibration achieves O(√{ε}) ECE and CDL, which is asymptotically optimal. The post-processing algorithm adds noise to make predictions differentially private. The optimal bound from low distance to calibration predictors from post-processing is non-optimal compared with existing online calibration algorithms that directly optimize for ECE and CDL.
Cite as

Jason Hartline, Yifan Wu, and Yunran Yang. Smooth Calibration and Decision Making. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 16:1-16:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hartline_et_al:LIPIcs.FORC.2025.16,
  author =	{Hartline, Jason and Wu, Yifan and Yang, Yunran},
  title =	{{Smooth Calibration and Decision Making}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{16:1--16:26},
  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.16},
  URN =		{urn:nbn:de:0030-drops-231438},
  doi =		{10.4230/LIPIcs.FORC.2025.16},
  annote =	{Keywords: Calibration, calibration errors, decision making, differential privacy}
}
Document
DOI: 10.4230/LIPIcs.FORC.2025.22
When Does a Predictor Know Its Own Loss?

Authors: Aravind Gollakota, Parikshit Gopalan, Aayush Karan, Charlotte Peale, and Udi Wieder

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

Abstract
Given a predictor and a loss function, how well can we predict the loss that the predictor will incur on an input? This is the problem of loss prediction, a key computational task associated with uncertainty estimation for a predictor. In a classification setting, a predictor will typically predict a distribution over labels and hence have its own estimate of the loss that it will incur, given by the entropy of the predicted distribution. Should we trust this estimate? In other words, when does the predictor know what it knows and what it does not know? In this work we study the theoretical foundations of loss prediction. Our main contribution is to establish tight connections between nontrivial loss prediction and certain forms of multicalibration [Ursula Hébert-Johnson et al., 2018], a multigroup fairness notion that asks for calibrated predictions across computationally identifiable subgroups. Formally, we show that a loss predictor that is able to improve on the self-estimate of a predictor yields a witness to a failure of multicalibration, and vice versa. This has the implication that nontrivial loss prediction is in effect no easier or harder than auditing for multicalibration. We support our theoretical results with experiments that show a robust positive correlation between the multicalibration error of a predictor and the efficacy of training a loss predictor.
Cite as

Aravind Gollakota, Parikshit Gopalan, Aayush Karan, Charlotte Peale, and Udi Wieder. When Does a Predictor Know Its Own Loss?. In 6th Symposium on Foundations of Responsible Computing (FORC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 329, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gollakota_et_al:LIPIcs.FORC.2025.22,
  author =	{Gollakota, Aravind and Gopalan, Parikshit and Karan, Aayush and Peale, Charlotte and Wieder, Udi},
  title =	{{When Does a Predictor Know Its Own Loss?}},
  booktitle =	{6th Symposium on Foundations of Responsible Computing (FORC 2025)},
  pages =	{22:1--22:22},
  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.22},
  URN =		{urn:nbn:de:0030-drops-231490},
  doi =		{10.4230/LIPIcs.FORC.2025.22},
  annote =	{Keywords: loss prediction, multicalibration, active learning, algorithmic fairness, calibration, predictive uncertainty, uncertainty estimation, machine learning theory}
}
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}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.68
New Pseudorandom Generators and Correlation Bounds Using Extractors

Authors: Vinayak M. Kumar

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

Abstract
We establish new correlation bounds and pseudorandom generators for a collection of computation models. These models are all natural generalization of structured low-degree 𝔽₂-polynomials that we did not have correlation bounds for before. In particular: - We construct a PRG for width-2 poly(n)-length branching programs which read d bits at a time with seed length 2^O(√{log n}) ⋅ d²log²(1/ε). This comes quadratically close to optimal dependence in d and log(1/ε). Improving the dependence on n would imply nontrivial PRGs for log n-degree 𝔽₂-polynomials. The previous PRG by Bogdanov, Dvir, Verbin, and Yehudayoff had an exponentially worse dependence on d with seed length of O(dlog n + d2^dlog(1/ε)). - We provide the first nontrivial (and nearly optimal) correlation bounds and PRGs against size-n^Ω(log n) AC⁰ circuits with either n^{.99} SYM gates (computing an arbitrary symmetric function) or n^{.49} THR gates (computing an arbitrary linear threshold function). This is a generalization of sparse 𝔽₂-polynomials, which can be simulated by an AC⁰ circuit with one parity gate at the top. Previous work of Servedio and Tan only handled n^{.49} SYM gates or n^{.24} THR gates, and previous work of Lovett and Srinivasan only handled polynomial-size circuits. - We give exponentially small correlation bounds against degree-n^O(1) 𝔽₂-polynomials which are set-multilinear over some arbitrary partition of the input into n^{1-O(1)} parts (noting that at n parts, we recover all low degree polynomials). This vastly generalizes correlation bounds against degree-d polynomials which are set-multilinear over a fixed partition into d blocks, which were established by Bhrushundi, Harsha, Hatami, Kopparty, and Kumar. The common technique behind all of these results is to fortify a hard function with the right type of extractor to obtain stronger correlation bounds for more general models of computation. Although this technique has been used in previous work, they rely on the model simplifying drastically under random restrictions. We view our results as a proof of concept that such fortification can be done even for classes that do not enjoy such behavior.
Cite as

Vinayak M. Kumar. New Pseudorandom Generators and Correlation Bounds Using Extractors. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 68:1-68:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kumar:LIPIcs.ITCS.2025.68,
  author =	{Kumar, Vinayak M.},
  title =	{{New Pseudorandom Generators and Correlation Bounds Using Extractors}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{68:1--68:23},
  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.68},
  URN =		{urn:nbn:de:0030-drops-226961},
  doi =		{10.4230/LIPIcs.ITCS.2025.68},
  annote =	{Keywords: Pseudorandom Generators, Correlation Bounds, Constant-Depth Circuits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.17
Loss Minimization Yields Multicalibration for Large Neural Networks

Authors: Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, and Preetum Nakkiran

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Multicalibration is a notion of fairness for predictors that requires them to provide calibrated predictions across a large set of protected groups. Multicalibration is known to be a distinct goal than loss minimization, even for simple predictors such as linear functions. In this work, we consider the setting where the protected groups can be represented by neural networks of size k, and the predictors are neural networks of size n > k. We show that minimizing the squared loss over all neural nets of size n implies multicalibration for all but a bounded number of unlucky values of n. We also give evidence that our bound on the number of unlucky values is tight, given our proof technique. Previously, results of the flavor that loss minimization yields multicalibration were known only for predictors that were near the ground truth, hence were rather limited in applicability. Unlike these, our results rely on the expressivity of neural nets and utilize the representation of the predictor.
Cite as

Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, and Preetum Nakkiran. Loss Minimization Yields Multicalibration for Large Neural Networks. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 17:1-17:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blasiok_et_al:LIPIcs.ITCS.2024.17,
  author =	{B{\l}asiok, Jaros{\l}aw and Gopalan, Parikshit and Hu, Lunjia and Kalai, Adam Tauman and Nakkiran, Preetum},
  title =	{{Loss Minimization Yields Multicalibration for Large Neural Networks}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{17:1--17:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.17},
  URN =		{urn:nbn:de:0030-drops-195452},
  doi =		{10.4230/LIPIcs.ITCS.2024.17},
  annote =	{Keywords: Multi-group fairness, loss minimization, neural networks}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.16
Matrix Multiplication and Number on the Forehead Communication

Authors: Josh Alman and Jarosław Błasiok

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Three-player Number On the Forehead communication may be thought of as a three-player Number In the Hand promise model, in which each player is given the inputs that are supposedly on the other two players' heads, and promised that they are consistent with the inputs of the other players. The set of all allowed inputs under this promise may be thought of as an order-3 tensor. We surprisingly observe that this tensor is exactly the matrix multiplication tensor, which is widely studied in the design of fast matrix multiplication algorithms. Using this connection, we prove a number of results about both Number On the Forehead communication and matrix multiplication, each by using known results or techniques about the other. For example, we show how the Laser method, a key technique used to design the best matrix multiplication algorithms, can also be used to design communication protocols for a variety of problems. We also show how known lower bounds for Number On the Forehead communication can be used to bound properties of the matrix multiplication tensor such as its zeroing out subrank. Finally, we substantially generalize known methods based on slice-rank for studying communication, and show how they directly relate to the matrix multiplication exponent ω.
Cite as

Josh Alman and Jarosław Błasiok. Matrix Multiplication and Number on the Forehead Communication. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alman_et_al:LIPIcs.CCC.2023.16,
  author =	{Alman, Josh and B{\l}asiok, Jaros{\l}aw},
  title =	{{Matrix Multiplication and Number on the Forehead Communication}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.16},
  URN =		{urn:nbn:de:0030-drops-182861},
  doi =		{10.4230/LIPIcs.CCC.2023.16},
  annote =	{Keywords: Number on the forehead, communication complexity, matrix multiplication}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.4
Communication Complexity of Inner Product in Symmetric Normed Spaces

Authors: Alexandr Andoni, Jarosław Błasiok, and Arnold Filtser

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We introduce and study the communication complexity of computing the inner product of two vectors, where the input is restricted w.r.t. a norm N on the space ℝⁿ. Here, Alice and Bob hold two vectors v,u such that ‖v‖_N ≤ 1 and ‖u‖_{N^*} ≤ 1, where N^* is the dual norm. The goal is to compute their inner product ⟨v,u⟩ up to an ε additive term. The problem is denoted by IP_N, and generalizes important previously studied problems, such as: (1) Computing the expectation 𝔼_{x∼𝒟}[f(x)] when Alice holds 𝒟 and Bob holds f is equivalent to IP_{𝓁₁}. (2) Computing v^TAv where Alice has a symmetric matrix with bounded operator norm (denoted S_∞) and Bob has a vector v where ‖v‖₂ = 1. This problem is complete for quantum communication complexity and is equivalent to IP_{S_∞}. We systematically study IP_N, showing the following results, near tight in most cases: 1) For any symmetric norm N, given ‖v‖_N ≤ 1 and ‖u‖_{N^*} ≤ 1 there is a randomized protocol using 𝒪̃(ε^{-6} log n) bits of communication that returns a value in ⟨u,v⟩±ε with probability 2/3 - we will denote this by ℛ_{ε,1/3}(IP_N) ≤ 𝒪̃(ε^{-6} log n). In a special case where N = 𝓁_p and N^* = 𝓁_q for p^{-1} + q^{-1} = 1, we obtain an improved bound ℛ_{ε,1/3}(IP_{𝓁_p}) ≤ 𝒪(ε^{-2} log n), nearly matching the lower bound ℛ_{ε, 1/3}(IP_{𝓁_p}) ≥ Ω(min(n, ε^{-2})). 2) One way communication complexity ℛ^{→}_{ε,δ}(IP_{𝓁_p}) ≤ 𝒪(ε^{-max(2,p)}⋅ log n/ε), and a nearly matching lower bound ℛ^{→}_{ε, 1/3}(IP_{𝓁_p}) ≥ Ω(ε^{-max(2,p)}) for ε^{-max(2,p)} ≪ n. 3) One way communication complexity ℛ^{→}_{ε,δ}(N) for a symmetric norm N is governed by the distortion of the embedding 𝓁_∞^k into N. Specifically, while a small distortion embedding easily implies a lower bound Ω(k), we show that, conversely, non-existence of such an embedding implies protocol with communication k^𝒪(log log k) log² n. 4) For arbitrary origin symmetric convex polytope P, we show ℛ_{ε,1/3}(IP_{N}) ≤ 𝒪(ε^{-2} log xc(P)), where N is the unique norm for which P is a unit ball, and xc(P) is the extension complexity of P (i.e. the smallest number of inequalities describing some polytope P' s.t. P is projection of P').
Cite as

Alexandr Andoni, Jarosław Błasiok, and Arnold Filtser. Communication Complexity of Inner Product in Symmetric Normed Spaces. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{andoni_et_al:LIPIcs.ITCS.2023.4,
  author =	{Andoni, Alexandr and B{\l}asiok, Jaros{\l}aw and Filtser, Arnold},
  title =	{{Communication Complexity of Inner Product in Symmetric Normed Spaces}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.4},
  URN =		{urn:nbn:de:0030-drops-175077},
  doi =		{10.4230/LIPIcs.ITCS.2023.4},
  annote =	{Keywords: communication complexity, symmetric norms}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.53
Fourier Growth of Structured 𝔽₂-Polynomials and Applications

Authors: Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, and Emanuele Viola

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

Abstract
We analyze the Fourier growth, i.e. the L₁ Fourier weight at level k (denoted L_{1,k}), of various well-studied classes of "structured" m F₂-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [Chattopadhyay et al., 2019; Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2020] which show that upper bounds on Fourier growth (even at level k = 2) give unconditional pseudorandom generators. Our main structural results on Fourier growth are as follows: - We show that any symmetric degree-d m F₂-polynomial p has L_{1,k}(p) ≤ Pr [p = 1] ⋅ O(d)^k. This quadratically strengthens an earlier bound that was implicit in [Omer Reingold et al., 2013]. - We show that any read-Δ degree-d m F₂-polynomial p has L_{1,k}(p) ≤ Pr [p = 1] ⋅ (k Δ d)^{O(k)}. - We establish a composition theorem which gives L_{1,k} bounds on disjoint compositions of functions that are closed under restrictions and admit L_{1,k} bounds. Finally, we apply the above structural results to obtain new unconditional pseudorandom generators and new correlation bounds for various classes of m F₂-polynomials.
Cite as

Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, and Emanuele Viola. Fourier Growth of Structured 𝔽₂-Polynomials and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 53:1-53:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{blasiok_et_al:LIPIcs.APPROX/RANDOM.2021.53,
  author =	{B{\l}asiok, Jaros{\l}aw and Ivanov, Peter and Jin, Yaonan and Lee, Chin Ho and Servedio, Rocco A. and Viola, Emanuele},
  title =	{{Fourier Growth of Structured \mathbb{F}₂-Polynomials and Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{53:1--53:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.53},
  URN =		{urn:nbn:de:0030-drops-147462},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.53},
  annote =	{Keywords: Fourier analysis, Pseudorandomness, Fourier growth}
}
  • Refine by Type
  • 22 Document/PDF
  • 11 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 8 2025
  • 1 2024
  • 2 2023
  • 2 2021
  • Show More...

  • Refine by Author
  • 5 Błasiok, Jarosław
  • 3 Blasiok, Jaroslaw
  • 3 Gopalan, Parikshit
  • 2 Nakkiran, Preetum
  • 2 Nelson, Jelani
  • Show More...

  • Refine by Series/Journal
  • 22 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Circuit complexity
  • 5 Theory of computation → Pseudorandomness and derandomization
  • 4 Theory of computation → Machine learning theory
  • 3 Theory of computation → Communication complexity
  • 2 Theory of computation → Sketching and sampling
  • Show More...

  • Refine by Keyword
  • 2 Fourier analysis
  • 2 Pseudorandomness
  • 2 communication complexity
  • 2 differential privacy
  • 2 moment estimation
  • 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