Omri Ben-Eliezer  |  office: MIT 2-232B | 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: 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 mathematical and algorithmic foundations of more applied areas such as decision making, data mining, and knowledge representation.

Program Committees: ITCS'22.
Check out our recent STOC'21 workshop Robust Streaming, Sketching, and Sampling.

Publications

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

Preprints

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

2021+

Finding monotone patterns in sublinear time, adaptively.
Omri Ben-Eliezer, Shoham Letzter, Erik Waingraten.
ICALP 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.

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.
TPDP 2021.

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

2020

A framework for adversarially robust streaming algorithms.
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev.
Journal of the ACM (2022, by invitation).
PODS 2020.
PODS 2020 Best Paper Award.
2021 ACM SIGMOD Research Highlight Award. Short version in SIGMOD Record (2021).
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.

2019

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

2018 or older

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

Notes

Information spread with error correction.
Omri Ben-Eliezer, 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


Accessibility