Sukumar Das Adhikari (Harish-Chandra Research Institute (Allahabad, India))
X
A particular weighted generalization of some classical zero-sum constants was first considered about ten years back. Since then, many people got interested in this generalization. Similar generalizations of other zero-sum constants were also considered and these gave rise to several conjectures and questions; some of these conjectures have been established, some of the questions have been answered.
And most interestingly, some applications of this weighted generalization have also been found. After a short discussion on the classical results, we shall have a glimpse of these weighted generalizations.
Weighted zero-sum constants: a survey
May. 08, 2018 3pm (MATH 350)
Topology
Josh Grochow (CU Boulder)
X
The Unique Games Conjecture states that approximating certain optimization problems to within some factor is NP-hard; over the past ~15 years it has been one of the most actively researched conjectures in computational complexity. In this talk I will give background on this conjecture, and explain how it is "really" about computational topology. In particular, we can rephrase the Unique Games Conjecture as a certain conjecture on the following computational problem: given given a finite graph Gamma, a finite group G, and a (not-necessarily-principle) G-bundle on Gamma, find the largest subset of Gamma over which the bundle admits a section. This observation originally goes back to Linial (2005), but here we extend it to show that several other aspects of this conjecture are essentially topological in nature. We use this viewpoint to mostly settle an open question of Chen & Freedman (2010). No background in computer science will be assumed. Our hope is that our observations on the topological nature of the Unique Games Conjecture will lead to applications of algebraic topology to the Unique Games Conjecture in the future.
Based on joint work with Jamie Tucker-Foltz arXiv:1803.06800, to appear in the 34th International Symposium on Computational Geometry (SoCG 2018).
Computational Topology & The Unique Games Conjecture