Executive Summary of Dagstuhl-Seminar Circuits, Logic, and Games

Circuits, Logic, and Games

计算机科学;物理学;数学

Benjamin Rossman ; Thomas Schwentick ; Denis Thérien ; Heribert Vollmer

Others  :  http://drops.dagstuhl.de/opus/volltexte/2010/2527/pdf/10061.executive_summary.2527.pdf
PID  :  44031

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

Starting with the seminal paper by Furst, Saxe and Sipser, the last two decades of the previous century saw an immense interest in the computational model of Boolean circuits. Emerging powerful lower bound techniques promised progress towards solutions of major open problems in computational complexity theory. Within a very short time, further progress was made in papers by Fagin et al., Gurevich and Lewis, Håstad, Razborov, Smolensky, and Yao, to mention only a few. The just mentioned result by Furst et al. was obtained independently by Ajtai making use of modeltheoretic arguments, and many further lower bounds in complexity have been obtained afterwards making use of inexpressibility results in logic, very often making use of model-theoretic games. After a decade of active research in this direction things slowed down considerably.[First Paragraph]