The goal of this research project is to develop new super-efficient, reliable, and robust algorithms solving modern challenges that arise in mastering complex data. For example, to successfully employ technological innovations such as autonomous vehicles it is necessary to synergistically and quickly operate with data that may be high-dimensional, distributed, erroneous, or even incomplete. This research project will advance the state of the art in computing with such diverse data by developing new theoretical foundations for problems that lie at the heart of communication-efficient distributed computation, coding and information theory, and machine learning. The project will also involve graduate and undergraduate student research and mentoring, and the results will achieve wide dissemination though workshops, conferences, online venues, and as teaching material.
The project will focus on four specific goals. The first one consists in abstracting global and local models that capture real-world data pertinent to distributed computation, learning and testing, and error-correction. The second goal is to design efficient algorithms and demonstrate limiting lower bounds in these models. The third goal is to illuminate the interplay between structure and fast computation, especially in the models mentioned above. Finally, the project aims to develop novel analysis techniques that are both data-specific, as well as unifying. These goals will likely be achieved by bridging insights from diverse areas of mathematics and computer science, including learning and coding theory, sublinear algorithms, cryptography, geometry, statistics and optimizations.
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.
