27 Search Results for "Lin, Huijia (Rachel)"

Volume

LIPIcs, Volume 368

7th Symposium on Foundations of Responsible Computing (FORC 2026)

FORC 2026, Harvard University, Cambridge, MA, USA, June 3-5, 2026

Editors: Huijia (Rachel) Lin

Document
DOI: 10.4230/LIPIcs.FORC.2026.2
Learning Rate Scheduling with Matrix Factorization for Private Training

Authors: Nikita P. Kalinin and Joel Daniel Andersson

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

Abstract
We study differentially private model training with stochastic gradient descent under learning rate scheduling and correlated noise. Although correlated noise, in particular via matrix factorizations, has been shown to improve accuracy, prior theoretical work focused primarily on the prefix-sum workload. That workload assumes a constant learning rate, whereas in practice learning rate schedules are widely used to accelerate training and improve convergence. We close this gap by deriving general upper and lower bounds for a broad class of learning rate schedules in both single- and multi-epoch settings. Building on these results, we propose a learning-rate-aware factorization that achieves improvements over prefix-sum factorizations under both MaxSE and MeanSE error metrics. Our theoretical analysis yields memory-efficient constructions suitable for practical deployment, and experiments on CIFAR-10 and IMDB datasets confirm that schedule-aware factorizations improve accuracy in private training.
Cite as

Nikita P. Kalinin and Joel Daniel Andersson. Learning Rate Scheduling with Matrix Factorization for Private Training. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kalinin_et_al:LIPIcs.FORC.2026.2,
  author =	{Kalinin, Nikita P. and Andersson, Joel Daniel},
  title =	{{Learning Rate Scheduling with Matrix Factorization for Private Training}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{2:1--2:21},
  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.2},
  URN =		{urn:nbn:de:0030-drops-259738},
  doi =		{10.4230/LIPIcs.FORC.2026.2},
  annote =	{Keywords: differential privacy, machine learning, matrix factorization}
}
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
Extended Abstract
DOI: 10.4230/LIPIcs.FORC.2026.5
Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting (Extended Abstract)

Authors: Monika Henzinger, Nikita Kalinin, and Jalaj Upadhyay

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

Abstract
The factorization norms of the lower-triangular all-ones n× n matrix, γ₂(M_{count}) and γ_{F}(M_{count}), play a central role in differential privacy as they are used to give theoretical justification of the accuracy of the only known production-level private training algorithm of deep neural networks by Google. Prior to this work, the best known upper bound on γ₂(M_{count}) was 1 + (log(n))/π by Mathias (Linear Algebra and Applications, 1993), and the best known lower bound was 1/π (2 + log((2n+1)/3)) ≈ 0.507 + (log(n))/π (Matoušek, Nikolov, Talwar, IMRN 2020), where log(⋅) is the natural logarithm. Recently, Henzinger and Upadhyay (SODA 2025) gave the first explicit factorization that meets the bound of Mathias (1993) and asked whether there exists an explicit factorization that improves on Mathias’ bound. We answer this question in the affirmative. Additionally, we improve the lower bound significantly. More specifically, we show that o(1) + 0.701 + (log(n))/π ≤ γ₂(M_{count}) ≤ 0.846 + (log(n))/π + o(1). That is, we reduce the gap between the upper and lower bound to 0.14 + o(1) and first improvement in over three decades. Additionally, we show that our factors achieve a better upper bound for γ_{F}(M_{count}) compared to prior work, and we also establish an improved lower bound for γ_{F}(M_{count}): o(1) + 0.701 + (log(n))/π ≤ γ_{F}(M_{count}) ≤ 0.748 + (log(n))/π + o(1). That is, the gap between the lower and upper bound provided by our explicit factorization is 0.047 + o(1).
Cite as

