## Seminars and Colloquia by Series

Friday, November 17, 2017 - 15:00 , Location: Skiles 005 , Huseyin Acan , Rutgers University , Organizer: Lutz Warnke
A 1992 conjecture of Alon and Spencer says, roughly, that the ordinary random graph G_{n,1/2} typically admits a covering of a constant fraction of its edges by edge-disjoint, nearly maximum cliques. We show that this is not the case. The disproof is based on some (partial) understanding of a more basic question: for k ≪ \sqrt{n} and A_1, ..., A_t chosen uniformly and independently from the k-subsets of {1…n}, what can one say about P(|A_i ∩ A_j|≤1 ∀ i≠j)? Our main concern is trying to understand how closely the answers to this and a related question about matchings follow heuristics gotten by pretending that certain (dependent) choices are made independently. Joint work with Jeff Kahn.
Friday, November 17, 2017 - 15:00 , Location: Skiles 006 , , Univ. Stuttgart , , Organizer:

This is part of the 2017 Quolloquium series.

Starting from the classical Berezin- and Li-Yau-bounds onthe eigenvalues of the Laplace operator with Dirichlet boundaryconditions I give a survey on various improvements of theseinequalities by remainder terms. Beside the Melas inequalitywe deal with modifications thereof for operators with and withoutmagnetic field and give bounds with (almost) classical remainders.Finally we extend these results to the Heisenberg sub-Laplacianand the Stark operator in domains.
Friday, November 17, 2017 - 10:00 , Location: Skiles 114 , Timothy Duff , GA Tech , Organizer: Timothy Duff
Motivated by the general problem of polynomial system solving, we state and sketch a proof Kushnirenko's theorem. This is the simplest in a series of results which relate the number of solutions of a "generic" square polynomial system to an invariant of some associated convex bodies. For systems with certain structure (here, sparse coefficients), these refinements may provide less pessimistic estimates than the exponential bounds given by Bezout's theorem.
Thursday, November 16, 2017 - 13:30 , Location: Skiles 005 , Vijay Vazirani , UC Irvine , 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.
Thursday, November 16, 2017 - 13:30 , Location: Skiles 005 , Vijay Vazirani , UC Irvine , 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.
Thursday, November 16, 2017 - 13:30 , Location: Skiles 006 , , Florida International University , , Organizer:

This is part of the 2017 Quolloquium series.

We use the weighted isoperimetric inequality of J. Ratzkin for a wedge domain in higher dimensions to prove new isoperimetric inequalities for weighted $L_p$-norms of the fundamental eigenfunction of a bounded domain in a convex cone-generalizing earlier work of Chiti, Kohler-Jobin, and Payne-Rayner. We also introduce relative torsional rigidity for such domains and prove a new Saint-Venant-type isoperimetric inequality for convex cones. Finally, we prove new inequalities relating the fundamental eigenvalue to the relative torsional rigidity of such a wedge domain thereby generalizing our earlier work to this higher dimensional setting, and show how to obtain such inequalities using the Payne interpretation in Weinstein fractional space. (Joint work with A. Hasnaoui)
Thursday, November 16, 2017 - 13:30 , Location: Skiles 006 , , Florida International University , , Organizer:

This is part of the 2017 Quolloquium series.

We use the weighted isoperimetric inequality of J. Ratzkin for a wedge domain in higher dimensions to prove new isoperimetric inequalities for weighted $L_p$-norms of the fundamental eigenfunction of a bounded domain in a convex cone-generalizing earlier work of Chiti, Kohler-Jobin, and Payne-Rayner. We also introduce relative torsional rigidity for such domains and prove a new Saint-Venant-type isoperimetric inequality for convex cones. Finally, we prove new inequalities relating the fundamental eigenvalue to the relative torsional rigidity of such a wedge domain thereby generalizing our earlier work to this higher dimensional setting, and show how to obtain such inequalities using the Payne interpretation in Weinstein fractional space. (Joint work with A. Hasnaoui)
Wednesday, November 15, 2017 - 13:55 , Location: Skiles 006 , Surena Hozoori , Georgia Tech , Organizer: Jennifer Hom
It is known that a class of codimension one foliations, namely "taut foliations", have subtle relation with the topology of a 3-manifold. In early 80s, David Gabai introduced the theory of "sutured manifolds" to study these objects and more than 20 years later, Andres Juhasz developed a Floer type theory, namely "Sutured Floer Homology", that turned out to be very useful in answering the question of when a 3-manifold with boundary supports a taut foliation.
Wednesday, November 15, 2017 - 13:55 , Location: Skiles 006 , Surena Hozoori , Georgia Tech , Organizer: Jennifer Hom
It is known that a class of codimension one foliations, namely "taut foliations", have subtle relation with the topology of a 3-manifold. In early 80s, David Gabai introduced the theory of "sutured manifolds" to study these objects and more than 20 years later, Andres Juhasz developed a Floer type theory, namely "Sutured Floer Homology", that turned out to be very useful in answering the question of when a 3-manifold with boundary supports a taut foliation.
Wednesday, November 15, 2017 - 13:55 , Location: Skiles 005 , Cristina Pereyra , University of New Mexico , Organizer: Michael Lacey
t-Haar multipliers are examples of Haar multipliers were the symbol depends both on the frequency variable (dyadic intervals) and on the space variable, akin to pseudo differential operators. They were introduced more than 20 years ago, the corresponding multiplier when $t=1$ appeared first  in connection to the resolvent of the dyadic paraproduct, the cases $t=\pm 1/2$ is intimately connected to direct and reverse inequalities for the dyadic square function in $L^2$, the case $t=1/p$ naturally appears in the study of weighted inequalities in $L^p$. Much has happened in the theory of weighted inequalities in the last two decades, highlights are the resolution of the $A_2$ conjecture (now theorem) by Hyt\"onen in 2012 and the resolution of the two weight problem for the Hilbert transform by  Lacey, Sawyer, Shen and Uriarte Tuero in 2014. Among the competing methods used to prove these results were Bellman functions, corona decompositions, and domination by sparse operators. The later method has gained a lot of traction and is being widely used in contexts beyond what it was originally conceived for  in work of Lerner, several of these new applications have originated here at Gatech. In this talk I would like to tell you what I know about t-Haar multipliers (some work goes back to my PhD thesis and joint work with Nets Katz and with my former students Daewon Chung, Jean Moraes, and Oleksandra Beznosova), and what we ought to know in terms of sparse domination.