News and Activities

2018 Alonzo Church Award for Outstanding Contributions to Logic and Computation

The 2018 Alonzo Church Award for Outstanding Contributions to Logic and Computation is given jointly to Tomas Feder and Moshe Y. Vardi for fundamental contributions to the computational complexity of constraint-satisfaction problems. Their contributions appeared in two papers:

  1. Tomas Feder, Moshe Y. Vardi: Monotone Monadic SNP and Constraint Satisfaction. STOC 1993, 612-622.
  2. Tomas Feder, Moshe Y. Vardi: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM J. Comput. 28(1), 57–104 (1998).

CONTRIBUTION SUMMARY: The Feder-Vardi project aimed at finding a large subclass of NP that exhibits a dichotomy (all problems are either in PTIME or NP-complete). The approach is to find this subclass via syntactic prescriptions. The paper identified a class of problems specified by “monotone monadic SNP without inequality”, which may exhibit this dichotomy. Feder and Vardi justified placing all three restrictions by showing, using Lad- ner’s theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. They then explored the structure of this class. They show that all problems in this class reduce to the seemingly simpler class CSP – Constraint Satisfaction Problems. They divided CSP into subclasses and tried to unify the collection of all known polytime algorithms for CSP problems and extract properties that make CSP problems NP-hard. They conjectured that the class CSP (and therefore, also MMSNP) also satisfy the dichotomy property. This became known as the Feder-Vardi Dichotomy Conjecture. The Dichotomy Conjecture stimulated an exten- sive research program, which culminated in 2017 in two independent proofs, by A. Bulatov and by D. Zhuk, of its correctness.


Gold Medal posthumously awarded to Petr Hájek

On June 27 2017 (in the framework of the conference in the series Topology, Algebra and Categories in Logic, TACL 2017) the Kurt Gödel Society has presented the gold medal posthumously to the son and the daughter of Professor Petr Hájek, which was awarded for his eminent contribution to the field of logic and to the development of the Kurt Gödel Society, whose president Professor Petr Hájek has been for many years.


Vienna Tbilisi Summer School in Logic and Language 2017

Also this year, the KGS organizes a summer school taking place in Tbilisi, Georgia. In September 2017 the Thirteenth Vienna Tbilisi Summer School in Logic and Language will bring courses to various topics to students. Please visit the web site of the summer school for more information: https://www.logic.at/tbilisi17/.


Call for Applications

Applications are being invited for outstanding early-career scientists (2-8 years post PhD), interested in establishing their first independent research group in an interdisciplinary field, connecting Logic with Mathematics and Computer Science. In this context, the Logic and Theory group at TU Wien is looking for candidates working on the analysis on mathematical proofs.

We are seeking for outstanding candidates, who are interested to submit an application to the open call for young investigators of the Vienna Science and Technology Fund (WWTF): https://www.wwtf.at/upload/VRG17_web.pdf.

In the case of a successful application, the research group will be funded for 6-8 years, with up to 1.6 million EUR by the WWTF, supplemented by an additional contribution from the University. After a successful interim evaluation, TU Wien will offer a tenure-track position to the group leader.

Requirements: Applicants should have an excellent track record demonstrating the innovative application of mathematical methods in Theoretical Computer Science. Application procedure: For a first step, informal inquiries, including a short CV with publication list, list of research projects and potential topics for a WWTF grant application should be sent to Agata Ciabattoni agata@logic.at as soon as possible but no later than June 28, 2017.

Female applicants are explicitly encouraged to apply!

Vienna, May 15 2017


First International Summer School for Proof Theory in First-Order Logic in Funchal, Madeira, 2017

The KGS organizes the first International Summer School for Proof Theory in First-Order Logic in Madeira. The summer school will take place in Funchal from 21.08.2017 to 26.08.2017 and will bring courses to various topics to students. Please visit the web site of the summer school for more information: https://kgs.logic.at/madeira/


Proof Theory Summer School in Funchal, Madeira

The KGS organizes a summer school taking place in Funchal, Madeira. In August 2016 the Proof Theory Summer School in Madeira will bring courses to various topics in proof theory to students. Please visit the official website of the summer school for more information.


Vienna Tbilisi Summer School in Logic and Language 2016

Also this year, the KGS organizes a summer school taking place in Tbilisi, Georgia. In September 2015 the Eleventh Vienna Tbilisi Summer School in Logic and Language will bring courses to various topics to students. Please visit the web site of the summer school for more information: www.logic.at/tbilisi16/.


Dana Scott eleceted President of KGS

On June 29, 2015 Professor Dana Scott was elected President of the KGS. Photos from the ceremony and his talk Can Modalities Save Naive Set Theory? given at VCLA can be viewed at Photos (photos copyright B Afshari).


Eleventh Vienna Tbilisi Summer School in Logic and Language

Also this year, the KGS organizes a summer school taking place in Tbilisi, Georgia. In September 2015 the Eleventh Vienna Tbilisi Summer School in Logic and Language will bring courses to various topics to students. Please visit the web site of the summer school for more information: www.logic.at/tbilisi15/.


Workshop on Proofs and Processes II

http://www.jaist.ac.jp/~preining/wpp2/

The Workshop on Proofs as Processes II is a continuation of last years Workshop on Proofs as Processes. It will be held with the support of the Kurt Gödel Society, and a Royal Society Daiwa Anglo-Japanese Foundation International Exchanges Award in Noto, Ishikawa, from 13‐15 July, 2015.

After the successful development of a Hypernatural deduction system (LICS 2015 etc) we will continue our long-term project on extending the classical Curry-Howard correspondence to hypersequent calculus and parallel processes. It will bring together scientists working on the various related fields who are interested in collaborating in the project.