AF: small: understanding expansion phenomena: graphical, hypergraphical, geometric, and quantum

The National Science Foundation (NSF) awarded a $202,207 Project Grant under its Computer and Information Science and Engineering (CFDA 47.070) program to the Toyota Technological Institute at Chicago (TTIC), a private non-profit university, to conduct research on understanding and applying different forms of "expansion phenomena" with applications in error-correcting codes, optimization problems, and geometric data embedding. The 2-year project aims to develop a unified perspective on various expansion concepts and techniques, and explore their connections to algorithmic coding theory and the approximability of discrete and continuous optimization problems. The research output will include new algorithms, coding theory advances, pseudorandom object designs, and combinatorial/geometric instances for inapproximability results, which will be disseminated through publications and educational materials.

Abstract

A broad variety of phenomena in computation can be viewed as different forms of ?expansion?, which ensure that local properties which can be observed by looking at small parts of an object, can be used to influence and understand global properties exhibited at a much larger scale. This is an important design requirement in several applications, such as (1) classical and quantum error-correction, where one wants errors to be easily detectable by local checks, (2) optimization problems, where one wants local choices to push the global solution towards optimality, and (3) geometric embeddings of high-dimensional data, where one wants to use local (low-dimensional) conditions to influence high-dimensional behavior. In the past few years, several new concepts and techniques have emerged to study expansion phenomena in different contexts. This project aims to study several different forms of expansion phenomena in a unified way, with an emphasis on applications in the areas of error-correcting codes and (approximate) optimization. This research is likely to lead to new connections between multiple areas where such phenomena are useful. The material generated as part of this research will also be disseminated through surveys and a series of expository videos. This project aims to obtain a unified view of the following different forms and applications of expansion phenomena: - classical notions of graph expansion and novel notions of high-dimensional expansion for hypergraphs, and their connections to recent advances in coding theory. - applications of classical expansion phenomena to quantum codes, as well as quantum extensions of classical expansion phenomena. - connections of high-dimensional expansion to the study and approximability of expansion phenomena in geometric spaces, and related problems about fine-grained graph expansion. The research directions pursued in this project aim to introduce new techniques in algorithmic coding theory and in the study of approximability of discrete and continuous optimization problems. The project considers several problems that have proved to be bottlenecks for current algorithmic and analytic techniques, explores new approaches arising from the study of expansion in a different context. The project aims to apply these ideas for the design of new error-correcting codes, and new algorithms for existing codes, towards the design of new pseudorandom objects, and also new families of combinatorial and geometric instances for proving inapproximability results. 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.