Ying Feng

me.jpeg

Hi!

I am a third-year PhD student at MIT, where I am fortunate to be advised by Piotr Indyk. Before that, I was an undergrad at CMU.

My research is on the algorithm design for high-dimensional data. Recently, I’m interested in questions arising from efficient computation in machine learning systems.

Email: yingggfeng(at)gmail.com


Manuscripts


  1. Attention under Bounded Key-Query Similarity: Space Complexity and Transformer Anisotropy
    with Justin Y. Chen, Piotr Indyk, Michael Kapralov, Ekaterina Kochetkova, and Boris Prokhorov
  2. Towards Tight Bounds for Streaming Attention
    with Justin Y. Chen, Piotr Indyk, Michael Kapralov, Ekaterina Kochetkova, and Boris Prokhorov
    arXiv
  3. Ultra-Fast Deterministic Approximate Near Neighbor Search in High Dimensions
    with Piotr Indyk
  4. Condition-Number-Independent Sparse Linear Regression on Random Supports

Publications

2026

  1. Provable Quantization with Randomized Hadamard Transform
    with Piotr Indyk, Michael Kapralov, Dmitry Krachun, and Boris Prokhorov
    To appear in NeurIPS 2026
    arXiv
  2. Fast Approximate Lp Chamfer Distance via Lopsided Embeddings and Structured JL
    with David P. Woodruff
    To appear in NeurIPS 2026
  3. Fast and Compact Random Mappings with Uniform Guarantees and Applications
    with Piotr Indyk
    In STOC 2026
    Link

2025

  1. On Differential Privacy for Adaptively Solving Search Problems via Sketching
    with Shiyuan Feng, George Z. Li, Zhao Song, David P. Woodruff, and Lichen Zhang
    In ICML 2025 (Selected for Oral Presentation)
    arXiv
  2. Even Faster Algorithm for the Chamfer Distance
    with Piotr Indyk
    In ICALP 2025
    arXiv

2024

  1. Fast White-Box Adversarial Streaming Without a Random Oracle
    with Aayush Jain, and David P. Woodruff
    In ICML 2024
    arXiv
  2. A Real-Time Rescheduling Algorithm for Multi-Robot Plan Execution
    with Adittyo Paul, Zhe Chen, and Jiaoyang Li
    In ICAPS 2024
    arXiv

2023

  1. Improved Algorithms for White-Box Adversarial Streams
    with David P. Woodruff
    In ICML 2023
    arXiv
  2. A Fast Rescheduling Algorithm for Real-Time Multi-Robot Coordination (Extended Abstract)
    with Adittyo Paul, and Jiaoyang Li
    In SoCS 2023
    Link