Accueil > Recherche

Recherche

Des papiers que j'ai écrits:

Papiers

  • 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.

  • 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. Voir aussi 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 avec 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)



Valid XHTML 1.0 Transitional Valid CSS!