@ gelash mit.edu

Office: 32-G630

I am a Ph.D. student in the Multicore Algorithms Group at MIT,

working with Prof. Nir Shavit.

I work 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, and

time and state complexity of population protocols.

I did my undergrad at ETH Zurich and have interned

at Google, Facebook, Akamai, Microsoft Reseach and Dropbox.

I like coding when I do math and I like math when I code.

# Detour

Math comes in many flavors. Here is my second favourite proof,

*but*instead of the Handshaking Lemma,

let us call edges doors and triangles rooms. Imagine entering the big triangle through an outer door.

Every room we enter, either it is the promised triangle, or it has exactly one more, unexplored door.

Keep walking, re-entering through a new outer door as necessary. There are odd number of outer doors,

so we must come to a halt in some room, and that will be it, the triangle of all colors.

And

*I know*, that was just a proof of the Handshaking Lemma.

My most favourite proof, I will not share.

# Publications

D. Alistarh, J. Aspnes, R. Gelashvili

*Space-Optimal Majority in Population Protocols.*

*Submitted*
[arxiv]

D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, R. L. Rivest

*Time-Space Trade-offs in Population Protocols.*

*SODA 2017*, Barcelona, Spain, 2017.
[arxiv]

F. Ellen, R. Gelashvili, N. Shavit, L. Zhu

*A Complexity-Based Hierarchy for Multiprocessor Synchronization.*

*PODC 2016*, Chicago, USA, 2016.
[arxiv]

R. Gelashvili

*Optimal Space Complexity of Consensus for Anonymous Processes.*

*DISC 2015*, Tokyo, Japan, 2015.
[arxiv] **Best Paper Award**

D. Alistarh, R. Gelashvili, M. Vojnovic

*Fast and Exact Majority in Population Protocols.*

*PODC 2015*, Donostia-San Sebastian, Spain, 2015.
[full text]

D. Alistarh, R. Gelashvili, A. Vladu

*How to Elect a Leader Faster than a Tournament.*

*PODC 2015*, Donostia-San Sebastian, Spain, 2015.
[arxiv]

D. Alistarh, R. Gelashvili

*Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States.*

*ICALP 2015*, Kyoto, Japan, 2015.
[arxiv]

Z. Allen-Zhu, R. Gelashvili, I. Razenshteyn.

*Restricted Isometry Property for General p-Norms.*

*IEEE Transactions on Information Theory*, Vol. 62, Issue 10, pp. 5839-5854, 2016

*SoCG 2015*, Eindhoven, Netherlands, 2015.
[arxiv]

Z. Allen-Zhu, R. Gelashvili, S. Micali, N. Shavit.

*Sparse Sign-Consistent Johnson-Lindenstrauss Matrices: Compression with Neuroscience-Based Constraints.*

*PNAS 2014*, vol 111, no. 47
[link]

R. Gelashvili, M. Ghaffari, J. Li, N. Shavit.

*On the Importance of Registers for Computability.*

*OPODIS 2014*, Cortina d'Ampezzo, Italy, 2014.
[arxiv]

D. Alistarh, J. Aspnes, M. A. Bender, R. Gelashvili, S. Gilbert.

*Dynamic Task Allocation in Asynchronous Shared Memory.*

*SODA 2014*, Portland, Oregon, 2014.
[full text]

R. Gelashvili.

*Attacks on re-keying and renegotiation in Key Exchange Protocols.*

*Bachelor Thesis*, 2012, Supervisor: Cas Cremers.
[full text]

H. Flier, R. Gelashvili, T. Graffagnino, M. Nunkesser.

*Mining Railway Delay Dependencies in Large-Scale Real-World Delay Data.*

*Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems.*

Lecture Notes in Computer Science, Vol. 5868, pp. 354-368, Springer, 2009.