|
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 Theoretical and algorithmic foundations of big data: sublinear time and streaming algorithms, beyond worst case analysis of algorithms, robustness and privacy, knowledge representation, complex networks. Program Committees: ITCS'22. Check out our STOC'21 workshop Robust Streaming, Sketching, and Sampling. New: see my recent talk on robust sampling and online learning at the Virtual talk series on foundations of data science. |
 |
Publications
(Order of authors is alphabetical by default, unless first author is marked with *)2022+
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
2021
Adversarial laws of large numbers and optimal regret in online classificationNoga 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 algorithmsOmri 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
2019
The hat guessing number of graphsNoga 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)
2018 or older
Earthmover resilience and testing in ordered structuresOmri 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 correctionOmri Ben-Eliezer, Elchanan Mossel, Madhu Sudan
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
Teaching
- MIT 18.200A, Principles of Discrete Applied Mathematics Fall 2022, lecturer.
- MIT 18.200, Principles of Discrete Applied Mathematics Spring 2022.
- MIT 18.01, Single variable calculus Fall 2021.
- Harvard CMSA computer science for mathematicians seminar 2020/21
- Probabilistic methods in combinatorics (0366-4913), Tel Aviv University, spring 2017.
- Data structures (0368-2158), Tel Aviv University, 2016/2017.
- Programming in python for engineers (0509-1820), Tel Aviv University, 2015/2016
Accessibility