Home > Research


Some research papers I have written:


  • Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
    with H. Avron, M. Kapralov, C. Musco, C. Musco, and A. Zandieh
    ICML 2017.

  • Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
    with V. Guruswami and S. Velusamy
    APPROX 2017.

  • Towards Constructing Ramanujan Graphs Using Shift Lifts
    with K. Chandrasekaran
    Linear Algebra and its Applications, volume 529, 2017. Also arXiv:1502.07410. (arXiv)

  • (1 + Ω(1))-Approximation to MAX-CUT Requires Linear Space
    with M. Kapralov, S. Khanna, and M. Sudan
    SODA 2017.

  • Bridging the Capacity Gap Between Interactive and One-Way Communication
    with B. Haeupler
    SODA 2017. Also ECCC TR16-090 and arXiv:1605.08792. (ECCC | arXiv)

  • On the Sensitivity Conjecture for Read-k Formulas
    with M. Bafna, S. Lokam, and S. Tavenas
    MFCS 2016. Also ECCC TR16-132. (ECCC)

  • Communication with Partial Noiseless Feedback
    with B. Haeupler and P. Kamath
    RANDOM 2015.

  • Approximating Data-Sensitive Distances
    with M. Cohen, B. Fasy, G. Miller, A. Nayyeri, and D. Sheehy
    WADS 2015. Also arXiv:1502.08048. (arXiv)

  • An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets
    with V. Guruswami
    CCC 2015. Also ECCC TR14-165 and arXiv:1411.6993. (ECCC | arXiv)
    • See video presentation from the Simons Institute's workshop on Coding: From Practice to Theory.
    • Note: This work shows that polar codes over prime alphabet are the first-known construction of efficiently encodable and decodable codes to exhibit a polynomial speed of convergence for all symmetric channels.

  • Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
    with V. Guruswami, M. Sudan, and C. Wang
    SODA 2015. Also ECCC TR14-067. (ECCC)

  • A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs
    with G. Miller and D. Sheehy
    SoCG 2013. Also arXiv:1304.0524. (arXiv)

  • Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
    with M. Cheraghchi and V. Guruswami
    SODA 2013. Journal version: SIAM Journal of Computing 42(5), pp. 1888-1914, 2013. Also ECCC TR12-082 and arXiv:1207.1140. (ECCC | arXiv)
    • Note: This work relates list-decoding of random linear codes to analyzing the Restricted Isometry Property (RIP) of subsampled DFT matrices from compressed sensing.
    • We show that the number of row samples needed for NxN matrices and sparsity k is O(k log^2 k log N), which improves on bounds by Candès-Tao and Rudelson-Vershynin!
    • Subsequent work: A further improvement of our compressed sensing bound has been obtained by Haviv and Regev.
    • Subsequent work: Our list-decoding result has been improved by Mary Wootters using a different approach.

  • Meshing log n Dimensions in Polynomial Time
    with G. Miller and D. Sheehy
    Extended abstract in CG:YRF 2012

  • On an Exact Formula for the Coefficients of Han's Generating Function
    Accepted to Annals of Combinatorics. (pdf)

  • On the Erdős-Straus Conjecture: Properties of Solutions to its Underlying Diophantine Equation
    with M. Monks
    Manuscript. (pdf)

Other Articles

  • My Favorite Problem: An Unconventional Inequality, Harvard College Math Review 2008. (pdf)

Valid XHTML 1.0 Transitional Valid CSS!