Intellectual merit:

Theoretical computer science concerns itsefl with the computational resources, such as number of operations or bits of memory, needed for a computer to solve a computational problem.  Traditionally, this is divided into two sub-fields: algorithm design, seeking new ways of  solving problems quickly or with few resources; and computational complexity, characterizing those problems that are ``hard'' in that they require large amount of resources.  Our research utilizes pardoxical connections between these two areas to make progress on both.  We utilize reasons why some problems are difficult to design new algorithms that solve other problems more efficiently, and utilize new algorithms for some problems to show others are difficult. 

As an example, we designed a new learning algorithm that, from random labelled examples of a function of a certain type (that can be expressed witha small number of  layers of and, or and parity gates) , deduces how to compute the function.  This solved a problem that had been open for twenty-five years, and won the Best Paper Award in CCC 16.  This algorithm is completely different from any in the previous learning theory literature, because it combines two ideas from complexity theory:  the circuit size lower bound of Smolensky and Razborov and the way to remove randomness from algorithms of Nisan and Wigderson. 

We also bridge another divide, showing connections between the difficulty of ``very hard'' problems that require exponential time and those that are relatively easy, but where algorithm designers are stil working to make further improvements. 

For example, the stable marriage problem was introduced by Gale (and was cited in his Nobel Prize for Economics as a major contribution).  The problem is to match partners in  a way that each prefers to be together than to split up.  It is widely used for applications such as pairing medical residents with hospitals.  It has a reasonably efficient algorithm, but if the input is described succinctly, one could hope to improve it.  We examined this problem from a complexity-theoretic viewpoint.  We obtained both new algorithms for many special cases of stable marriage, and hardness results, showing that improving algorithms for other cases would violate a widely-held conjecture about the complexity of NP-complete problems.

We also made progress on understanding the complexity of hard problems, such as Satisfiability.  New algorithms for hard problems were designed, many using circuit lower bound arguments.  Somewhat paradoxically, satisfiability is both a known hard problem, and a problem where heuristic algorithms solve many typical instances.  We used proof complexity to characterize both the power and limitations of different heuristic methods; for example, we gave provable examples where the new clause learning technique is superior to any implementation of the more old-fashioned Davis-Putnam style algorithms.  We also showed the first examples where memory restrictions would cost a SAT-solver  a huge amount of time, even if the memory is  much larger  than the input formula.

Broader impact:

The divide between algorithm design and computational complexity was social as well as technical.  Since researchers in the two communities are not used to each other's ideas and approaches, and have mostly worked separately, technical results explaining the connections between the two areas do not automatically create collaborations between the fields.   With this in mind, we organized a special semester at the Simons Insitute in Berkeley to bring together the two groups of researchers.  This semester program was very successful, both in terms of the research that was performed during the semester (solving many open problems and launching many new directions), and  in creating collaborations between algorithm designer s and complexity theorists.  Moreover, many young researchers became involved and interested in this new approach.

We also looked for ways to use theoretical ideas to improve undergraduate education.  One way we did this is by directly involving undergraduates in our reseach, such as Cody Murray, now a Ph.D. student at MIT working with non-UCSD PI Wlliiams.  We also used algorithmic problems that came up in our research as example problems in undergraduate courses.  Finally, some of us were instrumental in creating programs to ease the transition into the computer science major for new  undergraduates with little computing experience.

Last Modified: 11/28/2017
Modified by: Ramamohan Paturi