Boris Prokhorov

I am a PhD student in the EPFL Theory Group, advised by Michael Kapralov.

My research focuses on efficient, practical algorithms for high-dimensional problems. Recently, I have been studying nearly optimal algorithms for approximating attention in a beyond-worst-case setting.

Boris Prokhorov standing at the edge of the sea

Publications

(α–β) indicates alphabetical author order.

  1. Attention under Bounded Key–Query Similarity: Space Complexity and Transformer Anisotropy

    (α–β)J. Y. Chen, Y. Feng, P. Indyk, M. Kapralov, E. Kochetkova, and B. Prokhorov

    Preprint

  2. Towards Tight Bounds for Streaming Attention

    (α–β)J. Y. Chen, Y. Feng, P. Indyk, M. Kapralov, E. Kochetkova, and B. Prokhorov

    SODA 2027 · To appear arXiv ↗

  3. Provable Quantization with Randomized Hadamard Transform

    (α–β)Y. Feng, P. Indyk, M. Kapralov, D. Krachun, and B. Prokhorov

    NeurIPS 2026 · To appear arXiv ↗

  4. Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity

    B. Prokhorov, S. Chebykin, A. Gasnikov, and A. Beznosikov

    ICML 2026 arXiv ↗

  5. Optimization with Markovian Noise: Towards Optimal Rates in Strong Growth Case

    S. Chebykin, B. Prokhorov, and A. Beznosikov

    Doklady Mathematics · 2025 Journal ↗

Teaching

Teaching assistant for the following courses: