*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Abstract:
This is a talk in two parts, linked by probabilistic methods and linear algebra. In the first half, we look at the problem of finding all 2-edge cuts in a graph. For this we give a simple algorithm based on uniformly sampling the graph's cycle space (all Eulerian subgraphs). Its distributed implementation is time-optimal on every graph. In the second half, we talk about partitioning set systems into set covers. Mainly, as a function of the minimum degree and maximum set size, how many disjoint covers can be obtained? The tools used to answer this include discrepancy theory and iterated linear programming.
This is joint work with R. Thurimella; and with B. Bollobas, T. Rothvoss, & A. Scott.
