Buchumschlag

Complexity-Theoretic Implications of Multicalibration

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Casacuberta, Sílvia, Dwork, Cynthia, Vadhan, Salil
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Computational Complexity Computers and Society
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Characterizing the Distinguishability of Product Distributions through Multicalibration
von: Marcussen, Cassandra, et al.
Veröffentlicht: (2024)

Generalized and Unified Equivalences between Hardness and Pseudoentropy
von: Hu, Lunjia, et al.
Veröffentlicht: (2025)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
von: Putterman, Aaron, et al.
Veröffentlicht: (2026)

Unifying computational entropies via Kullback-Leibler divergence
von: Agrawal, Rohit, et al.
Veröffentlicht: (2019)

Efficient and Private Property Testing via Indistinguishability
von: Dwork, Cynthia, et al.
Veröffentlicht: (2025)

Supersimulators
von: Dwork, Cynthia, et al.
Veröffentlicht: (2025)

From Pseudorandomness to Multi-Group Fairness and Back
von: Dwork, Cynthia, et al.
Veröffentlicht: (2023)

Practitioners' Perspectives on a Differential Privacy Deployment Registry
von: Nanayakkara, Priyanka, et al.
Veröffentlicht: (2025)

How Global Calibration Strengthens Multiaccuracy
von: Casacuberta, Sílvia, et al.
Veröffentlicht: (2025)

Differentially Private Verification of Distribution Properties
von: Du, Elbert, et al.
Veröffentlicht: (2026)

When and Why is Persuasion Hard? A Computational Complexity Result
von: Wojtowicz, Zachary
Veröffentlicht: (2024)

The Alignment Trap: Complexity Barriers
von: Yao, Jasper
Veröffentlicht: (2025)

Verification Cost Asymmetry in Cognitive Warfare: A Complexity-Theoretic Framework
von: Luberisse, Joshua
Veröffentlicht: (2025)

Scheme-Theoretic Approach to Computational Complexity. III. SETH
von: Çivril, Ali
Veröffentlicht: (2023)

Distribution-Specific Auditing For Subgroup Fairness
von: Hsu, Daniel, et al.
Veröffentlicht: (2024)

Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation
von: Çivril, Ali
Veröffentlicht: (2023)

On Efficient Computation of DiRe Committees
von: Relia, Kunal
Veröffentlicht: (2024)

Good Allocations from Bad Estimates
von: Casacuberta, Sílvia, et al.
Veröffentlicht: (2026)

Barriers to Complexity-Theoretic Proofs that "AGI" Using Machine Learning is Impossible
von: Guerzhoy, Michael
Veröffentlicht: (2024)

Marginal Fairness: Fair Decision-Making under Risk Measures
von: Huang, Fei, et al.
Veröffentlicht: (2025)

Synthetic Census Data Generation via Multidimensional Multiset Sum
von: Dwork, Cynthia, et al.
Veröffentlicht: (2024)

Structure in Communication Complexity and Constant-Cost Complexity Classes
von: Hatami, Hamed, et al.
Veröffentlicht: (2024)

From Proof Complexity to Circuit Complexity via Interactive Protocols
von: Arteche, Noel, et al.
Veröffentlicht: (2024)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
von: Zheng, Bojin, et al.
Veröffentlicht: (2026)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
von: Przybyłek, Michał R., et al.
Veröffentlicht: (2026)

The Complexity of Tensor Rank
von: Schaefer, Marcus, et al.
Veröffentlicht: (2016)

Pseudodeterministic Communication Complexity
von: Göös, Mika, et al.
Veröffentlicht: (2025)

Query Complexity with Unknowns
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
von: Nalli, Sai Soumya, et al.
Veröffentlicht: (2026)

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

Inducing Efficient and Equitable Professional Networks through Link Recommendations
von: Dwork, Cynthia, et al.
Veröffentlicht: (2025)

Equilibria, Efficiency, and Inequality in Network Formation for Hiring and Opportunity
von: Dwork, Cynthia, et al.
Veröffentlicht: (2024)

The Radical Solution and Computational Complexity
von: Zheng, Bojin, et al.
Veröffentlicht: (2024)

The Computational Complexity of Factored Graphs
von: Gupta, Shreya, et al.
Veröffentlicht: (2024)

Separations in Proof Complexity and TFNP
von: Göös, Mika, et al.
Veröffentlicht: (2022)

Random Permutations in Computational Complexity
von: Hitchcock, John M., et al.
Veröffentlicht: (2025)

On the Complexity of Hazard-Free Formulas
von: Arazi, Leah London, et al.
Veröffentlicht: (2024)

Communication Complexity is NP-hard
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

The Complexity of Order-Finding for ROABPs
von: Bhargava, Vishwas, et al.
Veröffentlicht: (2024)

Computational Complexity of UAP Reverse Engineering: A Formal Analysis of Automaton Identification and Data Complexity
von: Daghbouche, Karim
Veröffentlicht: (2025)