Omri BenEliezer 
office: MIT 2232B  email: omrib@mit.edu
I am an Instructor (postdoc) in Applied Mathematics at MIT Mathematics.
I've completed my PhD in Computer Science at Tel Aviv University, where I was fortunate to be advised by Noga Alon.
After that, I spent a couple of months at Weizmann Institute, hosted by Moni Naor,
and a year at Harvard University, mentored by Madhu Sudan.
I am also affiliated with FODSI.
Research Interests
Theoretical and algorithmic foundations of big data: sublinear time and streaming algorithms, beyond worst case analysis of algorithms, robustness and privacy, knowledge representation, complex networks.
Program Committees: ITCS'22.
Check out our STOC'21 workshop Robust Streaming, Sketching, and Sampling.
New: see my recent talk on robust sampling and online learning at the Virtual talk series on foundations of data science.


Publications
(Order of authors is alphabetical by default, unless first author is marked with *)
2022+
Is this correct? Let's check!
Omri BenEliezer,
Dan Mikulincer,
Elchanan Mossel,
Madhu Sudan
ITCS 2023
Archimedes meets privacy: On privately estimating quantiles in high dimensions under minimal assumptions
Omri BenEliezer,
Dan Mikulincer,
Ilias Zadik
NeurIPS 2022
Active learning polynomial threshold functions
Omri BenEliezer,
Max Hopkins,
Chutong Yang,
Hantao Yu
NeurIPS 2022
Sampling multiple nodes in large networks: Beyond random walks
Omri BenEliezer*,
Talya Eden,
Joel Oren,
Dimitris Fotakis
WSDM 2022, selected for
oral presentation
Finding monotone patterns in sublinear time, adaptively
Omri BenEliezer,
Shoham Letzter,
Erik Waingarten
ICALP 2022
Adversarially robust streaming via densesparse tradeoffs
Omri BenEliezer,
Talya Eden,
Krzysztof Onak
SOSA 2022
2021
Adversarial laws of large numbers and optimal regret in online classification
Noga Alon,
Omri BenEliezer,
Yuval Dagan,
Shay Moran,
Moni Naor,
Eylon Yogev
STOC 2021
Invited to SICOMP special issue for STOC'21
Learning multimodal affinities for textual editing in images
Or Perel*,
Oron Anschel,
Omri BenEliezer,
Shai Mazor,
Hadar AverbuchElor
Transactions on Graphics (
2021)
Presented at
SIGGRAPH 2021
What is learned in knowledge graph embeddings?
Michael R. Douglas*,
Michael Simkin,
Omri BenEliezer,
Tianqi Wu,
Peter Chin,
Trung V. Dang,
Andrew Wood
Complex Networks 2021
Bounded space differentially private quantiles
Daniel Alabi,
Omri BenEliezer,
Anamay Chaturvedi
TPDP 2021
Limits of ordered graphs and their applications
Omri BenEliezer,
Eldar Fischer,
Amit Levi,
Yuichi Yoshida
ITCS 2021
2020
A framework for adversarially robust streaming algorithms
Omri BenEliezer,
Rajesh Jayaram,
David P. Woodruff,
Eylon Yogev
Journal of the ACM (
2022, by invitation)
Short version in
SIGMOD Record (
2021, by invitation)
PODS 2020
PODS 2020 Best Paper Award
2021 ACM SIGMOD Research Highlight Award
Invited to HALG 2021
READ: Recursive autoencoders for document layout generation
Akshay Gadi Patil*,
Omri BenEliezer,
Or Perel,
Hadar AverbuchElor
CVPR 2020 Workshop on Text and Documents in the Deep Learning Era.
Best Paper Award
The adversarial robustness of sampling
Omri BenEliezer,
Eylon Yogev
PODS 2020
Invited to HALG 2020
Very fast construction of boundeddegree spanning graphs via the semirandom graph process
Omri BenEliezer,
Lior Gishboliner,
Dan Hefetz,
Michael Krivelevich
Random Structures and Algorithms (
2020)
SODA 2020
Semirandom graph process
Omri BenEliezer,
Dan Hefetz,
Gal Kronenberg,
Olaf Parczyk,
Clara Shikhelman,
Miloš Stojaković
Random Structures and Algorithms (
2020)
Hard properties with (very) short PCPPs and their applications
Omri BenEliezer,
Eldar Fischer,
Amit Levi,
Ron D. Rothblum
ITCS 2020
2019
The hat guessing number of graphs
Noga Alon,
Omri BenEliezer,
Chong Shangguan,
Itzhak Tamo
Journal of Combinatorial Theory, Series B (
2020)
ISIT 2019
Finding monotone patterns in sublinear time
Omri BenEliezer,
Clément Canonne,
Shoham Letzter,
Erik Waingarten
FOCS 2019
Testing local properties of arrays
Omri BenEliezer
ITCS 2019
On the separation conjecture in AvoiderEnforcer games
Małgorzata BednarskaBzdęga,
Omri BenEliezer,
Lior Gishboliner,
Tuan Tran
Journal of Combinatorial Theory, Series B (
2019)
2018 or older
Earthmover resilience and testing in ordered structures
Omri BenEliezer,
Eldar Fischer
CCC 2018
Improved bounds for testing forbidden order patterns
Omri BenEliezer,
Clément Canonne
SODA 2018
Testing hereditary properties of ordered graphs and matrices
Noga Alon,
Omri BenEliezer,
Eldar Fischer
FOCS 2017
Efficient removal lemmas for matrices
Noga Alon,
Omri BenEliezer.
Order (
2020)
RANDOM 2017
Deleting and testing forbidden patterns in multidimensional arrays
Omri BenEliezer,
Simon Korman,
Daniel Reichman
ICALP 2017
Local and global colorability of graphs
Noga Alon,
Omri BenEliezer.
Discrete Mathematics (
2016)
Notes
Information spread with error correction
Omri BenEliezer,
Elchanan Mossel,
Madhu Sudan
Theses
Fast algorithms in highly structured settings
PhD Thesis, Tel Aviv University, June 2020. Supervisor: Prof.
Noga Alon
Local and global colorability of graphs
MSc Thesis, Tel Aviv University, April 2015. Supervisor: Prof.
Noga Alon
Teaching
 MIT 18.200A, Principles of Discrete Applied Mathematics Fall 2022, lecturer.
 MIT 18.200, Principles of Discrete Applied Mathematics Spring 2022.
 MIT 18.01, Single variable calculus Fall 2021.
 Harvard CMSA computer science for mathematicians seminar
2020/21
 Probabilistic methods in combinatorics (03664913), Tel Aviv University, spring 2017.
 Data structures (03682158), Tel Aviv University, 2016/2017.
 Programming in python for engineers (05091820), Tel Aviv University,
2015/2016
Accessibility