À¶Ý®ÊÓƵ

Title:ÌýWires, bits, and the cost of sorting

Abstract:ÌýHow hard is it to sort a list of n integers? A basic course on algorithms says it's O(n log n) time, but what if the list is enormous - so big you would need to cover the surface of the moon just to store it?

Title:ÌýDiagonal coefficients, graph invariants with the symmetries of Feynman integrals, and the proof of the c_2 completion conjecture

Abstract:ÌýIn a scalar field theory the contribution of a Feynman diagram to the beta function of the theory, the Feynman period, can be written as an integral in terms of the (dual) Kirchhoff polynomial of the graph.

Title:ÌýHypergraph Matchings Avoiding Forbidden Submatchings

Abstract:ÌýWe overview a general theoryÌýfor finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of forbidden submatchings (which we view as a hypergraph H where V(H)=E(G)).

Title:ÌýAlgorithmic Tools for Congressional Districting: Fairness via Analytics

Abstract:ÌýThe American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness and other related metrics.

Title:ÌýThe Chambolle-Pock algorithm revisited: splitting operator and its range with applications

Abstract:ÌýPrimal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions.

Title:ÌýA Simple Sparsification Algorithm for Maximum Matching with Applications to Graph StreamsÌý

Abstract:ÌýIn this talk, we present a simple algorithm that reducesÌýapproximating the maximum weight matching problem in arbitrary graphs to few adaptively chosen instances of the same problem on sparse graphs.

Title:ÌýAn Approximate Generalization of the Okamura-Seymour Theorem

Abstract:ÌýWe consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands.

Title:ÌýProof of the Clustered Hadwiger Conjecture

Abstract:ÌýHadwiger's Conjecture asserts that every Kh-minor-free graph isÌýproperly (h-1)-colourable. We prove the following improper analogue ofÌýHadwiger's Conjecture: for fixed h, every Kh-minor-free graph isÌý(h-1)-colourable with monochromatic components of bounded size.

Title:ÌýRigidity of Simplicial Complexes

Abstract:ÌýA simplicial k-cycle is an abstract simplicial k-complex in which every (k-1)-face belongs to an even number of k-faces. A simplicialÌýk-circuit is a minimal simplicial k-cycle (in the sense that none of its proper subcomplexes are simplicial k-cycles).

Title:ÌýCombinatorial and complexity theoretic aspects of Stabilities and Controllabilities of linear switched systems(discrete and continuous time)

Abstract:ÌýI will talk about my "pre-hyperbolic" research, some of it done jointly with Alex Samorodnitsky and Alex Olshevsky.