Logical Approaches to Barriers in
Computing and Complexity

Tobias Gärtner. Representation Theorems for Analytic Machines
Mihai Prunescu. Triangular perplexity and a stairway to heaven
Tomer Kotek and Johann Makowsky. Definability of Combinatorial Functions and Their Linear Recurrence Relations
Saugata Basu and Thierry Zell. Polynomial hierarchy, Betti numbers and a  real analogue of Toda's theorem
Oleg Kudinov, Victor Selivanov and Anton Zhukov. Undecidability in Weihrauch Degrees
Eryk Kopczynski. Complexity of Problems of Commutative Grammars
Pawel Parys. Some results on complexity of mu-calculus evaluation in the black-box model
Saeed Salehi. Herbrand Consistency of ${\rm I\Delta_0}$ and ${\rm I\Delta_0}+\Omega_1$
Markus Lohrey, Dietrich Kuske and Jiamou Liu. The Isomorphism Problem On Classes of Automatic Structures
Victor Selivanov. Fine Hierarchies via Priestley Duality
Olaf Beyersdorff, Arne Meier, Sebastian Mueller, Michael Thomas and Heribert Vollmer. Proof Complexity of Propositional Default Logic
André Souto, Luis Antunes and Andreia Teixeira. A characterization of one-way functions based on time-bounded Komogorov complexity
Wesley Calvert and Russell Miller. Noncomputable Functions in the Blum-Shub-Smale Model
Satoru Kuroda. Complete Problems and Bounded Arithmetic for LOGCFL
Yijia Chen, Joerg Flum and Moritz Mueller. On Optimal Algorithms for SAT
Bruno COURCELLE and Irène DURAND. Tractable constructions of finite automata from monadic second-order formulas
Arno Pauly. Nash Equilibria and Fixed Points in the BSS-Model
Mathieu Hoyrup. Randomness and the ergodic decomposition
Barnaby Dawson. How definitions, equivalent for Turing machines, cease to be equivalent, when generalized to Ordinal Time Turing Machines
Tim Fischbach and Peter Koepke. An Analogue of the Church-Turing Thesis for Computable Ordinal Functions
Ilia Averbouch, Johann Makowsky and Peter Tittmann. A Case Study in Graph Polynomials: The Subgraph Component Polynomial
Sam Sanders and Andreas Weiermann. UNBOUNDED ARITHMETIC
Cameron Donnay Hill. Efficiently inverting the $L^2$-invariant through stability theory
Peter Koepke and Gregor Weckbecker. Ordinal Register Machines and Combinatorial Principles in the Constructible Universe
Katrin Tent and Martin Ziegler. Computable functions on the reals
Jan Johannsen. Lower bounds for width-restricted clause learning
Peter Koepke and Benjamin Seyfferth. A Characterization of Delta^1_2 Pointclasses Via Ordinal Machines
Artur Wdowiarski. On Trasitive Closure Operators in Finite Order Logic
Marcin Mostowski. Classification of the classes of finite models in Tarski' style
Margarita Korovina. Computability over  Positive Predicate Structures
Anuj Dawar and Bjarki Holm. Pebble Games for Rank Logics
Peter Scheiblechner. Comparison of Complexity over the Real vs. Complex Numbers
Zofia Adamowicz and Konrad Zdanowski. Lower bounds for the  provability of Herbrand consistency in weak arithmetics
Oleg Kudinov and Victor Selivanov. A Logic to capture P-time computability on Cantor space

websites: Arnold Beckmann 2010-01-06