Omri Ben-Eliezer
E-mail: omrib@mail.tau.ac.il
I am a PhD student in computer science, supervised by Prof. Noga Alon. My Master's degree was also completed in Tel Aviv University under the supervision of Noga Alon.

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.


A framework for adversarially robust streaming algorithms.
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev.

PODS 2020.
Best Paper Award.

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.

Hard properties with (very) short PCPPs and their applications.
Omri Ben-Eliezer, Eldar Fischer, Amit Levi, Ron D. Rothblum.

ITCS 2020.

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

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