Assistant Professor of Mathematics
1035 Evans Hall, UC Berkeley.
email: firstname at math.berkeley.edu.
Research Interests: theoretical computer science, algebraic graph theory, random matrices, asymptotic convex geometry, geometry of polynomials.
Fall 2016 Office Hours: M 5:15-6:30pm (1035 Evans Hall) and Tu 2:00-3:45pm (Student Learning Center).
Math 54, Linear Algebra and Differential Equations.
- Tight Bounds on Plurality (with A. Taylor), IPL 96 (2005). [PDF]
- Voting with Rubber Bands, Weights, and Strings (with D. Cervone, R. Dai, D. Gnoutcheff,
G. Lanterman, A. Mackenzie, A. Morse, and W. Zwicker), to appear in Mathematical Social Sciences. [LINK]
- On the Longest Path Algorithm for Reconstructing Trees from Distance Matrices (with L. Reyzin), IPL 101 (2007). [PDF]
- Learning and Verifying Graphs Using Queries, with a Focus on Edge Counting (with L. Reyzin), ALT 2007. [PDF] [slides]
- Graph Sparsification by Effective Resistances (with D. Spielman), STOC 2008, SICOMP special issue (2011). [arXiv] [slides]
- Twice-Ramanujan Sparsifiers (with J. Batson and D. Spielman), STOC 2009, SICOMP special issue (2012). [arXiv] [slides] [video] and [bourbaki notes] by Assaf Naor.
- An Elementary Proof of the Restricted Invertibility Theorem (with D. Spielman), Israel J. Math 190 (2012). [arXiv] [video]
- On Contact Points of Convex Bodies, Geometric Aspects of Functional Analysis, Springer Lec. Notes in Math. (2012) [PDF]
- Covariance Estimation for Distributions with 2+epsilon Moments (with R. Vershynin), to appear in Annals of Probability. [arXiv] [slides]
- Graph Densification (with M. Hardt and M. Tulsiani), ITCS 2012. [PDF]
- Zero-One Rounding of Singular Vectors (with A. Deshpande and R. Kannan), ICALP 2012. [PDF]
- A New Approach to Computing Maximum Flows using Electrical Flows (with Y. Lee and S. Rao), STOC 2013. [PDF] [slides]
- Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees (with A. Marcus and D. Spielman), Annals of Mathematics & FOCS 2013 [arXiv] [slides]
- Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem (with A. Marcus and D. Spielman), Annals of Mathematics [arXiv] and [blog post]
- Spectral Sparsification of Graphs: Theory and Algorithms (with J. Batson, D. Spielman, and S-H. Teng), Communications of the ACM 2013. [PDF] and [technical perspective] by Assaf Naor.
- Ramanujan Graphs and the Solution of the Kadison-Singer Problem. (with A. Marcus and D. Spielman), Proc. ICM 2014. [arxiv]
- Finite Free Convolutions of Polynomials (with A. Marcus and D. Spielman), preprint. [arxiv]
- Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes (with A. Marcus and D. Spielman), FOCS 2015. [arxiv]
- Real Stability Testing (with P. Raghavendra and N. Ryder), submitted. [arxiv]
Thesis: Spectral Sparsification and Restricted Invertibility [PDF] [slides]
Advisor: Dan Spielman.
Simons Institute Tutorial on Graph Sparsification: one, two, three.
General Audience Talk on Graph Sparsification: [vimeo] (Kavli Frontiers of Science, Agra 2013)
Spring 2016: Math 55, Discrete Mathematics
Fall 2015: Math 185, Complex Analysis
Fall 2015: Math 270, Hot Topics: The Geometry of Polynomials in Algorithms, Combinatorics, and Probability
Spring 2015: Math 121A, Mathematical Tools for the Physical Sciences
Spring 2012: COS 521 Advanced Algorithms (Princeton)
Organizational Activities: MSRI Hot Topics 3/15, BIRS Algebraic Graph Theory 7/16
Program Committees: ITCS 2017, ICALP 2016, STOC 2015, FSTTCS 2012.
Funding: I am grateful to the NSF and to the Sloan Foundation for generously supporting my research.
Previously, I was at Microsoft Research India, Princeton, MSRI, IAS, Yale, and Union College.