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.
