Gregory Valiant

gregory.valiant@gmail.com www.eecs.berkeley.edu/~gvaliant

Research Interests

My main interests are in Algorithms, Learning, Applied Probability and Statistics, and Algorithmic Game Theory. I have also enjoyed working on Database Theory.

Education

University of California at Berkeley, 2007 – Present.

Currently fifth-year graduate student in Computer Science Theory with a minor in Statistics, advised by Christos Papadimitriou.

Harvard University, 2002 – 2006.

Awarded Bachelor of Arts degree Magna Cum Laude, with Highest Honors in Mathematics, June 2006. Master of Science in Computer Science, June 2006.

Professional Experience

IBM Research, Almaden, Summer 2010.

Summer internship, under the supervision of Ken Clarkson and under the mentorship of Vitaly Feldman. Research focused on several problems in learning theory and applied probability.

Microsoft Research, New England, Summer 2009.

Summer internship, under the supervision of Adam Kalai. Research focused on problems in algorithmic game theory, learning theory, and statistics.

Babel Research, 2006-2007.

Created predictive models of stock price movements using learning theoretic approaches applied to proprietary data gathered by colleagues at Harvard. This work developed new models of broad sentiment changes drawn from millions of internet sources.

Stanford University, Summer 2005.

Research under the supervision of Tim Roughgarden. We worked on two projects in Algorithmic Game Theory—both projects addressed aspects of the broad question of understanding the efficiency of interactions among large numbers of selfish individuals.

Teaching Experience

Graduate Student Instructor, UC Berkeley: CS271, graduate course in Randomness and Computation, taught by Alistair Sinclair, Fall 2011.

Graduate Student Instructor, UC Berkeley: CS70, undergraduate course in Discrete Mathematics and Probability, taught by Alistair Sinclair, Spring 2010.

Teaching Fellow, Harvard University: CS121, undergraduate course in Formal Systems and Computation, taught by Salil Vadhan, Fall 2004.

Awards

IBM PhD Fellowship, 2011-2012.

Best Paper award at the Symposium on Principles of Database Systems (PODS), 2009, for the paper Size and Treewidth Bounds for Conjunctive Queries, with Stephanie Lee and Georg Gottlob.

National Science Foundation Graduate Student Fellowship, 2008-2011.

Thomas Temple Hoopes Prize, for Harvard University seniors’ “outstanding scholarly work or research,” for my undergraduate mathematics thesis The Inefficiency of Selfishness in Network Routing.

Activities

Water Polo: Four-year member of Harvard University’s Varsity Water Polo Team (2002-2006). Member of the Caledonia Water Polo Team, a British National League team (Winter, 2006-2007). Currently member of Cal club team.

Surfing.

Publications

Statistics and Learning Theory

G. Valiant, Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise, 2012. Preliminary version available at http://eccc.hpi-web.de/report/2012/006/.

C. Daskalakis, I. Diakonikolas, R. Servedio, G. Valiant, and P. Valiant, Testing k-Modal Distributions: Optimal Algorithms via Reductions. Manuscript, 2011.

G. Valiant and P. Valiant, The Power of Linear Estimators. In the 53rd Symposium on Foundations of Computer Science (FOCS), 2011.

G. Valiant and P. Valiant, Estimating the Unseen: An n/log(n) Sample Estimator for Entropy and Support Size, Shown Optimal via New CLTs. In the 43rd Symposium on Theory of Computing (STOC), 2011.

G. Valiant and P. Valiant, Estimating the Unseen: a Sublinear-Sample Canonical Estimator of Distributions, 2010. Manuscript, available at http://eccc.hpi-web.de/report/2010/180/.

G. Valiant and P. Valiant, A CLT and Tight Lower Bounds for Estimating Entropy, 2010. Manuscript, available at http://eccc.hpi-web.de/report/2010/179/.

A. Moitra, and G. Valiant, Settling the Polynomial Learnability of Mixtures of Gaussians. In the 51st

Symposium on Foundations of Computer Science (FOCS), 2010. Invited to the Research Highlights section of the Communications of the ACM (CACM), will appear as: A. T. Kalai, A. Moitra, and G. Valiant, Disentangling Gaussians.

A. T. Kalai, A. Moitra, and G. Valiant, Efficiently Learning Mixtures of Two Gaussians. In the 42nd

Symposium on Theory of Computing (STOC), 2010.

Database Theory

G. Valiant and P. Valiant, Size Bounds for Conjunctive Queries with General Functional Dependencies. Manuscript, available at http://arxiv.org/abs/0909.2030.

G. Gottlob, S. T. Lee, and G. Valiant, Size and Treewidth Bounds for Conjunctive Queries. In the Symposium on Principles of Database Systems, PODS 2009. Best Paper Award. Invited to a special issue of the Journal of the ACM (JACM), will appear as: G. Gottlob, S. T. Lee, G. Valiant, and P. Valiant, Size and Treewidth Bounds for Conjunctive Queries.

Algorithmic Game Theory

N. Nisan, M. Schapira, G. Valiant, and A. Zohar, Best-Response Auctions. In the 12th ACM Conference on Electronic Commerce (EC), 2011.

N. Nisan, M. Schapira, G. Valiant, and A. Zohar, Best-Response Mechanisms. In the 2nd Innovations in Computer Science (ICS), 2011.

C. Daskalakis, R. Frongillo, C. Papadimitriou, G. Pierrakos, and G. Valiant, Learning Algorithms for Nash Equilibria. In the 3rd International Symposium on Algorithmic Game Theory (SAGT), 2010.

C. Papadimitriou and G. Valiant, A New Look at Selfish Routing, in the 1st Innovations in Computer Science (ICS), 2010.

C. Daskalakis, G. Shoenebeck, G. Valiant, and P. Valiant, On the Complexity of Nash Equilibria of Action-Graph Games. In the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.

H. Chen, T. Roughgarden, and G. Valiant, Designing Network Protocols for Good Equilibria. In the SIAM Journal on Computing. 39(5): 1799-1832, 2010. Originally appeared as, Designing Networks with Good Equilibria. In the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.

G. Valiant and T. Roughgarden, Braess’s Paradox in Large Random Graphs. In Random Structures and Algorithms, 37(4): 495-515, 2010. Originally in the 7th ACM Conference on Electronic Commerce (EC), 2006.

Planetary Sciences

S. T. Stewart and G. J. Valiant, Martian Subsurface Properties and Crater Formation Processes Inferred from Fresh Impact Crater Geometries. Meteoritics and Planetary Science 41, Nr 10, pp 1509-1537, 2006.

G. J. Valiant and S. T. Stewart, Martian Surface Properties: Inferences from Resolved Differences in Crater Geometries. Proc. of the Lunar and Planetary Science Conference 35, Abs. 1293, 2004.

References

Christos Papadimitriou, Professor, UC Berkeley.

Email: christos [AT] cs.berkeley.edu

Phone: 510 642 1559

Adam Kalai, Senior Researcher, Microsoft Research, New England.

Email: adum [AT] microsoft.com

Phone: 857 453 6323

Georg Gottlob, Professor, University of Oxford.

Email: georg.gottlob [AT] comlab.ox.ac.uk

Phone: +44 1865 283504

Alistair Sinclair, Professor, UC Berkeley.

Email: sinclair [AT] cs.berkeley.edu

Phone: 510 643 8144