- Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant.
*Size and Treewidth Bounds for Conjunctive Queries*. Journal of the ACM (to appear).

[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]

- 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)]

- 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]

- 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]

- 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]

- 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]

- 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.
*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]

- 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.

[abstract] [pdf]