Omri Ben-Eliezer
E-mail: omribene@cmsa.fas.harvard.edu
I am a Postdoctoral Fellow at Harvard CMSA, mentored by Madhu Sudan. I've recently completed my PhD 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.

Research interests

Algorithmic and mathematical problems in computer science, with a focus on algorithms for large-scale structured data. I'm especially interested in sublinear-time and streaming algorithms, adversarially robust algorithms, and learning-based algorithms. I'm also interested in establishing mathematical foundations of more applied areas such as decision making, data mining, knowledge representation, and computer vision.


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

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 (to appear).
To be presented at SIGGRAPH 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.

PODS 2020.
PODS 2020 Best Paper Award.
2021 ACM SIGMOD Research Highlight Award.
Invited to the Journal of the ACM.
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 Waingraten.
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).
RANDOM 2017.

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

Preprints available online

Optimal adaptive detection of monotone patterns.
Omri Ben-Eliezer, Shoham Letzter, Erik Waingraten.