EXCICO · Extremal Combinatorics and Circuit Complexity

Extremal Combinatorics and Circuit Complexity

Computation is a central aspect of our lives. Even when we are not consciously aware of it, we are often manipulating information to produce new information by applying a set of formal rules. Computation can be as simple as an arithmetic calculation that we perform in our head, or as complex as a simulation system which gives us reliable weather forecast. Intuition suggests that advances in hardware technologies should allow us to perform more and more complex tasks. Alas, we know already from the groundbreaking work of Alan Turing in 1937 that computation has inherent mathematical limits; regardless of what hardware is used, certain tasks are simply not possible, because there is no set of rules of information processing achieving them. Computational complexity theory is the systematic study of these limitations. Its main objective is to identify and classify computational problems with respect to their inherent logical hardness within given resources. After a few decades of development, this beautiful theory has established itself as a fundamental field of basic research, touching a wide spectrum of other areas. The basic objects of study in complexity theory are Boolean functions. Boolean circuits provide a natural model for computing Boolean functions. Circuits not only serve as a concrete theoretical model, but also they are implemented in practice and reside at the core of our every day computers. The most natural measure of complexity of a function is the size of a smallest circuit computing it. A classical counting argument due to Shannon shows that almost all Boolean functions require circuits of exponential size; there are simply a lot more functions than small circuits. Yet no explicit function is known which cannot be computed by circuits of even linear size. The quest for explicit circuit lower bounds is not just a technical curiosity, it seeks an answer to a profound question, what makes computational tasks hard? A convincing answer to this question resolves the most celebrated problem in complexity theory, the P vs. NP problem. One of the reasons for our failure in making decisive progress towards such problems is that we do not have sufficient understanding of the combinatorial structures arising from Boolean circuits. The proposed project continues the development of such understanding. More specifically, it identifies combinatorial objects which capture fundamental problems in complexity theory, and investigates their extremal properties. Extremal combinatorics is a dynamic branch of combinatorics which studies objects that satisfy various constraints. We thus give the title Extremal Combinatorics and Circuit Complexity (EXCICO). One of the earliest results in extremal combinatorics is the Turán theorem which gives a tight bound on the maximum possible number of edges in a graph with no complete subgraph of a given size. Problems of this type, i.e., bounds of the size of sets which avoid certain configurations, are henceforth called Turán-type. In EXCICO we are mainly concerned with this type of problems. Extremal combinatorics is a vibrant area of research and has a rigorous methodology, where an extensive set of sophisticated tools are systematically applied to almost all problems. The objective of this project is to adopt and develop such a methodology to attack central problems in circuit complexity.

Data: CORDIS, © European Union