Tal Wagner
Academic Homepage
I am an Assistant Professor (Senior Lecturer) in the School of Computer Science and AI in Tel Aviv University and a scientist in Amazon AWS. Before that I was a postdoc in the Machine Learning Foundations group at Microsoft Research Redmond (2020-2022), and obtained my PhD in Computer Science at CSAIL, MIT in 2020, advised by Piotr Indyk.
My research interests are in algorithm design for massive datasets and machine learning.
Email: firstname (dot) lastname (at) gmail (dot) com
Publications
Random Fourier Features in Near-Linear Time
with Sepideh Mahabadi and Sandeep Silwal
Manuscript 2026
[arXiv]
with Sepideh Mahabadi and Sandeep Silwal
Manuscript 2026
[arXiv]
Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy
with Anders Wikum, Nina Mishra and Amin Saberi
Manuscript 2026
[arXiv]
with Anders Wikum, Nina Mishra and Amin Saberi
Manuscript 2026
[arXiv]
Lexicure: Efficient, Encrypted Lexical Search
with Malvika Raj Joshi, Shai Halevi and Nina Mishra
Manuscript 2026
[ePrint]
with Malvika Raj Joshi, Shai Halevi and Nina Mishra
Manuscript 2026
[ePrint]
Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
with Barak Gorodissky
in NeurIPS 2026
[arXiv] [code]
with Barak Gorodissky
in NeurIPS 2026
[arXiv] [code]
Positional LSH: Binary Block Matrix Approximation
for Attention with Linear Biases
with Daniel Wolfson
in NeurIPS 2026
Preliminary version in Workshop on High-Dimensional Learning Dynamics (HiLD) at ICML 2026
[arXiv] [poster (PNG)] [code]
with Daniel Wolfson
in NeurIPS 2026
Preliminary version in Workshop on High-Dimensional Learning Dynamics (HiLD) at ICML 2026
[arXiv] [poster (PNG)] [code]
![[poster (PNG)]](publications/positional_lsh_workshop_poster.png){kind=link}
Frustratingly Simple Black-Box Adaptation of
Language Models via Logit Bias
with Ofek I. Cohen, Lior Shani, Aviv Rosenberg, Ankur Samanta and Yonathan Efroni
Manuscript 2026
[arXiv]
with Ofek I. Cohen, Lior Shani, Aviv Rosenberg, Ankur Samanta and Yonathan Efroni
Manuscript 2026
[arXiv]
QASP: Query-Adaptive Robust Vector Search Policy
with Hakan Ferhatosmanoglu, Kushal Kumar and Andy Warfield
in ICDE 2027
[arXiv]
with Hakan Ferhatosmanoglu, Kushal Kumar and Andy Warfield
in ICDE 2027
[arXiv]
New Bounds for Kernel Sums via Fast Spherical
Embeddings
in ICML 2026
[arXiv] [slides (PDF)] [video (5min)]
in ICML 2026
[arXiv] [slides (PDF)] [video (5min)]
Graph-based Nearest Neighbors with Dynamic Updates
via Random Walks
with Nina Mishra, Yonatan Naamad and Lichen Zhang
in ICLR 2026
[arXiv] [slides (PDF)] [poster (PDF)]
with Nina Mishra, Yonatan Naamad and Lichen Zhang
in ICLR 2026
[arXiv] [slides (PDF)] [poster (PDF)]
Quantization for Vector Search under Streaming
Updates
with Ishaq Aden-Ali, Hakan Ferhatosmanoglu, Alexander Greaves-Tunnell and Nina Mishra
Manuscript 2025
[arXiv]
with Ishaq Aden-Ali, Hakan Ferhatosmanoglu, Alexander Greaves-Tunnell and Nina Mishra
Manuscript 2025
[arXiv]
Learning from End User Data with Shuffled
Differential Privacy over Kernel Densities
in ICLR 2025, Spotlight presentation
also presented in TPDP 2025
[arXiv] [video (5min)]
in ICLR 2025, Spotlight presentation
also presented in TPDP 2025
[arXiv] [video (5min)]
Improved Algorithms for Kernel Matrix-Vector
Multiplication under Sparsity Assumptions
with Piotr Indyk, Michael Kapralov and Kshiteej Sheth
in ICLR 2025
Earlier version in Workshop on Long Context Foundation Models (LCFM) at ICML 2024, Best Paper Award
[arXiv] [video by Michael (5min)]
with Piotr Indyk, Michael Kapralov and Kshiteej Sheth
in ICLR 2025
Earlier version in Workshop on Long Context Foundation Models (LCFM) at ICML 2024, Best Paper Award
[arXiv] [video by Michael (5min)]
Private Text Generation by Seeding Large Language
Model Prompts
with Supriya Nagesh*, Justin Chen* and Nina Mishra
in Workshop on GenAI for Health: Potential, Trust and Policy Compliance at NeurIPS 2024
[arXiv]
with Supriya Nagesh*, Justin Chen* and Nina Mishra
in Workshop on GenAI for Health: Potential, Trust and Policy Compliance at NeurIPS 2024
[arXiv]
Fast Private Kernel Density Estimation via Locality
Sensitive Quantization
with Yonatan Naamad and Nina Mishra
in ICML 2023, Oral presentation
[arXiv] [poster (PDF)] [video (5min)] [code]
with Yonatan Naamad and Nina Mishra
in ICML 2023, Oral presentation
[arXiv] [poster (PDF)] [video (5min)] [code]
Budget-Constrained Bounds for Mini-Batch Estimation
of Optimal Transport
with David Alvarez-Melis, Nicolo Fusi and Lester Mackey
Manuscript 2023
[arXiv]
with David Alvarez-Melis, Nicolo Fusi and Lester Mackey
Manuscript 2023
[arXiv]
Learned Interpolation for Better Streaming Quantile
Approximation with Worst Case Guarantees
with Nicholas Schiefer, Anders Aamand, Justin Chen, Piotr Indyk, Shyam Narayanan and Sandeep Silwal
in ACDA 2023
[arXiv]
with Nicholas Schiefer, Anders Aamand, Justin Chen, Piotr Indyk, Shyam Narayanan and Sandeep Silwal
in ACDA 2023
[arXiv]
Exponentially Improving the Complexity of
Simulating the Weisfeiler-Lehman Test with Graph
Neural Networks
with Anders Aamand, Justin Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer and Sandeep Silwal
in NeurIPS 2022
[arXiv]
with Anders Aamand, Justin Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer and Sandeep Silwal
in NeurIPS 2022
[arXiv]
Unveiling Transformers with LEGO: A Synthetic
Reasoning Task
with Yi Zhang, Arturs Backurs, Sebastien Bubeck, Ronen Eldan and Suriya Gunasekar
Manuscript 2022
[arXiv]
with Yi Zhang, Arturs Backurs, Sebastien Bubeck, Ronen Eldan and Suriya Gunasekar
Manuscript 2022
[arXiv]
Streaming Algorithms for Support-Aware Histograms
with Justin Chen and Piotr Indyk
in ICML 2022
[arXiv] [proceedings] [video by Justin (5min)]
with Justin Chen and Piotr Indyk
in ICML 2022
[arXiv] [proceedings] [video by Justin (5min)]
Generalization Bounds for Data-Driven Numerical
Linear Algebra
with Peter Bartlett and Piotr Indyk
in COLT 2022
[arXiv] [slides (PDF)] [video (20min)]
with Peter Bartlett and Piotr Indyk
in COLT 2022
[arXiv] [slides (PDF)] [video (20min)]
Triangle and Four Cycle Counting with Predictions
in Graph Streams
with Justin Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, David Woodruff and Michael Zhang
in ICLR 2022
[arXiv]
with Justin Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, David Woodruff and Michael Zhang
in ICLR 2022
[arXiv]
Optimal (Euclidean) Metric Compression
with Piotr Indyk
in SIAM Journal on Computing (SICOMP), 2022
[arXiv] [doi] [video (30min)]
with Piotr Indyk
in SIAM Journal on Computing (SICOMP), 2022
[arXiv] [doi] [video (30min)]
Few-Shot Data-Driven Algorithms for Low Rank
Approximation
with Piotr Indyk and David Woodruff
in NeurIPS 2021
[PDF] [proceedings]
with Piotr Indyk and David Woodruff
in NeurIPS 2021
[PDF] [proceedings]
Faster Kernel Matrix Algebra via Density
Estimation
with Arturs Backurs, Piotr Indyk and Cameron Musco
in ICML 2021
[arXiv] [video (5min)]
with Arturs Backurs, Piotr Indyk and Cameron Musco
in ICML 2021
[arXiv] [video (5min)]
Learning-based Support Estimation in Sublinear
Time
with Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld and Sandeep Silwal
in ICLR 2021, Spotlight presentation
[arXiv]
with Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld and Sandeep Silwal
in ICLR 2021, Spotlight presentation
[arXiv]
Scalable Nearest Neighbor Search for Optimal
Transport
with Arturs Backurs, Yihe Dong, Piotr Indyk and Ilya Razenshteyn
in ICML 2020
Earlier version in OTML Workshop at NeurIPS 2019
[arXiv] [slides (PDF)] [video (12min)] [code]
with Arturs Backurs, Yihe Dong, Piotr Indyk and Ilya Razenshteyn
in ICML 2020
Earlier version in OTML Workshop at NeurIPS 2019
[arXiv] [slides (PDF)] [video (12min)] [code]
Learning Space Partitions for Nearest Neighbor
Search
with Yihe Dong, Piotr Indyk and Ilya Razenshteyn
in ICLR 2020
[arXiv] [slides (PDF)] [video (5min)] [code]
with Yihe Dong, Piotr Indyk and Ilya Razenshteyn
in ICLR 2020
[arXiv] [slides (PDF)] [video (5min)] [code]
Eccentricity Heuristics through Sublinear Analysis
Lenses
in APoCS 2020
Earlier version in SPAA 2019 (brief announcement)
[PDF] [brief announcement (PDF)] [slides (PDF)]
in APoCS 2020
Earlier version in SPAA 2019 (brief announcement)
[PDF] [brief announcement (PDF)] [slides (PDF)]
Multitasking Capacity: Hardness Results and
Improved Constructions
with Noga Alon, Jonathan D. Cohen, Tom Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar and Alexander Yu
in SIAM Journal on Discrete Mathematics (SIDMA), 2020
[arXiv] [doi]
with Noga Alon, Jonathan D. Cohen, Tom Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar and Alexander Yu
in SIAM Journal on Discrete Mathematics (SIDMA), 2020
[arXiv] [doi]
Space and Time Efficient Kernel Density Estimation
in High Dimensions
with Arturs Backurs and Piotr Indyk
in NeurIPS 2019
[PDF] [slides (PDF)] [poster (PDF)] [code]
with Arturs Backurs and Piotr Indyk
in NeurIPS 2019
[PDF] [slides (PDF)] [poster (PDF)] [code]
Scalable Fair Clustering
with Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber and Ali Vakilian
in ICML 2019
[arXiv] [code]
with Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber and Ali Vakilian
in ICML 2019
[arXiv] [code]
Sample-Optimal Low-Rank Approximation of Distance
Matrices
with Piotr Indyk, Ali Vakilian and David Woodruff
in COLT 2019
[arXiv] [slides (PDF)] [poster (PDF)] [video (10min)]
with Piotr Indyk, Ali Vakilian and David Woodruff
in COLT 2019
[arXiv] [slides (PDF)] [poster (PDF)] [video (10min)]
Semi-Supervised Learning on Data Streams via
Temporal Label Propagation
with Sudipto Guha, Shiva Kasiviswanathan and Nina Mishra
in ICML 2018
[PDF] [proceedings] [slides (PDF)] [poster (PDF)] [video (10min)]
with Sudipto Guha, Shiva Kasiviswanathan and Nina Mishra
in ICML 2018
[PDF] [proceedings] [slides (PDF)] [poster (PDF)] [video (10min)]
Approximate Nearest Neighbors in Limited Space
with Piotr Indyk
in COLT 2018
[arXiv] [slides (PDF)] [poster (PDF)] [video (10min)]
with Piotr Indyk
in COLT 2018
[arXiv] [slides (PDF)] [poster (PDF)] [video (10min)]
Practical Data-Dependent Metric Compression with
Provable Guarantees
with Piotr Indyk and Ilya Razenshteyn
in NeurIPS 2017
[arXiv] [code] [poster (PDF)]
with Piotr Indyk and Ilya Razenshteyn
in NeurIPS 2017
[arXiv] [code] [poster (PDF)]
A Graph-Theoretic Approach to Multitasking
with Noga Alon, Jonathan D. Cohen, Biswadip Dey, Tom Griffiths, Sebastian Musslick, Kayhan Ozcimder, Daniel Reichman and Igor Shinkar
in NeurIPS 2017, Oral presentation
[arXiv] [poster (PDF)]
with Noga Alon, Jonathan D. Cohen, Biswadip Dey, Tom Griffiths, Sebastian Musslick, Kayhan Ozcimder, Daniel Reichman and Igor Shinkar
in NeurIPS 2017, Oral presentation
[arXiv] [poster (PDF)]
A Sampling-based Approach to Accelerating Queries
in Log Management Systems
with Eric Schkufza and Udi Wieder
in SPLASH 2016
[doi]
with Eric Schkufza and Udi Wieder
in SPLASH 2016
[doi]
Towards Resistance Sparsifiers
with Michael Dinitz and Robert Krauthgamer
in RANDOM 2015
[arXiv] [doi] [slides (PDF)]
with Michael Dinitz and Robert Krauthgamer
in RANDOM 2015
[arXiv] [doi] [slides (PDF)]
Cheeger-Type Approximation for Sparsest st-Cut
with Robert Krauthgamer
in ACM Transactions on Algorithms (TALG), 2016
[arXiv] [doi]
with Robert Krauthgamer
in ACM Transactions on Algorithms (TALG), 2016
[arXiv] [doi]
Volume Regularization for Binary Classification
Koby Crammer and Tal Wagner
in NeurIPS 2012, Spotlight presentation
[PDF]
Koby Crammer and Tal Wagner
in NeurIPS 2012, Spotlight presentation
[PDF]
| Ph.D. Thesis: | Efficient Metric Representations for Big Data |
| MIT, September 2020 |
Teaching
-
0368-3077: Natural Language Processing (2027B, 2026A)
0368-4236: Approximation Algorithms for Big Data (2027A,
2026B)
0368-4247: Seminar on Algorithms for Big Data (2027B, 2026B)
Teaching Materials
Student Supervision
-
TAU: Daniel Wolfson (MSc, ongoing), Barak Gorodissky (MSc,
2026), Tal Argov (undergraduate research, 2024)
AWS interns: Malvika Raj Joshi (2026, 2025), Lichen Zhang
(with Yonatan Naamad, 2024), Ishaq Aden-Ali (with Alexander
Greaves-Tunnell, 2024), Justin Chen (2023)
Service
-
ICLR 2027 (AC), NeurIPS 2026 (AC), TPDP 2026 (PC), ICML 2026
(AC), ICLR 2026 (AC), ICML 2025 (AC)
Other
-
My
other list of publications
is more fun