- Time-Space Trade-Offs in Mo...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in October 2016

## Time-Space Trade-Offs in Molecular Computation

**Speaker:**
Rati Gelashvili

**Date:**
Wednesday, October 26, 2016

**Time:**
4:00 PM to 5:00 PM
** Note: all times are in the Eastern Time Zone**

**Public:**
Yes

**Location:**
32)g575

**Event Type:**

**Room Description:**

**Host:**
Pritish Kamath and Akshay Degwekar

**Contact:**
Rebecca Yadegar, ryadegar@csail.mit.edu

**Relevant URL:**
http://toc.csail.mit.edu/node/1039

**Speaker URL:**
None

**Speaker Photo:**

None

**Reminders to:**
seminars@csail.mit.edu, theory-seminars@csail.mit.edu

**Reminder Subject:**
TALK: Rati Gelashvili:Time-Space Trade-Offs in Molecular Computation

Abstract: Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special "leader" state), and majority (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory (number of states) available to each agent.

I will overview different results with a spectrum of time-space guarantees for these tasks, culminating in algorithms showing that fast, poly-logarithmic convergence time can be achieved using O(log^2 n) space per node in both cases. I will also present a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, any protocol solving either of these tasks for n agents using O(log log n) states must take ?(n / polylog n) expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. Overall, these results highlight a time complexity separation between O(log log n) and ?(log^2 n) state space size for both majority and leader election, and introduce new techniques, which should be applicable more broadly.

This is based on joint works with Dan Alistarh, James Aspnes, David Eisenstat, Ronald L. Rivest and Milan Vojnovic.

**Research Areas:**

**Impact Areas:**

Created by Rebecca Yadegar at Wednesday, October 19, 2016 at 1:37 PM.