Research
Some research papers I have written:
Papers
 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
 On the Power of Multiple Anonymous Messages
with B. Ghazi, N. Golowich, R. Kumar, and R. Pagh
arXiv:1908.11353 (arXiv)
 Oblivious Sketching of HighDegree 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 HighDegree 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)
 Dimensionindependent 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 MAXCUT Requires Linear Space
with M. Kapralov, S. Khanna, and M. Sudan
SODA 2017.
 Bridging the Capacity Gap Between Interactive and OneWay Communication
with B. Haeupler
SODA 2017. Also ECCC TR16090 and arXiv:1605.08792. (ECCC  arXiv)
 On the Sensitivity Conjecture for Readk Formulas
with M. Bafna, S. Lokam, and S. Tavenas
MFCS 2016. Also ECCC TR16132. (ECCC)
 Communication with Partial Noiseless Feedback
with B. Haeupler and P. Kamath
RANDOM 2015.
 Approximating DataSensitive 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 TR14165 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 firstknown construction of efficiently encodable and decodable codes to exhibit a polynomial speed of convergence for all symmetric channels.
 Limitations on Testable AffineInvariant Codes in the HighRate Regime
with V. Guruswami, M. Sudan, and C. Wang
SODA 2015. Also ECCC TR14067. (ECCC)
 A Fast Algorithm for WellSpaced 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. 18881914, 2013. Also ECCC TR12082 and arXiv:1207.1140. (ECCC  arXiv)
 Note: This work relates listdecoding 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èsTao and RudelsonVershynin!
 Subsequent work: A further improvement of our compressed sensing bound has been obtained by Haviv and Regev.
 Subsequent work: Our listdecoding 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ősStraus 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)
