Die Graphstruktur boolescher Funktionen

点击翻译按钮获取中文摘要

Eine zentrale Fragestellung der Theoretischen Informatik ist die Frage nach unteren Schranken für den zur Berechnung konkreter Funktionen erforderlichen Ressourcenaufwand. Im Rahmen des Projektes soll eine systematische Untersuchung des Konzepts der Graphenkomplexität initiiert werden. Dieses Konzept erlaubt die Anwendung mächtiger Methoden der Algebra, der Kombinatorik und der Kommunikationskomplexität auf zentrale offene Fragen der Schaltkreiskomplexität. Insbesondere soll die Anwendbarkeit dieser Methoden für die Ableitung unterer Schranken für boolesche Formeln und Schaltkreise beschränkter Tiefe untersucht werden.