Tal Wagner

I am a senior applied 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 designing algorithms for massive datasets and large-scale machine learning, especially in the following contexts:

• High-dimensional metric data and nearest neighbor search
• Efficient linear algebra
• Learning on data streams
• Data-driven and learning-augmented algorithm design

Email: firstname (dot) lastname (at) gmail (dot) com

---

Updates

	(Apr'23)	Our work on fast differentially private KDE is accepted to ICML'23 as an oral presentation.
	(Sep'22)	Our work on exponentially improved WL simulation with GNNs is accepted to NeurIPS'22.
	(Aug'22)	I joined Amazon AWS as a Senior Applied Scientist.
	(Jul'22)	I spoke at the workshop on Quantitative Geometry of Transportation Metrics in the AMS-EMS-SMF 2022 meeting.
	(May'22)	Our work on support-aware histograms is accepted to ICML'22.

---

Publications

Fast Private Kernel Density Estimation via Locality Sensitive Quantization
with Yonatan Naamad and Nina Mishra
in ICML 2023, Oral presentation
[PDF] [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]


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]


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]


Unveiling Transformers with LEGO: A Synthetic Reasoning Task
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)]


Generalization Bounds for Data-Driven Numerical Linear Algebra
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]


Optimal (Euclidean) Metric Compression
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]


Faster Kernel Matrix Algebra via Density Estimation
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]


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]


Learning Space Partitions for Nearest Neighbor Search
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)]


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]


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]


Scalable Fair Clustering
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)]


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


Approximate Nearest Neighbors in Limited Space
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)]


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


Near-Optimal (Euclidean) Metric Compression
with Piotr Indyk
in SODA 2017
[arXiv] [doi] [slides]


A Sampling-based Approach to Accelerating Queries in Log Management Systems
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)]


Cheeger-Type Approximation for Sparsest st-Cut
with Robert Krauthgamer
in ACM Transactions on Algorithms (TALG), 2016
[arXiv] [doi]


Generalized Girth Problems in Graphs and Hypergraphs
with Uriel Feige
Manuscript 2013
[PDF]


Volume Regularization for Binary Classification
Koby Crammer and Tal Wagner
in NeurIPS 2012, Spotlight presentation
[PDF]

---

---