Seminars and Colloquia by Series

Monday, November 20, 2017 - 14:05 , Location: Skiles 006 , Kevin Kordek , Georgia Institute of Technology , Organizer: Dan Margalit
Friday, November 17, 2017 - 15:00 , Location: Skiles 005 , Huseyin Acan , Rutgers University , Organizer: Lutz Warnke
Thursday, November 16, 2017 - 13:30 , Location: Skiles 005 , Vijay Vazirani , CS, GT , Organizer: Robin Thomas
Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P),  and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution!The case of bipartite planar graphs was solved by Miller and Naor in 1989 via a flow-based algorithm.  In 2000, Mahajan and Varadarajan gave an elegant way of using counting matchings to finding one, hence giving a different NC algorithm.However, non-bipartite planar graphs still didn't yield: the stumbling block being odd tight cuts.  Interestingly enough, these are also a key to the solution: a balanced odd tight cut leads to a straight-forward divide and conquer NC algorithm. The remaining task is to find such a cut in NC. This requires several algorithmic ideas, such as finding a point in the interior of the minimum weight face of the perfect matching polytope and uncrossing odd tight cuts.Joint work with Nima Anari.
Wednesday, November 15, 2017 - 13:55 , Location: Skiles 006 , Surena Hozoori , Georgia Tech , Organizer: Jennifer Hom
Wednesday, November 15, 2017 - 13:55 , Location: Skiles 005 , Cristina Pereyra , University of New Mexico , Organizer: Shahaf Nitzan
Monday, November 13, 2017 - 15:00 , Location: Skiles 006 , Renee Bell , Massachusetts Institute of Technology , , Organizer: Padmavathi Srinivasan
Given a Galois cover of curves X to Y with Galois group G which is totally ramified at a point x and unramified elsewhere, restriction to the punctured formal neighborhood of x induces a Galois extension of Laurent series rings k((u))/k((t)). If we fix a base curve Y , we can ask when a Galois extension of Laurent series rings comes from a global cover of Y in this way. Harbater proved that over a separably closed field, this local-to-global principle holds for any base curve if G is a p-group, and gave a condition for the uniqueness of such an extension. Using a generalization of Artin-Schreier theory to non-abelian p-groups, we characterize the curves Y for which this lifting property holds and when it is unique, but over a more general ground field.
Monday, November 13, 2017 - 13:55 , Location: Skiles 006 , Thang Le , Georgia Tech , , Organizer: Thang Le
Monday, November 13, 2017 - 13:55 , Location: Skiles 005 , Tuo Zhao , Georgia Tech , Organizer: Wenjing Liao
Friday, November 10, 2017 - 15:00 , Location: Skiles 006 , Prof. Fumin Zhang , GT ECE , Organizer: Sung Ha Kang
Thursday, November 9, 2017 - 15:05 , Location: Skiles 006 , Elliot Paquette , The Ohio State University , Organizer: Lutz Warnke