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 algorithms; algorithms and society; 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!
Program Committees:
FOCS 2025, PODS 2025, WSDM 2025, ESA 2025, WSDM 2024, IJCAI 2024, ITCS 2022
|
|
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. Selected for
oral presentation
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