- Gregory Valiant and Paul Valiant.
*An Automatic Inequality Prover and Instance Optimal Identity Testing*. SIAM Journal on Computing, 46(1) pp.429-455, 2017.

[abstract] [pdf]

- Gregory Valiant and Paul Valiant.
*Information Theoretically Secure Databases*. Electronic Colloquium on Computational Complexity TR16-078, 2016.

[abstract] [pdf]

- Jasper C.H. Lee and Paul Valiant.
*Optimizing Star-Convex Functions*. Proc. 57nd Foundations of Computer Science (FOCS), 2016.

[abstract] [pdf]

- Stephen Childress, Andrew Gilbert, and Paul Valiant.
*Eroding dipoles and vorticity growth for Euler flows in R*. Journal of Fluid Mechanics, 805, pp. 1-30, 2016.^{3}: Axisymmetric flow without swirl

[abstract] [pdf]

- James Zou, Gregory Valiant, Paul Valiant, Konrad Karczewski, Siu On Chan, Kaitlin Samocha, Monkol Lek, Shamil Sunyaev, Mark Daly and Daniel G. MacArthur.
*Quantifying unobserved protein-coding variants in human populations provides a roadmap for large-scale sequencing projects*. Nature Communications 7, Article 13293, 2016.

[abstract] [pdf]

- Gregory Valiant and Paul Valiant.
*Instance Optimal Learning of Discrete Distributions*. Proc. 47rd Symposium on Theory of Computing (STOC), 2015.

[abstract] [pdf]

- Paul Valiant.
*Evolvability of Real Functions*. Transactions on Theory of Computation 6(3): 12:1-12:19, 2014.

[abstract] [pdf]

- Gregory Valiant and Paul Valiant.
*An Automatic Inequality Prover and Instance Optimal Identity Testing*. Proc. 55nd Foundations of Computer Science (FOCS), 2014. ACM "Best of Computing" Notable Article for 2014

[abstract] [pdf]

- Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant.
*Optimal Algorithms for Testing Closeness of Discrete Distributions*. Proc. 25th Symposium on Discrete Algorithms (SODA), 2014.

[abstract] [pdf]

- Gregory Valiant and Paul Valiant.
*Estimating the Unseen: Improved Estimators for Entropy and other Properties*. Proc. Neural Information Processing Systems (NIPS) 2013.

[abstract] [pdf]

- Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, and Paul Valiant.
*Testing k-Modal Distributions: Optimal Algorithms via Reductions*. Proc. 24th Symposium on Discrete Algorithms (SODA), 2013.

[abstract] [pdf]

- Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant.
*Size and Treewidth Bounds for Conjunctive Queries*. Journal of the ACM, 59(3): 16:1-16:35, 2012.

[abstract] [pdf]

- Andrew McGregor and Paul Valiant.
*The Shifting Sands Algorithm*. Proc. 23rd Symposium on Discrete Algorithms (SODA), 2012.

[abstract] [pdf]

- Paul Valiant.
*Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions*. Proc. 3rd Innovations in Theoretical Computer Science (ITCS), 2012.

[abstract] [pdf]

- Gregory Valiant and Paul Valiant.
*The power of linear estimators*. Proc. 52nd Foundations of Computer Science (FOCS), 2011.

[abstract] [pdf]

- Gregory Valiant, and Paul Valiant.
*Estimating the unseen: a sublinear-sample canonical estimator of distributions*. Merged with below paper in: Proc. 43rd Symposium on Theory of Computing (STOC), 2011.

[abstract] [pdf(full)] [pdf(STOC)] [Video of 20 minute STOC talk! (110MB download)]

- Gregory Valiant and Paul Valiant.
*A CLT and tight lower bounds for estimating entropy*.

2010.

[abstract] [pdf]

- Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, and Paul Valiant.
*Testing Monotonicity of Distributions over General Partial Orders*. Proc. 2nd Innovations in Computer Science (ICS), 2011.

[abstract] [pdf]

- Jing Chen, Silvio Micali, and Paul Valiant.
*Robustly Leveraging Collusion in Combinatorial Auctions*. Proc. 1st Innovations in Computer Science (ICS), 2010, pp. 81-93.

[abstract] [pdf]

- Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, and Paul Valiant.
*On the Complexity of Nash Equilibria of Action-Graph Games*. Proc. 20th Symposium on Discrete Algorithms (SODA), 2009, pp. 710-719.

[abstract] [pdf]

- Paul Valiant.
*Testing Symmetric Properties of Distributions*, MIT PhD Thesis (2008); previous version published in Proc. 40th Symposium on Theory of Computing (STOC), 2008, pp. 383-392.

[abstract] [pdf(Thesis)] [pdf(STOC)]

- Silvio Micali and Paul Valiant.
*Leveraging Collusion in Combinatorial Auctions*. Manuscript, April 2008. ("MV2")

[abstract] [pdf]

- Silvio Micali and Paul Valiant.
*Resilient Mechanisms for Truly Combinatorial Auctions*. Manuscript, November 2008. ("MV1")

[abstract] [pdf]

- Paul Valiant.
*Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency*. Proc. 5th Theory of Cryptography Conference (TCC), 2008, pp. 1-18. (Winner of best student paper award)

[abstract] [pdf]

- Xi Chen, Shang-Hua Teng, and Paul Valiant,
*The approximation complexity of win-lose games*. Proc. 18th Symposium on Discrete Algorithms (SODA), 2007, pp. 159-168.

[abstract] [pdf]

- Mythili Vutukuru, Paul Valiant, Swastik Kopparty, and Hari Balakrishnan.
*How to Construct a Correct and Scalable iBGP Configuration*, Proc. 25th Conference on Computer Communications (INFOCOM), 2006.

[abstract] [pdf]

- Timothy Abbot, Daniel Kane, Paul Valiant.
*On the Complexity of Two-Player Win-Lose Games*. Proc. 46th Foundations of Computer Science (FOCS), 2005, pp. 113-122. (Co-winner of the best student paper award)

[abstract] [pdf]

- Paul Valiant.
*The Tensor Product of Two Codes Is Not Necessarily Robustly Testable*. Proc. 9th International Workshop on Randomization and Computation (RANDOM), 2005, pp. 472-481.

[abstract] [pdf]

- Mart de Graaf and Paul Valiant.
*Polynomial Representations of Symmetric Partial Boolean Functions*. SIAM J. Discrete Math 19(2):481-488 (2005).

[abstract] [pdf]