Theory Talk May 21, 2019 1:30pm — 2:30pm Location: 7501 - Gates Hillman Centers Speaker: RICHARD PENG , Assistant Professor https://www.cc.gatech.edu/~rpeng/ Batch-Dynamic Graph Algorithms We study parallel algorithms for large evolving graphs: the edges are distributed over machines with small space, and updates/queries arrive in small batches. We give constant round batch-dynamic algorithms for several problem considered difficult to solve in O(1) parallel rounds statically, including undirected connectivity, directed max-matching, and maximal independent set.Lower bounds in this model face difficulties inherent to communication-based models: the machines can perform arbitrarily powerful computations between rounds of communications. Here we obtain a separation in the difficulties of batch-dynamic undirected connectivity by combining adaptivity with P-hardness reductions.Based on ongoing works with Laxman Dhulipala, David Durfee, Janardan Kulkarni, Saurabh Sawlani, and Xiaorui Sun.Faculty Host: Gary Miller For More Information: eedavis@andrew.cmu.edu Add event to Google Add event to iCal
