Recherche

Des papiers que j'ai écrits:

Papiers

• Linear Space Streaming Lower Bounds for Approximating CSPs
  avec C. Chou, A. Golovnev, M. Sudan, et S. Velusamy
  STOC 2022. Voir aussi arXiv:2106.13078. (arXiv)
  
  
• Private Robust Estimation by Stabilizing Convex Relaxations
  avec P. Kothari et P. Manurangsi
  arXiv:2112.03548. (arXiv)
  
  
• On the Power of Multiple Anonymous Messages
  with B. Ghazi, N. Golowich, R. Kumar, et R. Pagh
  EUROCRYPT 2021. Voir aussi arXiv:1908.11353. (arXiv)
  
  
• Pure Differentially Private Summation from Anonymous Messages
  with B. Ghazi, N. Golowich, R. Kumar, P. Manurangsi, et R. Pagh
  ITC 2020. Voir aussi arXiv:2002.01919. (arXiv)
  
  
• Private Aggregation from Fewer Anonymous Messages
  with B. Ghazi, P. Manurangsi, et R. Pagh
  EUROCRYPT 2020. Voir aussi arXiv:1909.11073. (arXiv)
  
  
• Scaling up Kernel Ridge Regression via Locality Sensitive Hashing
  avec M. Kapralov, N. Nouri, I. Razenshteyn, et A. Zandieh
  AISTATS 2020. Voir aussi arXiv:2003.09756. (arXiv)
  
  
• Oblivious Sketching of High-Degree Polynomial Kernels
  avec T. Ahle, M. Kapralov, J. Knudsen, R. Pagh, D. Woodruff, et 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 par T. Ahle et J. Knudsen (arXiv:1909.01821)
  
  
• A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
  avec H. Avron, M. Kapralov, C. Musco, C. Musco, et A. Zandieh
  STOC 2019. Voir aussi arXiv:1812.08723. (arXiv)
  
  
• Dimension-independent Sparse Fourier Transform
  avec M. Kapralov et A. Zandieh
  SODA 2019. Voir aussi arXiv:1902.10633. (arXiv)
  
  
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
  avec H. Avron, M. Kapralov, C. Musco, C. Musco, et A. Zandieh
  ICML 2017. Voir aussi arXiv:1804.09893. (arXiv)
  
  
• Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
  avec V. Guruswami et S. Velusamy
  APPROX 2017.
  
  
• Towards Constructing Ramanujan Graphs Using Shift Lifts
  avec K. Chandrasekaran
  Linear Algebra and its Applications, volume 529, 2017. Also arXiv:1502.07410. (arXiv)
  
  
• (1 + Ω(1))-Approximation to MAX-CUT Requires Linear Space
  avec M. Kapralov, S. Khanna, et M. Sudan
  SODA 2017.
  
  
• Bridging the Capacity Gap Between Interactive and One-Way Communication
  avec B. Haeupler
  SODA 2017. Voir aussi ECCC TR16-090 et arXiv:1605.08792. (ECCC | arXiv)
  
  
• On the Sensitivity Conjecture for Read-k Formulas
  avec M. Bafna, S. Lokam, et S. Tavenas
  MFCS 2016. Voir aussi ECCC TR16-132. (ECCC)
  
  
• Communication with Partial Noiseless Feedback
  avec B. Haeupler et P. Kamath
  RANDOM 2015.
  
  
• Approximating Data-Sensitive Distances
  avec M. Cohen, B. Fasy, G. Miller, A. Nayyeri, et D. Sheehy
  WADS 2015. Voir aussi arXiv:1502.08048. (arXiv)
  
  
• An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets
  avec V. Guruswami
  CCC 2015. Voir aussi ECCC TR14-165 et arXiv:1411.6993. (ECCC | arXiv)
  
  • Voir aussi la présentation vidéo de la rencontre de l'Institut Simons sur Coding: From Practice to Theory.
  • Note: Ce travaux démontre que les codes polaires sur un alphabet premier sont la première construction connue de codes permettant un codage et un décodage efficaces qui ont une convergence polynomiale pour tous les canaux symétriques.
  
  
• Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
  avec V. Guruswami, M. Sudan, et C. Wang
  SODA 2015. Voir aussi ECCC TR14-067. (ECCC)
  
  
• A Fast Algorithm for Well-Spaced Points and Approximate Delaunay Graphs
  avec G. Miller et D. Sheehy
  SoCG 2013. Voir aussi arXiv:1304.0524. (arXiv)
  
  
• Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
  avec M. Cheraghchi et V. Guruswami
  SODA 2013. Revue: SIAM Journal of Computing 42(5), pp. 1888-1914, 2013. Voir aussi ECCC TR12-082 et arXiv:1207.1140. (ECCC | arXiv)
  
  • Note: Ce travaux relie la décodage en liste de codes aléatoires linéaires à l'analyse de la propiété d'isométrie restreinte (anglais: RIP) des matrices TFD sous-échantillonnées dans le domaine de l'acquisition comprimée.
  • On démontre que le nombre d'échantillons de lignes exigés pour des matrices NxN et parcimonie k est O(k log^2 k log N), qui améliore les bornes de Candès-Tao et Rudelson-Vershynin!
  • Travaux ultérieur: Une nouvelle amélioration de notre borne supérieure de l'acquisition comprimée a été obtenue par Haviv et Regev.
  • Travaux ultérieur: Notre résultat a été amélioré par Mary Wootters, qui utilise une approche différente.
  
  
• Meshing log n Dimensions in Polynomial Time
  avec G. Miller et D. Sheehy
  Résumé étendu dans CG:YRF 2012
  
  
• On an Exact Formula for the Coefficients of Han's Generating Function
  Accepté à Annals of Combinatorics. (pdf)
  
  
• On the Erdős-Straus Conjecture: Properties of Solutions to its Underlying Diophantine Equation
  avec M. Monks
  Manuscrit. (pdf)

Autres Articles

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

---