Duality in Circuit Complexity

• Applicant: Professor Dr. Klaus-Jörn Lange, since 2/2018
• Subject Area: Theoretical Computer Science
• Term: from 2018 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 395094066

One of the main concerns of complexity theory is the separation of classes. At the moment, the frontier of our knowledge concerning unconditional separation results, lies not between P and NP, but on the level of constant depth circuit classes. At this level separations have been shown in many isolated cases. The methods used to prove these results seem to be tailored to the specific cases. A general strategy is still missing. In the last few years, a new approach found its way into complexity theory. This raises the hope of providing a unified proof strategy. The approach, originating from Stone Duality, is capable of viewing complexity classes as topological objects and thus makes topological methods applicable. Since topology is a well established field of mathematics, it contributes a huge variety of such methods, notions and theorems. Stone Duality itself has previously been successfully applied in semantics: For instance by Abramsky for program logic and domain theory and by Esakia, providing a semantic for intuitionistic logic.The connection between topological objects and classes of languages was long known for the regular languages, together with an additional third algebraic component. This triple-play led to numerous characterisations and separations between subclasses of the regular languages.Regarding complexity classes, which are placed well outside the regular languages, there have been several different approaches to add an algebraic component, but none that integrates as well as the algebraic part in the regular case. Through investigating small instances of complexity classes, we have gained an idea for the design of a general method for separations, using an extended triple-play. Thus, the target of our research plan is to further invest into the solidification of that triple-play. We divide our tasks in the following way:The first task deals with subclasses of the visibly pushdown languages. These exhibit good-natured properties similar to those of the regular languages and thus pose an ideal subject to deepen our understanding of how the interplay of topology and algebra contributes to separations.In the second task, we examine constant depth circuit classes. In particular, we focus on the idea of a general method for separations, and extend it step-by-step to larger circuit classes.The third task deals with the mathematical background. The whole theory we wish to apply in the first two tasks deserves consideration on its own and our goal is to develop it into a sound framework.

• DFG Programme: Research Grants
• Ehemaliger Antragsteller: Privatdozent Dr. Andreas Krebs, until 2/2018