Grant: Discovery Grants Program - Individual

Computation is one of the central concepts in our universe. From understanding how biological systems work to solving everyday industrial problems, computation permeates our life. Yet pinpointing the complexity of large classes of important computational problems is still elusive. We believe that many such problems are intrinsically computationally hard; even stronger assumptions underlie cryptography we rely on in daily life to secure our online presence. However, hardness of solving such problems in practice sometime defies this intuition. There is a plethora of heuristics that are routinely used to solve optimization problems which are proven to be at least as hard as some of the most popular problems in cryptography. What could be the reason for that? Are the instances of these problems that we come across in industry somehow easier than the worst case scenario that complexity theory considers? If this is the case, can we formalize what exactly makes these instances easy, and develop dedicated algorithms exploiting these properties? Alternatively, when we are trying to approach a problem that is believed to be hard in the worst-case, how can this problem be stated to make it as easy as possible for heuristics to exploit its hidden structure? And overall, what can be efficiently computed in our world, with all of its intrinsic structure influencing the practical hardness of problems we encounter? These questions are the main focus for the proposed research program. More specifically, we plan to analyse the types of instances of computationally hard problems that come from practical applications, and develop novel techniques for discovering and exploiting properties that make such types of instances easy. We will rely on a variety of techniques to approach this question, from logic to probabilistic analysis. This can help explain what makes existing heuristics so successful for tasks such as software verification and scheduling, and take much of the guesswork out of solving such optimization problems, to the benefit of many branches of our industry. As representation matters, we will study the ways of representing the problems which make such hidden structure most explicit and useful for the problem solvers, in particular Satisfiability solvers which are widely used in practice.The exploration of these questions goes beyond the specific heuristics and industrial applications. Can these methods be extended to explain how people solve problems, and how does the human brain make use of this hidden structure in the world around us? How do representations of the world we perceive affect the way we think? By understanding our world, we might be better able to understand ourselves.