Die Graphstruktur boolescher Funktionen

• Applicant: Professor Dr. Georg Schnitger
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 44274447

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.

• DFG Programme: Research Grants