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