Uri Stemmer

(אורי שטמר)

I am a faculty member at the School of Computer Science at Tel Aviv University.

Previously, I was a faculty member at Ben-Gurion University, a postdoc at the Weizmann Institute of Science, and a postdoc at Harvard University. I completed my Ph.D. at Ben-Gurion University, where I was lucky to have Amos Beimel and Kobbi Nissim as my advisors.

Research Interests
Privacy-preserving data analysis, computational learning theory, algorithms.

News

• New papers on adaptive "resettable" streaming and machine unlearning posted on arXiv
• One paper in ICLR'26!
• Promoted to associate professor with tenure. Thanks to everyone who helped me get here!
• Two papers in ITCS'26: One on robust distributed counting and one on defining reconstruction (following up on our ITCS'25 reconstruction paper)
• One paper in SODA'26!
• Congrats to Emma on her first paper!! (Accepted to NeurIPS'25)

Professional Activities

• I taught a mini course at the Boston DP Summer School (2022). See the slides here: 1 2 3 4.
• I co-organized a STOC 2021 Workshop on Robust Streaming, Sketching, and Sampling
• Program committees:   TPDP'19, ICDT'20, ALT'20, TCC'20, TPDP'20, ITC'21, NeurIPS'21 (area chair), ICML'22 (area chair), NeurIPS'22 (area chair), ICML'23 (area chair), PODS'24, FORC'24, ICML'24 (area chair), TPDP'24, ALT'25 (area chair), ICML'25 (area chair), TPDP'25, NeurIPS'25 (area chair), ALT'26 (area chair), STOC'26

Teaching

Current students

• Moshe Shechner (co-advised with Edith Cohen)
• Refael Kohen
• Emma Rapoport
• Rotem Yeskin

Former students

• Menachem Sadigurschi, PhD 2023 (co-advised with Aryeh Kontorovich), now at Intent IQ
• Shachar Schnapp, PhD 2024 (co-advised with Sivan Sabato), now at PVML

Lecture notes for courses I have taught

• Data Privacy
• Adaptive Data Analysis
• Cryptography 2
• Design of Algorithms
• Computational Models

Publications

64. Protecting the Undeleted in Machine Unlearning
    Aloni Cohen, Refael Kohen, Kobbi Nissim, and Uri Stemmer
65. Adaptively Robust Resettable Streaming
    Edith Cohen, Elena Gribelyuk, Jelani Nelson, and Uri Stemmer
66. Hot PATE: Private Aggregation of Distributions for Diverse Tasks
    Edith Cohen, Benjamin Cohen-Wang, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer
    ICLR 2026
67. A Simple and Robust Protocol for Distributed Counting
    
    Edith Cohen, Moshe Shechner, and Uri Stemmer
    ITCS 2026
68. Bayesian Perspective on Memorization and Reconstruction
    
    Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer
    ITCS 2026
69. One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
    Edith Cohen, Jelani Nelson, Tamás Sarlós, Mihir Singhal, Uri Stemmer
    SODA 2026
70. Tight Bounds for Answering Adaptively Chosen Concentrated Queries
    Emma Rapoport, Edith Cohen, and Uri Stemmer
    NeurIPS 2025
71. The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for ℓ2 Norm Estimation
    Sara Ahmadian, Edith Cohen, and Uri Stemmer
    NeurIPS 2025
72. Private Set Union with Multiple Contributions
    Travis Dick, Haim Kaplan, Alex Kulesza, Uri Stemmer, Ziteng Sun, and Ananda Theertha Suresh
    NeurIPS 2025 (Spotlight)
73. Nearly Optimal Sample Complexity for Learning with Label Proportions
    Robert Busa-Fekete, Travis Dick, Claudio Gentile, Haim Kaplan, Tomer Koren, and Uri Stemmer
    ICML 2025
74. Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
    Edith Cohen, Mihir Singhal, and Uri Stemmer
    ICML 2025
75. Minimizing Recourse in an Adaptive Balls and Bins Game
    
    Adi Fine, Haim Kaplan, and Uri Stemmer
    ICALP 2025
76. On Differentially Private Linear Algebra
    Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, and Nitzan Tur
    STOC 2025
77. Data Reconstruction: When You See It and When You Don't
    Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia
    ITCS 2025
78. Private Truly-Everlasting Robust-Prediction
    Uri Stemmer
    ICML 2024 (Oral Presentation)
79. Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries
    Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer
    COLT 2024
80. MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate Amicably
    Bar Alon, Moni Naor, Eran Omri, and Uri Stemmer
    CRYPTO 2024
81. Adaptive Data Analysis in a Balanced Adversarial Model
    Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia
    NeurIPS 2023 (Spotlight)
82. Private Everlasting Prediction
    Moni Naor, Kobbi Nissim, Uri Stemmer, and Chao Yan
    NeurIPS 2023 (Oral Presentation)
83. Black-Box Differential Privacy for Interactive ML
    
    Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, and Uri Stemmer
    NeurIPS 2023
84. Relaxed Models for Adversarial Streaming: The Bounded Interruptions Model and the Advice Model
    Menachem Sadigurschi, Moshe Shechner, and Uri Stemmer
    ESA 2023
85. Concurrent Shuffle Differential Privacy Under Continual Observation
    Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer
    ICML 2023
86. Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
    
    Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer
    STOC 2023
87. On Differential Privacy and Adaptive Data Analysis with Bounded Space
    Itai Dinur, Uri Stemmer, David P. Woodruff, and Samson Zhou
    Eurocrypt 2023
88. Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
    Edith Cohen, Jelani Nelson, Tamás Sarlós, and Uri Stemmer
    AAAI 2023
89. Generalized Private Selection and Testing with High Confidence
    Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer
    ITCS 2023
90. A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
    Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer
    ITCS 2023 and Algorithmica
91. On the Robustness of CountSketch to Adaptive Inputs
    
    Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer
    ICML 2022
92. Adaptive Data Analysis with Correlated Observations
    Aryeh Kontorovich, Menachem Sadigurschi, and Uri Stemmer
    ICML 2022
93. FriendlyCore: Practical Differentially Private Aggregation
    Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer
    ICML 2022
94. Differentially Private Approximate Quantiles
    Haim Kaplan, Shachar Schnapp, and Uri Stemmer
    ICML 2022
95. Monotone Learning
    Olivier Bousquet, Amit Daniely, Haim Kaplan, Yishay Mansour, Shay Moran, and Uri Stemmer
    COLT 2022
96. Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
    
    Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer
    STOC 2022
97. On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
    Menachem Sadigurschi and Uri Stemmer
    
    NeurIPS 2021
98. Differentially Private Multi-Armed Bandits in the Shuffle Model
    Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer
    
    NeurIPS 2021
99. Learning and Evaluating a Differentially Private Pre-trained Language Model
    Shlomo Hoory, Amir Feder, Avichai Tendler, Sofia Erell, Alon Peled-Cohen, Itay Laish, Hootan Nakhost, Uri Stemmer, Ayelet Benjamini, Avinatan Hassidim, and Yossi Matias
    
    EMNLP Findings 2021
100. Separating Adaptive Streaming from Oblivious Streaming
     
     Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer
     
     CRYPTO 2021
101. The Sparse Vector Technique, Revisited
     Haim Kaplan, Yishay Mansour, and Uri Stemmer
     
     COLT 2021
102. Differentially-Private Clustering of Easy Instances
     Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia
     
     ICML 2021
103. Differentially Private Weighted Sampling
     Edith Cohen, Ofir Geri, Tamás Sarlós, and Uri Stemmer
     
     AISTATS 2021
104. Adversarially Robust Streaming Algorithms via Differential Privacy
     
     Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer
     NeurIPS 2020 (Oral Presentation) and Journal of the ACM
105. Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
     Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia
     
     NeurIPS 2020
106. On the Round Complexity of the Shuffle Model
     
     Amos Beimel, Iftach Haitner, Kobbi Nissim, and Uri Stemmer
     
     TCC 2020
107. Closure Properties for Private Classification and Online Prediction
     Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer
     COLT 2020
108. Privately Learning Thresholds: Closing the Exponential Gap
     
     Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer
     COLT 2020
109. The power of synergy in differential privacy: Combining a small curator with local randomizers
     
     Amos Beimel, Aleksandra Korolova, Kobbi Nissim, Or Sheffet, and Uri Stemmer
     ITC 2020
110. How to Find a Point in the Convex Hull Privately
     
     Haim Kaplan, Micha Sharir, and Uri Stemmer
     SoCG 2020
111. Private k-Means Clustering with Stability Assumptions
     Moshe Shechner, Or Sheffet, and Uri Stemmer
     AISTATS 2020
112. Locally Private k-Means Clustering
     Uri Stemmer
     SODA 2020 and Journal of Machine Learning Research
113. Differentially Private Learning of Geometric Concepts
     Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer
     
     ICML 2019 and SIAM Journal on Computing
114. Private Center Points and Learning of Halfspaces
     Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer
     
     COLT 2019
115. The Limits of Post-Selection Generalization
     
     Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman
     
     NeurIPS 2018
116. Differentially Private k-Means with Constant Multiplicative Error
     
     Haim Kaplan and Uri Stemmer
     NeurIPS 2018 (Spotlight)
117. Heavy Hitters and the Structure of Local Privacy
     Mark Bun, Jelani Nelson, and Uri Stemmer
     
     PODS 2018 and Transactions on Algorithms
118. Clustering Algorithms for the Centralized and Local Models
     Kobbi Nissim and Uri Stemmer
     
     ALT 2018
119. Concentration Bounds for High Sensitivity Functions Through Differential Privacy
     Kobbi Nissim and Uri Stemmer
     
     Journal of Privacy and Confidentiality
120. Practical Locally Private Heavy Hitters
     Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta
     
     NIPS 2017 and Journal of Machine Learning Research
     →Presented at HALG 2018 (by invitation)
121. Locating a Small Cluster Privately
     Kobbi Nissim, Uri Stemmer, and Salil Vadhan
     
     PODS 2016
122. Algorithmic Stability for Adaptive Data Analysis
     Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman
     
     STOC 2016 and SIAM Journal on Computing (by invitation)
123. Simultaneous Private Learning of Multiple Concepts
     Mark Bun, Kobbi Nissim, and Uri Stemmer
     
     ITCS 2016 and Journal of Machine Learning Research
124. Differentially Private Release and Learning of Threshold Functions
     Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan
     
     FOCS 2015
125. Learning Privately with Labeled and Unlabeled Examples
     Amos Beimel, Kobbi Nissim, and Uri Stemmer
     
     SODA 2015 and Algorithmica
126. Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
     Amos Beimel, Kobbi Nissim, and Uri Stemmer
     
     RANDOM 2013 and Theory of Computing (by invitation)
127. Characterizing the Sample Complexity of Private Learners
     Amos Beimel, Kobbi Nissim, and Uri Stemmer
     
     ITCS 2013 and Journal of Machine Learning Research

Other Manuscripts

• Individuals and Privacy in the Eye of Data Analysis. Ph.D. Thesis
• Privacy Preserving Social Norm Nudges. Yifat Nahmias, Oren Perez, Yotam Shlomo, and Uri Stemmer. Michigan Technology Law Review
• A Note on Sanitizing Streams with Differential Privacy. Haim Kaplan and Uri Stemmer

Links

Amos Beimel, Kobbi Nissim, Moni Naor, Ilan Shallom, Ilan Orlov, Aryeh Kontorovich, Avner Stemmer, Dana Stemmer, Maya Stemmer