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

The interplay between structure and algorithms in computer science, with a focus on sublinear algorithms for highly structured problems. Some topics on which I've been working recently:
  • Property testing in ordered structures, and related combinatorial questions.
  • Practical sublinear algorithms for sampling in real-world social networks.
  • Deep representation and synthesis of structured data.
  • Adversarial robustness of algorithms for massive data.

Preprints available online

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

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


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.
Best Paper Award.
2021 ACM SIGMOD Research Highlight Award.
Invited to the Journal of the ACM.

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.

The hat guessing number of graphs.
Noga Alon, Omri Ben-Eliezer, Chong Shangguan, Itzhak Tamo.
Journal of Combinatorial Theory, Series B (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.

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 (Track A).

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