|
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
Density-accuracy tradeoffs in real-world graph spanners
Nadia Koshima*, Tim Rieder*, Sabyasachi Basu, Talya Eden, Omri Ben-Eliezer
ACDA 2025, extended abstract, to appear.
A sublinear algorithm for approximate shortest paths in large networks
Sabyasachi Basu*, Nadia Koshima* , Talya Eden, Omri Ben-Eliezer, C. Seshadhri
WSDM 2025. 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 settingsPhD 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