| 2026 | COLT | The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network. | Abhigyan Dutta, Itay Safran, Paul Valiant |
| 2025 | COLT | Depth Separations in Neural Networks: Separating the Dimension from the Accuracy. | Itay Safran, Daniel Reichman, Paul Valiant |
| 2025 | ICML | All-Purpose Mean Estimation over R: Optimal Sub-Gaussianity with Outlier Robustness and Low Moments Performance. | Jasper C. H. Lee, Walter McKelvie, Maoyuan Song, Paul Valiant |
| 2025 | STOC | A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities. | Joey Rivkin, Gregory Valiant, Paul Valiant |
| 2024 | SODA | How Many Neurons Does it Take to Approximate the Maximum? | Itay Safran, Daniel Reichman, Paul Valiant |
| 2021 | FOCS | Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$. | Jasper C. H. Lee, Paul Valiant |
| 2021 | SODA | Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins. | Jasper C. H. Lee, Paul Valiant |
| 2020 | COLT | Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process. | Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant |
| 2016 | FOCS | Optimizing Star-Convex Functions. | Jasper C. H. Lee, Paul Valiant |
| 2016 | STOC | Instance optimal learning of discrete distributions. | Gregory Valiant, Paul Valiant |
| 2014 | FOCS | An Automatic Inequality Prover and Instance Optimal Identity Testing. | Gregory Valiant, Paul Valiant |
| 2014 | SODA | Optimal Algorithms for Testing Closeness of Discrete Distributions. | Siu On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant |
| 2013 | SODA | Testing | Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant |
| 2012 | SODA | The shifting sands algorithm. | Andrew McGregor, Paul Valiant |
| 2011 | FOCS | The Power of Linear Estimators. | Gregory Valiant, Paul Valiant |
| 2011 | STOC | Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs. | Gregory Valiant, Paul Valiant |
| 2009 | SODA | On the complexity of Nash equilibria of action-graph games. | Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant |
| 2008 | STOC | Testing symmetric properties of distributions. | Paul Valiant |
| 2008 | TCC | Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency. | Paul Valiant |
| 2007 | SODA | The approximation complexity of win-lose games. | Xi Chen, Shang-Hua Teng, Paul Valiant |
| 2006 | INFOCOM | How to Construct a Correct and Scalable iBGP Configuration. | Mythili Vutukuru, Paul Valiant, Swastik Kopparty, Hari Balakrishnan |
| 2005 | FOCS | On the Complexity of Two-PlayerWin-Lose Games. | Timothy G. Abbott, Daniel Kane, Paul Valiant |