Grant: Discovery Grants Program - Individual

Given how central computation is to our lives, understanding computation is one of the most fundamental problems in modern-day science. Yet, some of the most basic questions about computation are still shrouded in mystery. For example, we still do not know whether being able to efficiently verify solutions can give us faster algorithms than exhaustive search: this is the famous "P vs NP" problem, designated by the Clay Mathematical institute in Oxford as one of the seven "millenium problems" with a million-dollar prize for a solution. We are surrounded by computational devices of various shapes and architectures, from computers and phones to smart thermostats, yet many of their computational abilities and limitations remain a mystery. To understand them, we design and study models of computations intended to capture their power and structure, from classical and randomized algorithms to logic, arithmetic and quantum circuits, to a variety of neural networks. Yet the many fundamental questions about these computational models remain unresolved, particularly for powerful enough models. Are there problems solved faster by quantum or randomized algorithms than by classical ones? How much does extra depth translate into more power for circuits and networks? And how can we create such objects, what does it take to obtain circuits or neural nets which compute (or at least approximate) a given function -- and how hard is it, to start with, to ascertain whether there exists such a circuit of a reasonable size? Existence of such circuits gives us tools for for solving practical problems, while proofs that they do not exist are crucial for other applications, most prominently cryptography. And, most intriguingly, proofs of hardness give us algorithms, and vice versa. In the proposed line of research, we plan to focus on the connections among these questions, leveraging the rich landscape of methods and techniques of Computational Complexity theory. In particular, we will study interrelations and connections among meta-algorithms and meta-complexity problems: that is, algorithms that operate on computational models themselves, and problems about determining the complexity of such tasks. This approach has already given us new ways of designing learning algorithms and prove lower bounds, and we are looking forward to fully exploring its potential.