research
∙
07/18/2023
Oracle Efficient Online Multicalibration and Omniprediction
A recent line of work has shown a surprising connection between multical...
share
research
∙
07/14/2023
Dissenting Explanations: Leveraging Disagreement to Reduce Model Overreliance
While explainability is a desirable characteristic of increasingly compl...
research
∙
05/22/2023
Bidding Strategies for Proportional Representation in Advertisement Campaigns
Many companies rely on advertising platforms such as Google, Facebook, o...
research
∙
02/24/2023
Generative Models of Huge Objects
This work initiates the systematic study of explicit distributions that ...
research
∙
02/13/2023
Characterizing notions of omniprediction via multicalibration
A recent line of work shows that notions of multigroup fairness imply su...
research
∙
10/16/2022
Loss Minimization through the Lens of Outcome Indistinguishability
We present a new perspective on loss minimization and the recent notion ...
research
∙
09/15/2022
Omnipredictors for Constrained Optimization
The notion of omnipredictors (Gopalan, Kalai, Reingold, Sharan and Wiede...
research
∙
05/02/2022
Leximax Approximations and Representative Cohort Selection
Finding a representative cohort from a broad pool of candidates is a goa...
research
∙
03/09/2022
Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability
We give the first sample complexity characterizations for outcome indist...
research
∙
02/28/2022
KL Divergence Estimation with Multi-group Attribution
Estimating the Kullback-Leibler (KL) divergence between two distribution...
research
∙
09/11/2021
Omnipredictors
Loss minimization is a dominant paradigm in machine learning, where a pr...
research
∙
05/05/2021
On the Communication Complexity of Key-Agreement Protocols
Key-agreement protocols whose security is proven in the random oracle mo...
research
∙
05/04/2021
Inaccessible Entropy II: IE Functions and Universal One-Way Hashing
This paper uses a variant of the notion of inaccessible entropy (Haitner...
research
∙
05/04/2021
Finding Collisions in Interactive Protocols – Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
We study the round and communication complexities of various cryptograph...
research
∙
03/10/2021
Multicalibrated Partitions for Importance Weights
The ratio between the probability that two distributions R and P give to...
research
∙
11/26/2020
Outcome Indistinguishability
Prediction algorithms assign numbers to individuals that are popularly u...
research
∙
10/12/2020
Inaccessible Entropy I: Inaccessible Entropy Generators and Statistically Hiding Commitments from One-Way Functions
We put forth a new computational notion of entropy, measuring the (in)fe...
research
∙
08/18/2020
Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
We study the problem of robustly estimating the mean of a d-dimensional ...
research
∙
04/22/2019
Tracking and Improving Information in the Service of Fairness
As algorithmic prediction systems have become widespread, fears that the...
research
∙
03/15/2019
Deterministic Approximation of Random Walks in Small Space
We give a deterministic, nearly logarithmic-space algorithm that given a...
research
∙
06/11/2018
Pseudorandom Generators for Width-3 Branching Programs
We construct pseudorandom generators of seed length Õ((n)·(1/ϵ)) that ϵ-...
research
∙
03/08/2018
Fairness Through Computationally-Bounded Awareness
We study the problem of fair classification within the versatile framewo...
research
∙
11/22/2017
Calibration for the (Computationally-Identifiable) Masses
As algorithms increasingly inform and influence decisions made about ind...
research
∙
08/15/2017