default search action
Paul Valiant
Person information
- affiliation: Brown University, Providence, RI, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c28]Itay Safran, Daniel Reichman, Paul Valiant:
How Many Neurons Does it Take to Approximate the Maximum? SODA 2024: 3156-3183 - [i23]Itay Safran, Daniel Reichman, Paul Valiant:
Depth Separations in Neural Networks: Separating the Dimension from the Accuracy. CoRR abs/2402.07248 (2024) - 2023
- [c27]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 - [c26]Shivam Gupta, Jasper C. H. Lee, Eric Price, Paul Valiant:
Minimax-Optimal Location Estimation. NeurIPS 2023 - [i22]Itay Safran, Daniel Reichman, Paul Valiant:
How Many Neurons Does it Take to Approximate the Maximum? CoRR abs/2307.09212 (2023) - [i21]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 abs/2311.12784 (2023) - 2022
- [c25]Jasper C. H. Lee, Paul Valiant:
Optimal Sub-Gaussian Mean Estimation in Very High Dimensions. ITCS 2022: 98:1-98:21 - [c24]Shivam Gupta, Jasper C. H. Lee, Eric Price, Paul Valiant:
Finite-Sample Maximum Likelihood Estimation of Location. NeurIPS 2022 - [i20]Shivam Gupta, Jasper C. H. Lee, Eric Price, Paul Valiant:
Finite-Sample Maximum Likelihood Estimation of Location. CoRR abs/2206.02348 (2022) - 2021
- [c23]Jasper C. H. Lee, Paul Valiant:
Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$. FOCS 2021: 672-683 - [c22]Jasper C. H. Lee, Paul Valiant:
Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins. SODA 2021: 414-433 - 2020
- [c21]Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant:
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process. COLT 2020: 483-513 - [c20]Justin Y. Chen, Gregory Valiant, Paul Valiant:
Worst-Case Analysis for Randomly Collected Data. NeurIPS 2020 - [p1]Gregory Valiant, Paul Valiant
:
Instance Optimal Distribution Testing and Learning. Beyond the Worst-Case Analysis of Algorithms 2020: 506-526 - [i19]Jasper C. H. Lee, Paul Valiant:
Optimal Sub-Gaussian Mean Estimation in R. CoRR abs/2011.08384 (2020)
2010 – 2019
- 2019
- [i18]Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant:
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process. CoRR abs/1904.09080 (2019) - [i17]Jasper C. H. Lee, Paul Valiant:
Uncertainty about Uncertainty: Near-Optimal Adaptive Algorithms for Estimating Binary Mixtures of Unknown Coins. CoRR abs/1904.09228 (2019) - [i16]Justin Y. Chen, Gregory Valiant, Paul Valiant:
How bad is worst-case data if you know where it comes from? CoRR abs/1911.03605 (2019) - 2017
- [j8]Gregory Valiant, Paul Valiant:
Estimating the Unseen: Improved Estimators for Entropy and Other Properties. J. ACM 64(6): 37:1-37:41 (2017) - [j7]Gregory Valiant, Paul Valiant:
An Automatic Inequality Prover and Instance Optimal Identity Testing. SIAM J. Comput. 46(1): 429-455 (2017) - 2016
- [c19]Jasper C. H. Lee, Paul Valiant:
Optimizing Star-Convex Functions. FOCS 2016: 603-614 - [c18]Gregory Valiant, Paul Valiant:
Instance optimal learning of discrete distributions. STOC 2016: 142-155 - [i15]Gregory Valiant, Paul Valiant:
Information Theoretically Secure Databases. CoRR abs/1605.02646 (2016) - [i14]Gregory Valiant, Paul Valiant:
Information Theoretically Secure Databases. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i13]Gregory Valiant, Paul Valiant:
Instance Optimal Learning. CoRR abs/1504.05321 (2015) - [i12]Jasper C. H. Lee, Paul Valiant:
Beyond Convex Optimization: Star-Convex Functions. CoRR abs/1511.04466 (2015) - 2014
- [j6]Paul Valiant:
Evolvability of Real Functions. ACM Trans. Comput. Theory 6(3): 12:1-12:19 (2014) - [c17]Gregory Valiant, Paul Valiant:
An Automatic Inequality Prover and Instance Optimal Identity Testing. FOCS 2014: 51-60 - [c16]Siu On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant:
Optimal Algorithms for Testing Closeness of Discrete Distributions. SODA 2014: 1193-1203 - 2013
- [c15]Paul Valiant, Gregory Valiant:
Estimating the Unseen: Improved Estimators for Entropy and other Properties. NIPS 2013: 2157-2165 - [c14]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
Testing k-Modal Distributions: Optimal Algorithms via Reductions. SODA 2013: 1833-1852 - [i11]Siu On Chan, Ilias Diakonikolas, Gregory Valiant, Paul Valiant:
Optimal Algorithms for Testing Closeness of Discrete Distributions. CoRR abs/1308.3946 (2013) - [i10]Gregory Valiant, Paul Valiant:
Instance-by-instance optimal identity testing. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j5]Georg Gottlob
Size and Treewidth Bounds for Conjunctive Queries. J. ACM 59(3): 16:1-16:35 (2012) - [c13]Paul Valiant:
Distribution free evolvability of polynomial functions over all convex loss functions. ITCS 2012: 142-148 - [c12]Andrew McGregor, Paul Valiant:
The shifting sands algorithm. SODA 2012: 453-458 - 2011
- [j4]Paul Valiant:
Testing Symmetric Properties of Distributions. SIAM J. Comput. 40(6): 1927-1968 (2011) - [c11]Gregory Valiant, Paul Valiant:
The Power of Linear Estimators. FOCS 2011: 403-412 - [c10]Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant:
Testing monotonicity of distributions over general partial orders. ICS 2011: 239-252 - [c9]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: 685-694 - [i9]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant:
Testing $k$-Modal Distributions: Optimal Algorithms via Reductions. CoRR abs/1112.5659 (2011) - [i8]Paul Valiant:
Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [c8]Jing Chen, Silvio Micali, Paul Valiant:
Robustly Leveraging Collusion in Combinatorial Auctions. ICS 2010: 81-93 - [i7]Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant:
Testing monotonicity of distributions over general partial orders. Electron. Colloquium Comput. Complex. TR10 (2010) - [i6]Gregory Valiant, Paul Valiant:
A CLT and tight lower bounds for estimating entropy. Electron. Colloquium Comput. Complex. TR10 (2010) - [i5]Gregory Valiant, Paul Valiant:
Estimating the unseen: A sublinear-sample canonical estimator of distributions. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [c7]Constantinos Daskalakis, Grant Schoenebeck
On the complexity of Nash equilibria of action-graph games. SODA 2009: 710-719 - [i4]Gregory Valiant, Paul Valiant:
Size Bounds for Conjunctive Queries with General Functional Dependencies. CoRR abs/0909.2030 (2009) - 2008
- [b1]Paul Valiant:
Testing symmetric properties of distributions. Massachusetts Institute of Technology, Cambridge, MA, USA, 2008 - [c6]Paul Valiant:
Testing symmetric properties of distributions. STOC 2008: 383-392 - [c5]Paul Valiant:
Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency. TCC 2008: 1-18 - [i3]Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, Paul Valiant:
On the Complexity of Nash Equilibria of Action-Graph Games. CoRR abs/0802.1604 (2008) - 2007
- [c4]Xi Chen, Shang-Hua Teng, Paul Valiant:
The approximation complexity of win-lose games. SODA 2007: 159-168 - [i2]Paul Valiant:
Testing Symmetric Properties of Distributions. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c3]Mythili Vutukuru, Paul Valiant
How to Construct a Correct and Scalable iBGP Configuration. INFOCOM 2006 - 2005
- [j3]Mart de Graaf, Paul Valiant:
Polynomial Representations of Symmetric Partial Boolean Functions. SIAM J. Discret. Math. 19(2): 481-488 (2005) - [c2]Paul Valiant:
The Tensor Product of Two Codes Is Not Necessarily Robustly Testable. APPROX-RANDOM 2005: 472-481 - [c1]Timothy G. Abbott, Daniel Kane, Paul Valiant:
On the Complexity of Two-PlayerWin-Lose Games. FOCS 2005: 113-122 - 2004
- [j2]Paul Valiant:
Linear bounds on the North-East model and higher-dimensional analogs. Adv. Appl. Math. 33(1): 40-50 (2004) - [j1]Paul Valiant:
The Log-Rank Conjecture and low degree polynomials. Inf. Process. Lett. 89(2): 99-103 (2004) - 2002
- [i1]Mart de Graaf, Paul Valiant:
Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds. CoRR quant-ph/0211179 (2002)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:15 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: