Sixteenth meeting: Saturday, November 10, 2018
Location: UNC Chapel Hill
Lecture Room: Hanes 120
Speakers:
László Babai (University of Chicago), Daniel Bienstock (Columbia), Rebecca Goldin (George Mason University), and Lek-Heng Lim (University of Chicago)
Registration and funding applications:
To register and/or apply for funding, please fill out this form. If you have any questions, feel free to email Cynthia Vinzant at clvinzan@ncsu.edu.
We are asking that participants pre-register if possible, as pre-registration is very helpful for planning our coffee breaks and obtaining funding to support these meetings. We have some funding available for some participants, especially for early-career participants. Most of this is restricted to US citizens and permanent residents, and what is available to others still requires that the participants be employed at a U.S. university. You will have the opporutunity to apply for funding when registering for the conference.
Conference schedule:
9:30-10am, coffee and "meet and greet"
10-11am, Lek-Heng Lim, Combinatorial geometry of deep neural networks (slides)
11-11:30am, coffee break
11:30am-12:30pm, Rebecca Goldin, On some (equivariant) combinatorics related to flag manifolds (slides)
12:30-2:15pm, lunch break
2:15-3:15pm, Daniel Bienstock, Approximate nonconvex optimization and tree-width (slides)
3:15-3:45pm, coffee break
3:45-4:30pm, László Babai, Global symmetry from local information: The graph isomorphism problem
4:30-4:45pm, coffee break
4:45-5:30pm, László Babai, Hidden irregularity vs. hidden symmetry: The emergence of the Johnson graph
6:30pm informal conference dinner
Local organizing committee:
Prakash Belkale (UNC Chapel Hill), Gabor Pataki (UNC Chapel Hill), Richard Rimanyi (UNC Chapel Hill), and Seth Sullivant (NCSU)
Parking: Some free parking is available in the N11 (Venable) parking lot, which is very close to Hanes Hall. (If you scroll towards the northeast, you will see Hanes hall on that map.) The lot has been reserved for TLC, but the reservation is not strictly enforced, so others may park there as well. Pay parking is available on Rosemary street. Those parking lots are about a 10 minute walk to Hanes hall.
Hotel recommendations: The Hampton Inn & Suites Chapel Hill/Carrboro (919-969-6988) is within walking distance of the conference. Other hotels in Chapel Hill that are within a few miles include Carolina Inn, The Franklin Hotel, AC Hotel by Marriott, Aloft, (Call Stephanie at 919-442-2773 for the UNC rate), Chapel Hill University Inn Hotel, and Hyatt Place Chapel Hill / Southern Village.
Airport: Raleigh-Durham International Airport is 20-30 minutes drive from UNC Chapel Hill. Taxi fare is about $30.
Participants:
Edward Allen (Wake Forest University)
László Babai (University of Chicago )
Prakash Belkale (UNC Chapel Hill)
Marc Besson (UNC Chapel Hill)
Daniel Bienstock (Columbia University)
Cash Bortner (NCSU)
Jordan Bryan (Duke University)
Changjia Cai (UNC Chapel Hill)
Miheer Dewaskar (UNC Chapel Hill)
Rebecca Goldin (George Mason University)
Brent Gorbutt (George Mason University)
Ian Gossett (Wake Forest University)
Gabor Hetyei (UNC Charlotte)
Jeff Hirst (Appalachian State University)
Benjamin Hollering (NCSU)
Jiuzu Hong (UNC Chapel Hill)
Sam Jeralds (UNC Chapel Hill)
Naihuan Jing (NCSU)
Sumit Kumar Kar (UNC Chapel Hill)
Joshua Kiers (UNC Chapel Hill)
Cassie Kierzkowski (Georgia Tech)
Jong-Min Kim (SAMSI & U. Minnesota at Morris)
Henry Kirveslahti (Duke University)
Paul Kruse (UNC Chapel Hill)
Stephen Lacina (NCSU)
Benjamin Leinwand (UNC Chapel Hill)
Gang Li (UNC Chapel Hill)
Lek-Heng Lim (University of Chicago)
Ricky Liu (NCSU)
Pengyu Liu (Simon Fraser University)
Gene Luks (University of Oregon)
Greg Malen (Duke University)
Sarah Mason (Wake Forest University)
Katherine Mawhinney (Appalachian State University)
Geoffrey McKenna (Oculus Group LLC)
Marie Meyer (Lewis University)
Katherine Moore (Wake Forest University)
Walter Morris (George Mason University)
Sayan Mukherjee (Duke University)
David Nichols (Wake Forest University)
Dávid Papp (NCSU)
Gabor Pataki (UNC Chapel Hill)
Robert Proctor (UNC Chapel Hill)
Sutipoj Promtapan (UNC Chapel Hill)
Richard Rimanyi (UNC Chapel Hill)
Justin Sawon (UNC Chapel Hill)
Alexey Slinkin (UNC Chapel Hill)
Jack Snoeyink (UNC Chapel Hill)
Michael Strayer (UNC Chapel Hill)
Changjian Su (University of Toronto)
Michael Suggs (NCSU)
Seth Sullivant (NCSU)
Zachary Taylor (NCSU)
Quoc Tran Dinh (UNC Chapel Hill)
Shira Viel (Duke University)
Cynthia Vinzant (NCSU)
Yongge Wang (UNC Charlotte)
Talk titles and abstracts:
Lek-Heng Lim (University of Chicago)
Title: Combinatorial geometry of deep neural networks
Abstract: A useful way to visualize a classification problem in machine learning is as a problem of finding a decision boundary that separates two collections of points (e.g., spam or nonspam) in some high-dimensional space. A simple data set, say, comprising points sampled from two disjoint convex sets, may be easily separated by a hyperplane but modern complex data sets tend to require more complex, usually piecewise linear, decision boundaries. The number of linear regions of a classifier then gives a measure of its expressive power. By undertaking a tropical geometric perspective, we show that the linear regions of a feedforward ReLU neural network correspond to vertices of polytopes associated with tropical rational functions. The main consequence of this is that a deeper network is exponentially more expressive than a shallow network, and a side observation is that zonotopes form the basic building blocks for deep neural networks.
This is joint work with Greg Naitzat (Chicago) and Liwen Zhang (Facebook).
Rebecca Goldin (George Mason University)
Title: On some (equivariant) combinatorics related to flag manifolds
Abstract: Schubert calculus arose from 19th Century explorations of enumerative geometry, but has evolved into the study of specific rings associated with homogeneous spaces. The topic includes, for example, examining the product structure of the cohomology ring of the Grassmannian of k-dimensional subspace of complex n-space, or the equivariant cohomology ring of G/P, where P is a parabolic in a complex group G), as well as the K-theory or equivariant K-theory of the complete flag variety. In a geometrically motivated basis for each ring, the product of any two basis elements, expanded in that basis, has coefficients that are positive in an appropriate sense.
Remarkably, equivariant cohomology and K-theory--which take into account a group action by a torus T (an abelian group)--have some advantages over their non-equivariant counterparts, even as they have strictly more information. They can be described simply by a sequence of polynomials (in the case of cohomology), and rational functions (in the case of K-theory). This description is amenable to combinatorial methods and provides hope for future positive formulas on structure constants. I will give an overview of some results on positivity, as well as a geometric (but unfortunately non-positive) recursion for computing these coefficients using divided difference operators. The last part is joint work with Allen Knutson.
Daniel Bienstock (Columbia)
Title: Approximate nonconvex optimization and tree-width
Abstract: The intersection graph of an optimization problem has a vertex corresponding to each variable and an edge between two vertices whenever the corresponding variables appear in the same constraint. This is a classical concept dating to more than fifty years ago. In this talk we discuss how the structure of the intersection graph, in particular low tree-width, can be leveraged to produce rigorous algorithms for approximate optimization of nonconvex problems. This body of work encompasses research by other authors, and recent work by the author and collaborators. We will also discuss applications to generalization problems in machine learning.
László Babai (University of Chicago)
Title, Part 1: Global symmetry from local information: The graph isomorphism problem
Title, Part 2: Hidden irregularity vs. hidden symmetry: The emergence of the Johnson graph
Abstract: In the first talk we explain the central, group theoretic, component of the recent quasipolynomial-time algorithm to test isomorphism of graphs. The second talk outlines the combinatorial ingredients, based on coherent configurations (certain highly regular colorings of the edges of the complete directed graph).