@ gelash cs.toronto.edu
and had the pleasure to be supervised by Prof. Nir Shavit.
Starting in Fall'17, I am a Postdoctoral Fellow at the
University of Toronto, working with Prof. Faith Ellen.
My research is in distributed computing,
centered on the complexity of synchronization.
I have worked on the complexity of randomized concurrent algorithms
in different asynchronous distributed models:
time and space complexity of algorithms in shared-memory systems,
time and message complexity in the message passing models, and
time and state complexity of population protocols.
My full research statement can be found here.
During high school, I competed at international math and informatics olympiads.
I did my undergrad at ETH Zurich and have interned
at Google, Facebook, Akamai, Microsoft Reseach, Dropbox and D.E.Shaw.
I like coding when I do math and I like math when I code :-).
Here is what I wish every researcher had on their websites, a list of some of their favorite papers.
This can guide anyone looking to learn about the fields, or for getting a sense of personal taste.
Time-testedFLP: A must-read for anyone interested in asynchrony. Foundational.
Burns-Lynch: This paper introduced covering arguments. Very clever and elegant.
Tight Step Bound for Consensus by Attyia and Censor-Hillel: Beautiful techniques, some originating in this
tour de force by Aspnes that bounds the number of randomized coin flips.
Gödel prize-winning papers showing k-set agreement impossibility: Establishing a connection between combinatorial
topology and distributed computing. I recommend checking Maurice Herlihy's website for sources to learn more.
More recentDoty-Soloveichik linear time lower bound for constant-state population protocols: Hands down the favorite paper
that came out during my PhD. Check it out for yourself.
Tight space bound for consensus by Zhu. The proof fits in 3 pages and solves a problem that was open for 20+ years.
And it was not for the lack of trying :-).
Space-optimal Test-and-Set: All of the above were lower bounds, so here is what a real upper bound looks like.
Bachelor Thesis: Attacks on re-keying and renegotiation in Key Exchange Protocols. 2012, Supervisor: Cas Cremers. [full text]
Master Thesis: Leader election and renaming with optimal message complexity. 2014, Advisor: Nir Shavit. [dspace]
Doctoral Thesis: On the complexity of synchronization. 2017, Advisor: Nir Shavit. [dspace]
Why Extension-Based Proofs Fail. D. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu. Submitted to PODC 2018 [draft]
Revisionist Simulations: A New Approach to Proving Space Lower Bounds. F. Ellen, R. Gelashvili, L. Zhu. Submitted to PODC 2018 [arxiv]
Towards Reduced Instruction Sets for Synchronization. R. Gelashvili, I. Keidar, A. Spiegelman, R. Wattenhofer. DISC 2017 Brief Announcement, Vienna, Austria, 2017. [arxiv]
A Complexity-Based Hierarchy for Multiprocessor Synchronization. F. Ellen, R. Gelashvili, N. Shavit, L. Zhu. PODC 2016, Chicago, USA, 2016. [arxiv]
Optimal Space Complexity of Consensus for Anonymous Processes. R. Gelashvili. DISC 2015, Tokyo, Japan, 2015. [arxiv] Best Paper Award
On the Importance of Registers for Computability. R. Gelashvili, M. Ghaffari, J. Li, N. Shavit. OPODIS 2014, Cortina d'Ampezzo, Italy, 2014. [arxiv]
Dynamic Task Allocation in Asynchronous Shared Memory. D. Alistarh, J. Aspnes, M. A. Bender, R. Gelashvili, S. Gilbert. SODA 2014, Portland, Oregon, 2014. [full text]
Space-Optimal Majority in Population Protocols. D. Alistarh, J. Aspnes, R. Gelashvili. SODA 2018, New Orleans, USA, 2018. [arxiv]
Time-Space Trade-offs in Population Protocols. D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, R. L. Rivest. SODA 2017, Barcelona, Spain, 2017. [arxiv]
Fast and Exact Majority in Population Protocols. D. Alistarh, R. Gelashvili, M. Vojnovic. PODC 2015, Donostia-San Sebastian, Spain, 2015. [full text]
Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States. D. Alistarh, R. Gelashvili. ICALP 2015, Kyoto, Japan, 2015. [arxiv]
How to Elect a Leader Faster than a Tournament. D. Alistarh, R. Gelashvili, A. Vladu. PODC 2015, Donostia-San Sebastian, Spain, 2015. [arxiv]
Restricted Isometry Property for General p-Norms.
Z. Allen-Zhu, R. Gelashvili, I. Razenshteyn.
SoCG 2015, Eindhoven, Netherlands, 2015.
Journal: IEEE Transactions on Information Theory, Vol. 62, Issue 10, pp. 5839-5854, 2016. [arxiv]
Sparse Sign-Consistent Johnson-Lindenstrauss Matrices: Compression with Neuroscience-Based Constraints.
Z. Allen-Zhu, R. Gelashvili, S. Micali, N. Shavit.
Journal: Proceedings of the national academy of sciences (PNAS), vol 111, no. 47, 2014. [link]
Mining Railway Delay Dependencies in Large-Scale Real-World Delay Data. H. Flier, R. Gelashvili, T. Graffagnino, M. Nunkesser. Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems. Lecture Notes in Computer Science, Vol. 5868, pp. 354-368, Springer, 2009.