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)
|