The grant will support Meka’s research into the structure of randomness. Specifically, he will conduct research in three areas:
* Pseudorandomness: Looking at when randomness is necessary for efficient computing, versus when not-quite perfect randomness may suffice. Pseudorandomness is central to complexity theory, a major area in computer science that organizes problems by how difficult they are, and how they connect to each other. This research will look at pseudorandomness and its applications in many areas, including potentially saving space in algorithms for the processing of big data.
* Optimization hierarchies and hardness of approximation: Identifying which algorithmic problems are hard to solve, even approximately, as well as when optimization techniques – —the most powerful algorithm design methods currently available – can succeed in solving such problems.
* Communication complexity: Which problems can be solved with little communication between two entities, rather than a lot.
The five-year research grant, with a projected total amount of $500,000, includes funds for educating graduate and undergraduate students. Meka joined UCLA in 2014. He was previously a researcher with Microsoft Research. Meka was also a post-doctoral scholar at the Institute for Advanced Study, in Princeton, N.J., and at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers University. He received his Ph.D. in computer science from the University of Texas at Austin.