Moritz Müller FWF

FWF Project P 28699

Complexity theory in feasible mathematics




The project is hosted at Vienna universities Kurt Gödel Research Center for Mathematical Logic (KGRC) directed by Sy David Friedman.

General information about the project can be found here.


Team at the KGRC



Moritz Müller is funded as the project leader.

Jan Pich holds a funded postdoctoral position.

Jan Bydzovsky is working on a master thesis on a topic related to the project.


International collaborators



Albert Atserias at Universitat Polytecnica de Catalunya, Barcelona, Spain.

Yijia Chen at Fudan University, Shanghai, China.

Jan Krajicek at Charles University, Prague, Czech Republic.


Visitors




Igor Oliveira visits the KRGC from 2017-01-16 to 2017-01-21.

Michal Garlik visits the KRGC from 2017-01-23 to 2017-01-27 and gives a talk.

Yijia Chen visits the KRGC from 2017-08-12 to 2017-08-19 and gives a talk.


Talks




Cobham recursive set functions   By M. Müller, Barcelona Set Theory Seminar, Universitat de Barcelona, 2017-03-16.

Gentzen and Frege systems for QBF   By J. Pich, Computational Logic Day, KGRC, Vienna, 2017-01-13.

Complexity theory in feasible mathematics.   By J. Pich, KGRC Forschungsseminar, Vienna, 2016-10-03.


Publications




Pseudo proof systems and hard instances of SAT.   By J. Maly and M. Müller. Submitted March 2017.

The parameterized space complexity of model-checking bounded variable first-order logic.   By Y. Chen, M. Elberfeld and M. Müller. Submitted March 2017.

Reasons for hardness in QBF.   By O. Beyersdorff, L. Hinde and J. Pich. Submitted March 2017.

Subset-bounded recursion and a circuit model for Cobham recursive set functions.  By A. Beckmann, S. Buss, S.-D. Friedman, M. Müller, N. Thapen. Submitted December 2016.