Special Year Workshops on Combinatorics and Complexity

点击翻译按钮获取中文摘要

The Special Year Workshops on Combinatorics and Complexity award supports four workshops at the interface of the two fields during the periods of 2-6 October 2017, 13-17 November 2017, 5-9 February 2018, and 9-13 April 2018 at the Harvard Center of Mathematical Sciences and Applications (CMSA) in Cambridge, Massachusetts. Combinatorics and Computational Complexity have enjoyed a rich history of interaction leading to many significant developments in the two fields, such as the theories of NP-completeness, expander graphs, pseudorandomness, and property testing. Lately these fields have seen many new points of intersection such as in the development of the polynomial method (used, for example, in recent advances on the cap-set problem as well as in development of optimal list-decodable codes), the method of interlacing families of polynomials (yielding Ramanujan graphs and the resolution of the Kadison-Singer problem), and the theory of randomness extractors (yielding explicit constructions of Ramsey graphs. The base funding for the workshops will be provided by the Harvard CMSA and will enable the participation of senior visitors and a core group of leaders in the fields. Additional funding provided by this award will support the travel and local arrangements of graduate students, postdocs, junior researchers, members of underrepresented groups, and those without other forms of support. Topics to be covered by the workshops include: (1) Additive Combinatorics (organized by Ben Green, Swastik Kopparty, Ryan O'Donnell and Tamar Zeigler). (2) Algebraic Methods in Combinatorics (organized by Zeev Dvir, Larry Guth and Shubhangi Saraf). (3) Probabilistic and Extremal Combinatorics (organized by David Conlon and Benjamin Sudakov) and (4) Coding and Information Theory (organized by Alexander Barg, Venkatesan Guruswami, and Mary Wootters). Further information on the workshops and other special year activities may be found at http://cmsa.fas.harvard.edu/combinatorics/.