שלחו לחבר

Short paths in expander graphs

Seminar
Speaker
Klim Efremenko (Tel-Aviv U)
Date
08/11/2015 - 15:30 - 14:00
Place
Building 216, Room 201
Abstract

In this talk we study short edge-disjoint paths in expander graphs(here it mean: graph with constant mixing time). We use the Lovasz Local Lemma to prove the following result: Given a d-regular expander graph G and a set L={(s_i,t_i)} such that each vertex of G appears at most O(d) times in the list, there exist a set of edge disjoint paths of constant length connecting each s_i to t_i. This result has applications to multiparty computation performed over networks in the presence of random noise.

תאריך עדכון אחרון : 04/11/2015