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:
- Tomas Feder, Moshe Y. Vardi: Monotone Monadic SNP and Constraint Satisfaction. STOC 1993, 612-622.
- 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.
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 email@example.com as soon as possible but no later than June 28, 2017.
Female applicants are explicitly encouraged to apply!
Vienna, May 15 2017
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).
The ScienceWeek@Austria is dedicated to public relation work for science and research. All universities and other research/scientific institutes are invited to present their work, developments and interests in a way easy to grasp for the non-scientist.
In cooperation with the Institut Wiener Kreis we will organize a series of events in a viennese coffeehouse under the title Cafehaus-Wissenschaft - Der Wiener Kreis Logic, Medicine, Jurisprudence and Philosophy: four sciences which were prominent in Vienna at the beginning of the 20th century. We will present these four disciplines with interesting, funny, strange and famous results. There will be lectures to each of these sciences and two special courses are held on the incompleteness theorem of Gödel and on Kelsens jurisdiction.
For more informations please visit the ScienceWeek Homepage
In 2000 the KGS screened the movie "Kurt Gödel - ein mathematischer Mythos" by Werner De Pauli-Schimanovich and Peter Weibel in a Viennese cinema together with a introduction by Mr. Schimanovich and a long discussion after the screening.