Research

Some research papers I have written:

Papers

• On the Power of Multiple Anonymous Messages
  with B. Ghazi, N. Golowich, R. Kumar, and R. Pagh
  EUROCRYPT 2021. Also arXiv:1908.11353. (arXiv)
  
  
• Pure Differentially Private Summation from Anonymous Messages
  with B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, and R. Pagh
  ITC 2020. Also arXiv:2002.01919. (arXiv)
  
  
• Private Aggregation from Fewer Anonymous Messages
  with B. Ghazi, P. Manurangsi, and R. Pagh
  EUROCRYPT 2020. Also arXiv:1909.11073. (arXiv)
  
  
• Scaling up Kernel Ridge Regression via Locality Sensitive Hashing
  with M. Kapralov, N. Nouri, I. Razenshteyn, and A. Zandieh
  AISTATS 2020. Also 2003.09756. (arXiv)
  
  
• Oblivious Sketching of High-Degree Polynomial Kernels
  with T. Ahle, M. Kapralov, J. Knudsen, R. Pagh, D. Woodruff, and A. Zandieh
  SODA 2020.
  • This paper was merged from the following two papers:
    • Oblivious Sketching of High-Degree Polynomial Kernels by M. Kapralov, R. Pagh, A. Velingker, D. Woodruff, A. Zandieh (arXiv:1909.01410)
    • Almost Optimal Tensor Sketch by T. Ahle and J. Knudsen (arXiv:1909.01821)
  
  
• A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
  with H. Avron, M. Kapralov, C. Musco, C. Musco, and A. Zandieh
  STOC 2019. Also arXiv:1812.08723. (arXiv)
  
  
• Dimension-independent Sparse Fourier Transform
  with M. Kapralov and A. Zandieh
  SODA 2019. Also arXiv:1902.10633. (arXiv)
  
  
• 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. Also arXiv:1804.09893. (arXiv)
  
  
• 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)

---