Short paths in expander graphs

Seminar
Speaker
Klim Efremenko (Tel-Aviv U)
Date
08/11/2015 - 15:30 - 14:00Add to Calendar 2015-11-08 14:00:00 2015-11-08 15:30:00 Short paths in expander graphs 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. Building 216, Room 201 אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
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.

Last Updated Date : 04/11/2015