Paul Valiant

Publication Activity (10 Years)

Years Active: 2002-2024
Publications (10 Years): 24

Top Venues

CoRR

FOCS

NeurIPS

SODA

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Itay Safran, Daniel Reichman, Paul Valiant
How Many Neurons Does it Take to Approximate the Maximum? SODA (2024)
Itay Safran, Daniel Reichman, Paul Valiant
Depth Separations in Neural Networks: Separating the Dimension from the Accuracy. CoRR (2024)
Trung Dang, Jasper C. H. Lee, Maoyuan Song, Paul Valiant
Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1+α Moments. CoRR (2023)
Trung Dang, Jasper C. H. Lee, Maoyuan Raymond Song, Paul Valiant
Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1+α Moments. NeurIPS (2023)
Itay Safran, Daniel Reichman, Paul Valiant
How Many Neurons Does it Take to Approximate the Maximum? CoRR (2023)
Shivam Gupta, Jasper C. H. Lee, Eric Price, Paul Valiant
Minimax-Optimal Location Estimation. NeurIPS (2023)
Jasper C. H. Lee, Paul Valiant
Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$. FOCS (2022)
Jasper C. H. Lee, Paul Valiant
Optimal Sub-Gaussian Mean Estimation in Very High Dimensions. ITCS (2022)
Shivam Gupta, Jasper C. H. Lee, Eric Price, Paul Valiant
Finite-Sample Maximum Likelihood Estimation of Location. CoRR (2022)
Shivam Gupta, Jasper C. H. Lee, Eric Price, Paul Valiant
Finite-Sample Maximum Likelihood Estimation of Location. NeurIPS (2022)
Jasper C. H. Lee, Paul Valiant
Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$. FOCS (2021)
Jasper C. H. Lee, Paul Valiant
Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins. SODA (2021)
Jasper C. H. Lee, Paul Valiant
Optimal Sub-Gaussian Mean Estimation in R. CoRR (2020)
Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process. COLT (2020)
Justin Y. Chen, Gregory Valiant, Paul Valiant
Worst-Case Analysis for Randomly Collected Data. NeurIPS (2020)
Justin Y. Chen, Gregory Valiant, Paul Valiant
How bad is worst-case data if you know where it comes from? CoRR (2019)
Jasper C. H. Lee, Paul Valiant
Uncertainty about Uncertainty: Near-Optimal Adaptive Algorithms for Estimating Binary Mixtures of Unknown Coins. CoRR (2019)
Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process. CoRR (2019)
Gregory Valiant, Paul Valiant
An Automatic Inequality Prover and Instance Optimal Identity Testing. SIAM J. Comput. 46 (1) (2017)
Gregory Valiant, Paul Valiant
Estimating the Unseen: Improved Estimators for Entropy and Other Properties. J. ACM 64 (6) (2017)
Gregory Valiant, Paul Valiant
Information Theoretically Secure Databases. CoRR (2016)
Jasper C. H. Lee, Paul Valiant
Optimizing Star-Convex Functions. FOCS (2016)
Gregory Valiant, Paul Valiant
Instance optimal learning of discrete distributions. STOC (2016)
Gregory Valiant, Paul Valiant
Information Theoretically Secure Databases. Electron. Colloquium Comput. Complex. 23 (2016)
Jasper C. H. Lee, Paul Valiant
Beyond Convex Optimization: Star-Convex Functions. CoRR (2015)
Gregory Valiant, Paul Valiant
Instance Optimal Learning. CoRR (2015)
Gregory Valiant, Paul Valiant
An Automatic Inequality Prover and Instance Optimal Identity Testing. FOCS (2014)
Siu-on Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant
Optimal Algorithms for Testing Closeness of Discrete Distributions. SODA (2014)
Paul Valiant
Evolvability of Real Functions. ACM Trans. Comput. Theory 6 (3) (2014)
Gregory Valiant, Paul Valiant
Instance-by-instance optimal identity testing. Electron. Colloquium Comput. Complex. 20 (2013)
Siu-on Chan, Ilias Diakonikolas, Gregory Valiant, Paul Valiant
Optimal Algorithms for Testing Closeness of Discrete Distributions. CoRR (2013)
Paul Valiant, Gregory Valiant
Estimating the Unseen: Improved Estimators for Entropy and other Properties. NIPS (2013)
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant
-Modal Distributions: Optimal Algorithms via Reductions. SODA (2013)
Andrew McGregor, Paul Valiant
The shifting sands algorithm. SODA (2012)
Paul Valiant
Distribution free evolvability of polynomial functions over all convex loss functions. ITCS (2012)
Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, Paul Valiant
Size and Treewidth Bounds for Conjunctive Queries. J. ACM 59 (3) (2012)
Paul Valiant
Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions. Electron. Colloquium Comput. Complex. 18 (2011)
Gregory Valiant, Paul Valiant
The Power of Linear Estimators. FOCS (2011)
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant
Testing $k$-Modal Distributions: Optimal Algorithms via Reductions CoRR (2011)
Paul Valiant
Testing Symmetric Properties of Distributions. SIAM J. Comput. 40 (6) (2011)
Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant
Testing monotonicity of distributions over general partial orders. ICS (2011)
Gregory Valiant, Paul Valiant
Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs. STOC (2011)
Gregory Valiant, Paul Valiant
Estimating the unseen: A sublinear-sample canonical estimator of distributions. Electron. Colloquium Comput. Complex. 17 (2010)
Gregory Valiant, Paul Valiant
A CLT and tight lower bounds for estimating entropy. Electron. Colloquium Comput. Complex. 17 (2010)
Gregory Valiant, Paul Valiant
A CLT and tight lower bounds for estimating entropy. Electron. Colloquium Comput. Complex. 17 (2010)
Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant
Testing monotonicity of distributions over general partial orders. Electron. Colloquium Comput. Complex. 17 (2010)
Jing Chen, Silvio Micali, Paul Valiant
Robustly Leveraging Collusion in Combinatorial Auctions. ICS (2010)
Gregory Valiant, Paul Valiant
Size Bounds for Conjunctive Queries with General Functional Dependencies CoRR (2009)
Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant
On the complexity of Nash equilibria of action-graph games. SODA (2009)
Paul Valiant
Testing symmetric properties of distributions. STOC (2008)
Paul Valiant
Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency. TCC (2008)
Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant
On the Complexity of Nash Equilibria of Action-Graph Games CoRR (2008)
Paul Valiant
Testing Symmetric Properties of Distributions. Electron. Colloquium Comput. Complex. 14 (135) (2007)
Xi Chen, Shang-Hua Teng, Paul Valiant
The approximation complexity of win-lose games. SODA (2007)
Mythili Vutukuru, Paul Valiant, Swastik Kopparty, Hari Balakrishnan
How to Construct a Correct and Scalable iBGP Configuration. INFOCOM (2006)
Timothy G. Abbott, Daniel M. Kane, Paul Valiant
On the Complexity of Two-PlayerWin-Lose Games. FOCS (2005)
Mart de Graaf, Paul Valiant
Polynomial Representations of Symmetric Partial Boolean Functions. SIAM J. Discret. Math. 19 (2) (2005)
Paul Valiant
The Tensor Product of Two Codes Is Not Necessarily Robustly Testable. APPROX-RANDOM (2005)
Paul Valiant
The Log-Rank Conjecture and low degree polynomials. Inf. Process. Lett. 89 (2) (2004)
Paul Valiant
Linear bounds on the North-East model and higher-dimensional analogs. Adv. Appl. Math. 33 (1) (2004)
Mart de Graaf, Paul Valiant
Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds CoRR (2002)

Paul Valiant.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Paul Valiant