@ 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 concurrent data-structures and algorithms in both

asynchronous shared memory and message-passing models, and

more recently, the population protocol model.

My favourite problem is Leader Election (Test-and-Set). I love

lower bounds, but most of my attempts so far ended up with algorithms.

I did undergrad at ETH Zurich.

# 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

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.

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.*

*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.*

*Proceedings of 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.*

*Proceedings of 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.