AF: Small: Challenges in Communication Complexity and Pseudorandomness

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

The project addresses central questions within two closely related areas: communication complexity, and pseudorandomness. What is the minimal amount of communication needed to complete a computational task when the input is split between different parties? Such questions have profound applications both in theory and in practice, especially as communication is increasingly becoming the bottleneck in large-scale computation. A goal of the project is to prove meta-theorems and develop generic techniques that reduce understanding communication to much simpler 'decision-theoretic' problems. Randomness versus determinism in the universe is an ancient philosophical debate. In computing, however, randomness seems to be winning hands down with amazing applications in cryptography, e-commerce, data analytics, algorithm design, and networking. Which of these applications absolutely need randomness? Which of them can still be simulated if we do not have random bits or have access only to defective random bits as in data from radio-active decay? The project will study these fundamental questions when optimizing for memory as a resource: Can we simulate randomized algorithms deterministically with only a small overhead in memory? The investigator will develop and make freely available educational material on these cutting-edge research problems and guide undergraduate and graduate students on performing research on these topics. In more detail, the project aims to develop a comprehensive theory of 'lifting theorems' in communication, which reduce proving communication lower bounds to proving query-complexity lower bounds that are often simpler. The project will focus on the two central open problems in this area: lifting for constant-size gadgets, and lifting for semi-definite optimization. The investigator will also explore new applications and connections between multi-party communication complexity and leakage-resilience in cryptography and extractors. The project also seeks to design optimal pseudorandom generators for small-width branching programs, which would be a significant step toward understanding the trade-off between randomness and space. 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.