Omri Ben-Eliezer  |  office: Taub 520 | email: omribene@cs.technion.ac.il

I am a Senior Lecturer (Assistant Professor) and Taub Fellow at the Faculty of Computer Science in the Technion — Israel Institute of Technology. I've completed my PhD at Tel Aviv University, where I was fortunate to be advised by Noga Alon. After that, I was a postdoc at Weizmann Institute (hosted by Moni Naor) and later at Harvard University (mentored by Madhu Sudan), an instructor in applied mathematics at MIT, and a research fellow at Simons Institute.

Research Interests: Theoretical and algorithmic foundations of big data, focusing on theoretical modeling of modern massive, complex, and challenging computational environments. Areas of interest include sublinear time and streaming algorithms, beyond worst case analysis of algorithms, robustness and privacy, knowledge representation, and complex networks.

Prospective Students: I am looking for motivated students interested in algorithmic research "between theory and practice". Feel free to reach out!
Omri Ben-Eliezer

Publications

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

Approximate counting of permutation patterns
Omri Ben-Eliezer, Slobodan Mitrović, Pranjal Srivastava
Preprint

On the instance optimality of detecting collisions and subgraphs
Omri Ben-Eliezer, Tomer Grossman, Moni Naor
Preprint

A sublinear algorithm for approximate shortest paths in large networks
Sabyasachi Basu*, Nadia Koshima* , Talya Eden, Omri Ben-Eliezer, C. Seshadhri
WSDM 2025, to appear

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

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

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

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

Accessibility