NSF Student Travel Grant for 2019 Caleidoscope Research School in Computational Complexity (Caleidoscope)

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

This award will support student attendance at the Caleidoscope school, a one-week summer school in computational complexity to be held in Paris, France, June 17-21, 2019. Caleidoscope is intended for graduate students as well as established researchers who wish to learn more about neighboring areas. This award will provide partial support to approximately 6 students to attend this school. Efforts will be made to support students from under-represented groups and geographic diversity among students will be taken into account. It will contribute towards attracting more under-represented groups to computer science research giving students an opportunity to engage in the important technical, professional, and social exchanges.Computational complexity theory was born more than 50 years ago when researchers started asking what could be computed efficiently. Classifying problems or functions with respect to the amount of resources (e.g. time and/or space) needed to solve or compute them turned out to be an extremely difficult question. This has led researchers to develop a remarkable variety of approaches, employing different mathematical methods and theories. The future development of complexity theory will require a subtle understanding of the similarities, differences, and limitations of the many current approaches. In fact, even though these approaches study the same phenomena, they are developed today within disjoint communities, with little or no communication between them (e.g. algorithms, logic, programming theory, algebra, etc.). This dispersion is unfortunate since it hinders the development of hybrid methods and more generally the advancement of computational complexity as a whole. The goal (and peculiarity) of the Caleidoscope school is to reunite in a single event as many different takes on computational complexity as can reasonably be fit in one week.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.