4 papers · 1 filter
Testing Unate Distributions
Daeho Lee, Shivam Nadimpalli, Mingda Qiao +1
We initiate the study of *unate distributions* over -- a natural analogue of unate Boolean functions -- by considering two basic testing problems that parallel well-st…
Computational and Statistical Hardness of Calibration Distance
Mingda Qiao
The distance from calibration, introduced by Błasiok, Gopalan, Hu, and Nakkiran (STOC 2023), has recently emerged as a central measure of miscalibration for probabilistic predictor…
No Price Tags? No Problem: Query Strategies for Unpriced Information
Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld
The classic *priced query model*, introduced by Charikar et al. (STOC 2000), captures the task of computing a known function on an unknown input when each input variable can only b…
A Combinatorial Approach to Robust PCA
Weihao Kong, Mingda Qiao, Rajat Sen
We study the problem of recovering Gaussian data under adversarial corruptions when the noises are low-rank and the corruptions are on the coordinate level. Concretely, we assume t…