Paul Valiant - RankMe

68 papers A* 24A 5B 1Journal 34Unranked 2

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