CAREER: The power and limitations of randomness

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

This project addresses three foundational questions in computer science: 1) Pseudo- randomness: When is randomness necessary for efficient computing? 2) Hardness of approximation: Which optimization problems are computationally hard? 3) Communication complexity: Which problems can be solved with little communication? At first glance, these questions appear quite disparate. However, there is a strong and deep connection between them through a hidden, more basic, theme: identifying structure in randomness. The central motif is that understanding what role randomness and pseudorandomness have in computation can be a guiding approach to questions in complexity theory, communication complexity, algorithm design, and more. The proposed research has potential for impacting several areas such as complexity theory, optimization, streaming algorithms, cryptography, and communication complexity; these areas in turn touch several core fields of computer science that impact all of science and even our daily lives. For example, pseudorandom generators are useful for saving space in streaming algorithms which in turn are important for processing massive amounts of data as is done in many modern applications. An integral part of the proposed research plan is to educate both undergraduate and graduate students. The PI intends to involve students at all levels in performing the research outlined in the proposal by actively advising PhD students as well as guiding undergraduate students on research projects. In more detail, this project aims to address the following three questions: 1) Pseudorandomness: Can randomness in algorithms be removed at the expense of a constant-factor increase in space? Recent work has led to the resolution of several longstanding challenges in this context and the new techniques can potentially lead to further progress. 2) Optimization hierarchies and hardness of approximation: Semi-definite programming (SDP) hierarchies are some of the most powerful techniques in algorithm design. Can a comprehensive theory to understand the power and limitations of the semi-definite hierarchies be developed for problems in approximation algorithms? This is a particularly pressing issue for problems where we do not have NP-hardness results as is the case for uniform sparsest cut, the unique games problem, or average-case problems like the planted clique problem. 3) Communication complexity: Can we characterize precisely the communication complexity of ?lifted problems??one of the most studied classes of functions in this context? Such a characterization will likely simplify the task of analyzing communication costs significantly. There is a rich history of interaction between the above pivotal areas and these connections should be investigated anew in light of the recent progress in the respective fields over the last few years.