The Principal Investigator (PI) plans to study problems arising in analysis, convex geometry and computer science using the methods of probability. For many problems of geometry and analysis, such as finding sections of a convex body with certain nice properties or extracting a small sample with a certain structure from a large set, the explicit constructions are unknown. In these cases random constructions turn out to be very effective. It is often possible to define a random section or sample and show that it has the desired property with high probability. This approach combined with advanced probabilistic tools, like measure concentration, led to major discoveries in convex geometry and functional analysis. The PI plans to study the combinatorial dimension of a set of functions. This is a new measure of complexity, which arises from questions in probability and computer science. The PI will also investigate the spectral properties of random matrices and apply the results of this research to construction of effective error-correcting codes.
This research will provide new connections between functional analysis, convex geometry and probability. An important part of this project is the application of probabilistic methods to concrete problems of computer science. The study of combinatorial dimension is likely to have practical applications in machine learning. The geometric approach to the signal recovery and error-correcting codes will lead to the construction of more efficient and stable algorithms.
