Georgia Institute of Technology College of Sciences

Average-case reductions establish rigorous connections between different statistical models, allowing us to show that if one problem is computationally hard, then another must be as well. Reductions from the planted clique problem have revealed statistical-to-computational gaps in many statistical problems with combinatorial structure. However, several important models remain beyond the reach of existing reduction techniques—for example, no reduction-based hardness results are currently known for sparse phase retrieval.

In this talk, we introduce a computationally efficient procedure that approximately transforms a single observation from certain source models with continuous-valued sample and parameter spaces into a single observation from a broad class of target models. I will present several such reductions and highlight their applications in computational lower bounds, including universality results and hardness in sparse generalized linear models. I will also discuss a potential application in transforming one differentially private mechanism into another.

This is joint work with Guy Bresler and Ashwin Pananjady. Part of the talk is based on the paper: https://arxiv.org/abs/2402.07717.