Monika Henzinger, Nikita Kalinin, and Jalaj Upadhyay. Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting (Extended Abstract). In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{henzinger_et_al:LIPIcs.FORC.2026.5,
  author =	{Henzinger, Monika and Kalinin, Nikita and Upadhyay, Jalaj},
  title =	{{Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{5:1--5:1},
  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.5},
  URN =		{urn:nbn:de:0030-drops-259767},
  doi =		{10.4230/LIPIcs.FORC.2026.5},
  annote =	{Keywords: Differential privacy, continual release, factorization norm}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.6
Escaping the Subprime Trap in Algorithmic Lending

Authors: Adam Bouyamourn and Alexander Williams Tolbert

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

Abstract
Disparities in lending to minority applicants persist even as algorithmic lending finds widespread adoption. We study the role of risk-management constraints, specifically Value-at-Risk and Expected Shortfall, in inducing inequality in loan approval decisions, even among applicants who are equally creditworthy. We contribute an analysis of 431,551 loan applications recorded under the Home Mortgage Disclosure Act, illustrating that disparities in data quality are associated with higher rates of loan denial and higher interest rate spreads for Black borrowers. We develop a formal model in which a mainstream bank (low-interest) is more sensitive to variance risk than a subprime bank (high-interest). If the mainstream bank has an inflated prior belief about the variance of the minority group, it may deny that group credit indefinitely, never learning the true risk of lending to that group, while the subprime lender serves this population at higher rates. We call this "The Subprime Trap": an equilibrium in which minority borrowers can borrow only from high-cost lenders, even when they are as creditworthy as majority applicants. We show that a finite subsidy can help minority groups escape the trap by covering enough of the mainstream bank’s downside so that it can afford to lend to, and thereby learn the true risk of lending to, the minority group. Once the mainstream bank has observed sufficiently many loans, its beliefs converge to the true underlying risk, and competition drives down the interest rates of subprime loans.
Cite as

Adam Bouyamourn and Alexander Williams Tolbert. Escaping the Subprime Trap in Algorithmic Lending. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 6:1-6:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bouyamourn_et_al:LIPIcs.FORC.2026.6,
  author =	{Bouyamourn, Adam and Tolbert, Alexander Williams},
  title =	{{Escaping the Subprime Trap in Algorithmic Lending}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{6:1--6:27},
  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.6},
  URN =		{urn:nbn:de:0030-drops-259777},
  doi =		{10.4230/LIPIcs.FORC.2026.6},
  annote =	{Keywords: Algorithmic fairness, algorithmic lending, Risk management, Value-at-Risk, Algorithmic Philosophy}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.7
When to Ask a Question: Understanding Communication Strategies in Generative AI Tools

Authors: Charlotte Park, Kate Donahue, and Manish Raghavan

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

Abstract
Generative AI models differ from traditional machine learning tools in that they allow users to provide as much or as little information as they choose in their inputs. This flexibility often leads users to omit certain details, relying on the models to infer and fill in under-specified information based on distributional knowledge of user preferences. Such inferences may privilege majority viewpoints and disadvantage users with atypical preferences, raising concerns about fairness. Unlike more traditional recommender systems, LLMs can explicitly solicit more information from users through natural language. However, while directly eliciting user preferences could increase personalization and mitigate inequality, excessive querying places a burden on users who value efficiency. We develop a stylized model of user-LLM interaction and develop an objective that captures tradeoff between user burden and preference representation. Building on the observation that individual preferences are often correlated, we analyze how AI systems should balance inference and elicitation, characterizing the optimal amount of information to solicit before content generation. Ultimately, we show that information elicitation can mitigate the systematic biases of preference inference, enabling the design of generative tools that better incorporate diverse user perspectives while maintaining efficiency. We complement this theoretical analysis with an empirical evaluation illustrating the model’s predictions and exploring their practical implications.
Cite as

Charlotte Park, Kate Donahue, and Manish Raghavan. When to Ask a Question: Understanding Communication Strategies in Generative AI Tools. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{park_et_al:LIPIcs.FORC.2026.7,
  author =	{Park, Charlotte and Donahue, Kate and Raghavan, Manish},
  title =	{{When to Ask a Question: Understanding Communication Strategies in Generative AI Tools}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{7:1--7:25},
  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.7},
  URN =		{urn:nbn:de:0030-drops-259782},
  doi =		{10.4230/LIPIcs.FORC.2026.7},
  annote =	{Keywords: human-AI interaction, user modeling, personalization}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.8
Can We Watermark Low-Entropy LLM Outputs?

Authors: Noam Mazor, Andrew Morgan, and Rafael Pass

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

Abstract
A recent and exciting thread of work focuses on developing methods for watermarking the output of large language models (LLMs). We focus on provably undetectable watermarking - that is, schemes that do not alter the output distribution of the LLM, yet enable embedding a watermark in the output that identifies the output as having been generated by the particular LLM. Furthermore, the watermark should be hard to remove by an adversary that may potentially edit, insert, or delete tokens from the watermarked output. Indeed, recent work (Christ et al. [COLT'24], Christ et al. [CRYPTO’24], Golowich et al. [NeuroIPS’24]) shows how to develop such schemes that are robust against a constant fraction of substitutions, or even against a constant fraction of arbitrary edits. These works, however, make strong assumptions on the amount of entropy present in the output of the LLM. Most notably, they all require constant entropy rate - that is, a constant fraction of the tokens in a sufficiently long substring of the output need to have empirical entropy at least O(log |T|), where T is the alphabet of tokens, and Golowich et al. additionally require T to be larger than the security parameter. In this work, we consider the question of whether we can also watermark the outputs of LLMs when the per-token entropy is just a constant, discarding the dependence on the alphabet size or security parameter. In this regime, we construct: - A watermarking scheme robust against random substitutions (assuming subexponential LPN, as in Christ et al. [CRYPTO’24]) - A watermarking scheme robust against random substitutions and random deletions, given either the additional heuristic assumption that the output of the LLM only introduces random errors (analogous to the assumption made by Christ et al. [CRYPTO’24]) or a construction of a pseudorandom error-correcting code robust to adversarial substitutions and random deletions.
Cite as

Noam Mazor, Andrew Morgan, and Rafael Pass. Can We Watermark Low-Entropy LLM Outputs?. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mazor_et_al:LIPIcs.FORC.2026.8,
  author =	{Mazor, Noam and Morgan, Andrew and Pass, Rafael},
  title =	{{Can We Watermark Low-Entropy LLM Outputs?}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{8:1--8: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.8},
  URN =		{urn:nbn:de:0030-drops-259809},
  doi =		{10.4230/LIPIcs.FORC.2026.8},
  annote =	{Keywords: Cryptography, Generative Models, Watermarking, Pseudorandom Codes}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.9
Serving Clients Fairly: On Facility Location and k-Median with Fair Outliers

Authors: Rajni Dabas, Samir Khuller, and Emilie Rivkin

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

Abstract
Classical clustering problems such as Facility Location and k-Median aim to efficiently serve a set of clients from a subset of facilities - minimizing the total cost of facility openings and client assignments in Facility Location, and minimizing assignment (service) cost under a facility count constraint in k-Median. These problems are highly sensitive to outliers, and therefore researchers have studied variants that allow excluding a small number of clients as outliers to reduce cost. However, in many real-world settings, clients belong to different demographic or functional groups, and unconstrained outlier removal can disproportionately exclude certain groups, raising fairness concerns, especially when the facilities correspond to critically needed facilities for emergencies such as fire stations, hospitals and other emergency services. We study Facility Location with Fair Outliers, where each group is allowed a specified number of outliers, and the objective is to minimize total cost while respecting group-wise fairness constraints. We present a bicriteria approximation with a O(1/ε) approximation factor and (1+ 2ε) factor violation in outliers per group. For k-Median with Fair Outliers, we design a bicriteria approximation with a 4(1+ω/ε) approximation factor and (ω + ε) violation in outliers per group improving on prior work by avoiding dependence on k in outlier violations. We also prove that the problems are W[1]-hard parameterized by ω. We complement our algorithmic contributions with a detailed empirical analysis, demonstrating that fairness can be achieved with negligible increase in cost and that the integrality gap of the standard LP is small in practice.
Cite as

Rajni Dabas, Samir Khuller, and Emilie Rivkin. Serving Clients Fairly: On Facility Location and k-Median with Fair Outliers. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dabas_et_al:LIPIcs.FORC.2026.9,
  author =	{Dabas, Rajni and Khuller, Samir and Rivkin, Emilie},
  title =	{{Serving Clients Fairly: On Facility Location and k-Median with Fair Outliers}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{9:1--9:19},
  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.9},
  URN =		{urn:nbn:de:0030-drops-259812},
  doi =		{10.4230/LIPIcs.FORC.2026.9},
  annote =	{Keywords: Approximation algorithms, fairness}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.10
Packing Compact Subgraphs with Applications to Districting

Authors: Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu

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

Abstract
Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e.g., having constant radius from a single center vertex) and that satisfy additional composition requirements, such as a minimum population/weight threshold or balanced weight types (e.g., political affiliations). We aim to maximize coverage by disjoint districts that meet these requirements. In this work, we present new results that substantially improve the previously known bounds on balanced star districts for planar and minor-free graphs [Prathamesh Dharangutte et al., 2025]. In particular, we improve the approximation factor from O(log n) to O(1) for packing balanced star districts using the exact same algorithm, but with a refined analysis. We also extend the results beyond planar graphs to minor-free graphs and an even broader family of graphs of bounded expansion. Additionally, we obtain an O(1) approximation for packing radius-k districts (with a constant k) in planar and apex-minor-free graphs. In order to get a (1+ε) approximation on the max coverage, we show that this can be achieved if we allow a slight relaxation of the balancedness parameters (by a factor that can be made arbitrarily close to 1), for bounded radius-k districts on planar and apex-minor-free graphs. We show that all of these results can also be obtained if we enforce a minimum weight threshold for each district as the composition requirement, rather than balancedness. We present various results on hardness and hardness of approximation for this variant, by graph and district types.
Cite as

Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu. Packing Compact Subgraphs with Applications to Districting. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.FORC.2026.10,
  author =	{Chen, Ho-Lin and Chou, Po-Yu and Dharangutte, Prathamesh and Gao, Jie and Huang, Shang-En and Yu, Fang-Yi},
  title =	{{Packing Compact Subgraphs with Applications to Districting}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{10:1--10:25},
  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.10},
  URN =		{urn:nbn:de:0030-drops-259820},
  doi =		{10.4230/LIPIcs.FORC.2026.10},
  annote =	{Keywords: Approximation algorithms, algorithmic fairness}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.11
Limitations on Accurate, Trusted, Human-Level Reasoning

Authors: Rina Panigrahy and Vatsal Sharan

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

Abstract
We identify a fundamental incompatibility between the goals of accuracy, trust, and human-level reasoning in artificial intelligence (AI) systems, for strict mathematical definitions of these notions. We define accuracy of a system as the property that it never makes any false claims when it has the ability to abstain from making a prediction on any input, and trust as the assumption that the system is accurate. We define human-level reasoning as the property of an AI system always matching or exceeding human capability. Our core finding is that - for our formal definitions of these notions - an accurate and trusted AI system cannot be a human-level reasoning system: for such an accurate, trusted system there are task instances which are easily and provably solvable by a human but not by the system. Our proofs draw parallels to Gödel’s incompleteness theorems and Turing’s proof of the undecidability of the halting problem, and can be regarded as interpretations of Gödel’s and Turing’s results. Key to our proof is the formalization of the notion of trust, which allows us to separate the intrinsic property of a system (being accurate) from its epistemic status (being trusted).
Cite as

Rina Panigrahy and Vatsal Sharan. Limitations on Accurate, Trusted, Human-Level Reasoning. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{panigrahy_et_al:LIPIcs.FORC.2026.11,
  author =	{Panigrahy, Rina and Sharan, Vatsal},
  title =	{{Limitations on Accurate, Trusted, Human-Level Reasoning}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{11:1--11:21},
  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.11},
  URN =		{urn:nbn:de:0030-drops-259840},
  doi =		{10.4230/LIPIcs.FORC.2026.11},
  annote =	{Keywords: Accuracy, Safety, Trust, Complexity-theoretic limitations}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.12
Tradeoffs in Privacy, Welfare, and Fairness for Facility Location

Authors: Sara Fish, Yannai A. Gonczarowski, Jason Z. Tang, and Salil Vadhan

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

Abstract
The differentially private (DP) facility location problem seeks to determine a socially optimal placement for a public facility while ensuring that each participating agent’s location remains private. In order to privatize its input data, a DP mechanism must inject noise into its output distribution, producing a placement that will have lower expected social welfare than the optimal spot for the facility. The privacy-induced welfare loss can be viewed as the "cost of privacy," illustrating a tradeoff between social welfare and privacy that has been the focus of prior work. Yet, the imposition of privacy also induces a third consideration that has not been similarly studied: fairness in how the "cost of privacy" is distributed across individuals. For instance, a mechanism may satisfy differential privacy with minimal social welfare loss, yet still be undesirable if that loss falls entirely on one individual. In this paper, we quantify this new notion of unfairness and design mechanisms for facility location that attempt to simultaneously optimize across these three objectives of privacy, social welfare, and fairness. Under this setup, we first derive an impossibility result, showing that privacy and fairness cannot be simultaneously guaranteed over all possible datasets that could represent the locations of individuals in a population. We then consider a relaxation of the original problem that still requires worst-case differential privacy, but only seeks fairness and appealing social welfare over smaller, more "realistic-looking" families of datasets. For this relaxation, we construct a DP mechanism and demonstrate that it is simultaneously optimal (or, for a harder family of datasets, near-optimal up to small factors) on fairness and social welfare. This suggests that while there is a tradeoff between privacy and each of social welfare and fairness, there is no additional tradeoff when we consider all three objectives simultaneously, provided that the population data is sufficiently natural.
Cite as

Sara Fish, Yannai A. Gonczarowski, Jason Z. Tang, and Salil Vadhan. Tradeoffs in Privacy, Welfare, and Fairness for Facility Location. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fish_et_al:LIPIcs.FORC.2026.12,
  author =	{Fish, Sara and Gonczarowski, Yannai A. and Tang, Jason Z. and Vadhan, Salil},
  title =	{{Tradeoffs in Privacy, Welfare, and Fairness for Facility Location}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{12:1--12: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.12},
  URN =		{urn:nbn:de:0030-drops-259858},
  doi =		{10.4230/LIPIcs.FORC.2026.12},
  annote =	{Keywords: differential privacy, facility location, fairness, mechanism design}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.13
Inducing Efficient and Equitable Professional Networks Through Link Recommendations

Authors: Cynthia Dwork, Chris Hays, Lunjia Hu, Nicole Immorlica, and Juan Perdomo

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

Abstract
Professional networks are a key determinant of individuals’ labor market outcomes. They may also play a role in either exacerbating or ameliorating inequality of opportunity across social groups. We initiate an investigation into the positive role that a professional networking platform can play when network members have different degrees of off-platform privilege. In a theoretical model, we show that the set of link recommendation policies that reduce costs between privileged and unprivileged individuals yield equilibria that are welfare-improving over all possible equilibria, compared to those obtained when not recommending links or recommending some smaller fraction of cross-group links. We next investigate the implications of platforms that do not intervene on the network formation process. We show that, absent intervention, inequality can increase relative to starting privilege levels even without exogenous in-group preferences, confirming and complementing existing theoretical literature. Increased inequality emerges from the differential leverage privileged and unprivileged individuals have in forming connections due to their asymmetric ex ante prospects. This is a formalization of a source of inequality in the labor market which has not been previously explored. These two findings reveal a stark reality: professional networking platforms that fail to foster integration in the link formation process risk reducing the platform’s utility to its users and exacerbating existing labor market inequality.
Cite as

Cynthia Dwork, Chris Hays, Lunjia Hu, Nicole Immorlica, and Juan Perdomo. Inducing Efficient and Equitable Professional Networks Through Link Recommendations. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dwork_et_al:LIPIcs.FORC.2026.13,
  author =	{Dwork, Cynthia and Hays, Chris and Hu, Lunjia and Immorlica, Nicole and Perdomo, Juan},
  title =	{{Inducing Efficient and Equitable Professional Networks Through Link Recommendations}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{13:1--13: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.13},
  URN =		{urn:nbn:de:0030-drops-259863},
  doi =		{10.4230/LIPIcs.FORC.2026.13},
  annote =	{Keywords: Professional networks, Inequality, Link Recommendations}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.14
Fair Multi-Agent Persuasion with Submodular Constraints

Authors: Yannan Bai, Kamesh Munagala, Yiheng Shen, and Davidson Zhu

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

Abstract
We study the problem of selection in the context of Bayesian persuasion. We are given multiple agents with hidden values (or quality scores), to whom resources must be allocated by a welfare-maximizing decision-maker. An intermediary with knowledge of the agents' values seeks to influence the outcome of the selection by designing informative signals and providing tie-breaking policies, so that when the receiver maximizes welfare over the resulting posteriors, the expected utilities of the agents (where utility is defined as allocation times value) achieve certain fairness properties. The fairness measure we will use is majorization, which simultaneously approximately maximizes all symmetric, monotone, concave functions of the utilities. We consider the general setting where the allocation to the agents needs to respect arbitrary submodular constraints, as given by the corresponding polymatroid. We present a signaling policy that achieves a logarithmically approximate majorized policy in this setting, assuming the receiver is a (1+ε) approximate welfare maximizer. The approximation ratio is almost best possible, and that significantly outperforms generic results that only yield linear approximations. A key component of our result is a structural characterization showing that the vector of agent utilities for a given signaling policy defines the base polytope of a different polymatroid, a result that may be of independent interest. In addition, we show that an arbitrarily good additive approximation to this vector can be produced in (weakly) polynomial time via the multiplicative weights update method.
Cite as

Yannan Bai, Kamesh Munagala, Yiheng Shen, and Davidson Zhu. Fair Multi-Agent Persuasion with Submodular Constraints. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bai_et_al:LIPIcs.FORC.2026.14,
  author =	{Bai, Yannan and Munagala, Kamesh and Shen, Yiheng and Zhu, Davidson},
  title =	{{Fair Multi-Agent Persuasion with Submodular Constraints}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-259872},
  doi =		{10.4230/LIPIcs.FORC.2026.14},
  annote =	{Keywords: Bayesian Persuasion, Fair Division, Submodular Optimization}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.15
Incentivizing High-Quality Content in Online Recommender Systems

Authors: Xinyan Hu, Meena Jagadeesan, Michael I. Jordan, and Jacob Steinhardt

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

Abstract
In content recommender systems such as TikTok and YouTube, the platform’s recommendation algorithm shapes content producer incentives. Many platforms employ online learning, which generates intertemporal incentives, since content produced today affects recommendations of future content. We study the game between producers and analyze the content created at equilibrium. We prove that standard online learning algorithms, such as Hedge and EXP3, unfortunately incentivize producers to create low-quality content, where producers' effort approaches zero in the long run for typical learning rate schedules. Motivated by this negative result, we design learning algorithms that incentivize producers to invest high effort and achieve high user welfare. At a conceptual level, our work illustrates the unintended impact that a platform’s learning algorithm can have on content quality and introduces algorithmic approaches to mitigating these effects.
Cite as

Xinyan Hu, Meena Jagadeesan, Michael I. Jordan, and Jacob Steinhardt. Incentivizing High-Quality Content in Online Recommender Systems. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.FORC.2026.15,
  author =	{Hu, Xinyan and Jagadeesan, Meena and Jordan, Michael I. and Steinhardt, Jacob},
  title =	{{Incentivizing High-Quality Content in Online Recommender Systems}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{15:1--15: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.15},
  URN =		{urn:nbn:de:0030-drops-259887},
  doi =		{10.4230/LIPIcs.FORC.2026.15},
  annote =	{Keywords: recommender systems, content quality, producer incentives, online learning, algorithmic game theory, Stackelberg games}
}
  • Refine by Type
  • 26 Document/PDF
  • 1 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 25 2026
  • 1 2025
  • 1 2021

  • Refine by Author
  • 4 Manurangsi, Pasin
  • 3 Lin, Huijia (Rachel)
  • 2 Cohen, Aloni
  • 2 Harrison, Charlie
  • 1 Andersson, Joel Daniel
  • Show More...

  • Refine by Series/Journal
  • 26 LIPIcs

  • Refine by Classification
  • 9 Security and privacy
  • 3 Theory of computation → Computational complexity and cryptography
  • 3 Theory of computation → Design and analysis of algorithms
  • 2 Applied computing
  • 2 Applied computing → Economics
  • Show More...

  • Refine by Keyword
  • 3 Differential privacy
  • 3 differential privacy
  • 2 Approximation algorithms
  • 2 Cryptography
  • 2 continual release
  • 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