Omri Ben-Eliezer  |  office: MIT 2-232B | email:
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: PODS 2025, WSDM 2024, IJCAI 2024, ITCS 2022.


(Order of authors is alphabetical by default, unless first author is marked with *)

Property testing with online adversaries
Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova
ITCS 2024, to appear

Is this correct? Let's check!
Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan
ITCS 2023

Archimedes meets privacy: On privately estimating quantiles in high dimensions under minimal assumptions
Omri Ben-Eliezer, Dan Mikulincer, Ilias Zadik
NeurIPS 2022

Active learning polynomial threshold functions
Omri Ben-Eliezer, Max Hopkins, Chutong Yang, Hantao Yu
NeurIPS 2022

Sampling multiple nodes in large networks: Beyond random walks
Omri Ben-Eliezer*, Talya Eden, Joel Oren, Dimitris Fotakis
WSDM 2022, selected for oral presentation

Finding monotone patterns in sublinear time, adaptively
Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten
ICALP 2022

Adversarially robust streaming via dense-sparse trade-offs
Omri Ben-Eliezer, Talya Eden, Krzysztof Onak
SOSA 2022

Adversarial laws of large numbers and optimal regret in online classification
Noga Alon, Omri Ben-Eliezer, 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 Ben-Eliezer, Shai Mazor, Hadar Averbuch-Elor
Transactions on Graphics (2021)
Presented at SIGGRAPH 2021

What is learned in knowledge graph embeddings?
Michael R. Douglas*, Michael Simkin, Omri Ben-Eliezer, Tianqi Wu, Peter Chin, Trung V. Dang, Andrew Wood
Complex Networks 2021

Bounded space differentially private quantiles
Daniel Alabi, Omri Ben-Eliezer, Anamay Chaturvedi
Transactions on Machine Learning Research (2023)
TPDP 2021

Limits of ordered graphs and their applications
Omri Ben-Eliezer, Eldar Fischer, Amit Levi, Yuichi Yoshida

ITCS 2021

A framework for adversarially robust streaming algorithms
Omri Ben-Eliezer, 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 Ben-Eliezer, Or Perel, Hadar Averbuch-Elor

CVPR 2020 Workshop on Text and Documents in the Deep Learning Era.
Best Paper Award

The adversarial robustness of sampling
Omri Ben-Eliezer, Eylon Yogev
PODS 2020
Invited to HALG 2020

Very fast construction of bounded-degree spanning graphs via the semi-random graph process
Omri Ben-Eliezer, Lior Gishboliner, Dan Hefetz, Michael Krivelevich
Random Structures and Algorithms (2020)
SODA 2020

Semi-random graph process
Omri Ben-Eliezer, 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 Ben-Eliezer, Eldar Fischer, Amit Levi, Ron D. Rothblum

ITCS 2020

The hat guessing number of graphs
Noga Alon, Omri Ben-Eliezer, Chong Shangguan, Itzhak Tamo
Journal of Combinatorial Theory, Series B (2020)
ISIT 2019

Finding monotone patterns in sublinear time
Omri Ben-Eliezer, Clément Canonne, Shoham Letzter, Erik Waingarten
FOCS 2019

Testing local properties of arrays
Omri Ben-Eliezer
ITCS 2019

On the separation conjecture in Avoider-Enforcer games
Małgorzata Bednarska-Bzdęga, Omri Ben-Eliezer, Lior Gishboliner, Tuan Tran

Journal of Combinatorial Theory, Series B (2019)

Earthmover resilience and testing in ordered structures
Omri Ben-Eliezer, Eldar Fischer

CCC 2018

Improved bounds for testing forbidden order patterns
Omri Ben-Eliezer, Clément Canonne

SODA 2018

Testing hereditary properties of ordered graphs and matrices
Noga Alon, Omri Ben-Eliezer, Eldar Fischer

FOCS 2017

Efficient removal lemmas for matrices
Noga Alon, Omri Ben-Eliezer.

Order (2020)

Deleting and testing forbidden patterns in multi-dimensional arrays
Omri Ben-Eliezer, Simon Korman, Daniel Reichman

ICALP 2017

Local and global colorability of graphs
Noga Alon, Omri Ben-Eliezer.
Discrete Mathematics (2016)

Notes and Preprints

Does prior knowledge help detect collisions?
Omri Ben-Eliezer, Tomer Grossman, Moni Naor

Information spread with error correction
Omri Ben-Eliezer, Elchanan Mossel, Madhu Sudan


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