Tootfinder

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, Anannya Upasana
https://arxiv.org/abs/2403.07328

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
In MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula $Φ$, and $k \ge 0$, and the goal is to find an assignment $β$ with at most $k$ variables set to true (also called a weight $k$-assignment) such that the number of clauses satisfied by $β$ is maximized. MaxCov can be seen as a special case of CC-MaxSAT, where the formula $Φ$ is monotone, i.e., does not contain any negative literals. CC-MaxSAT and MaxCov are extremely well-studied problems in the approximati…

Fair Risk Control: A Generalized Framework for Calibrating Multi-group Fairness Risks
Lujing Zhang, Aaron Roth, Linjun Zhang
https://arxiv.org/abs/2405.02225

Fair Risk Control: A Generalized Framework for Calibrating Multi-group Fairness Risks
This paper introduces a framework for post-processing machine learning models so that their predictions satisfy multi-group fairness guarantees. Based on the celebrated notion of multicalibration, we introduce $(\mathbf{s},\mathcal{G}, α)-$GMC (Generalized Multi-Dimensional Multicalibration) for multi-dimensional mappings $\mathbf{s}$, constraint set $\mathcal{G}$, and a pre-specified threshold level $α$. We propose associated algorithms to achieve this notion in general settings. This framew…