Table of Contents
Avoiding Simplicity Is Complex Eric Allender 1
Higher-Order Containers Thorsten Altenkirch Paul Levy Sam Staton 11
On the Completeness of Quantum Computation Models Pablo Arrighi Gilles Dowek 21
The Ordinal of Skolem + Tetration Is τ0 Mathias Barra Philipp Gerhardy 31
Proofs, Programs, Processes Ulrich Berger Monika Seisenberger 39
Ergodic-Type Characterizations of Algorithmic Randomness Laurent Bienvenu Adam Day Ilya Mezhirov Alexander Shen 49
How Powerful Are Integer-Valued Martingales? Laurent Bienvenu Frank Stephan Jason Teutsch 59
A Faster Algorithm for Finding Minimum Tucker Submatrices Guillaume Blin Romeo Rizzi Stéphane Vialette 69
Processes in Space Luca Cardelli Philippa Gardner 78
Computability of Countable Subshifts Douglas Cenzer Ali Dashti Ferit Toska Sebastian Wyman 88
The Limits of Tractability in Resolution-Based Propositional Proof Systems Stefan Dantchev Barnaby Martin 98
Haskell before Haskell: Curry's Contribution to Programming (1946-1950) Liesbeth De Mol Maarten Bullynck Martin Carlé 108
A Miniaturisation of Ramsey's Theorem Michiel De Smet Andreas Weiermann 118
Graph Structures and Algorithms for Query-Log Analysis Debora Donato 126
On the Complexity of Local Search for Weighted Standard Set Problems Dominic Dumrauf Tim Süβ 132
Computational Interpretations of Analysis via Products of Selection Functions Martín Escardó Paulo Oliva 141
The Peirce Translation and the Double Negation Shift Martín Escardó Paulo Oliva 151
Counting the Changes of Random Δ02 Sets Santiago Figueira Denis Hirschfeldt Joseph S. Miller Keng Meng Ng André Nies 162
Boole: From Calculating Numbers to Calculating Thoughts Michèle Friend 172
Approximability and Hardness in Multi-objective Optimization Christian Glaβer Christian Reitwieβner Heinz Schmitz Maximilian Witek 180
Pw Is Not a Heyting Algebra Kojiro Higuchi 190
Lower Bounds for Reducibility to the Kolmogorov Random Strings John M. Hitchcock 195
Spatial Models for Virtual Networks Jeannette Janssen 201
DNA Rearrangements through Spatial Graphs Nataša Jonoska Masahico Saito 211
On Index Sets of Some Properties of Computable Algebras Bakhadyr Khoussainov Andrey Morozov 219
The Strength of the Besicovitch-Davies Theorem Bjørn Kjos-Hanssen Jan Reimann 229
Circuit Complexity and Multiplicative Complexity of Boolean Functions Arist Kojevnikov Alexander S. Kulikov 239
Definability in the Subword Order Oleg V. Kudinov Victor L. Selivanov Lyudmila V. Yartseva 246
Undecidability in Weihrauch Degrees Oleg V. Kudinov Victor L. Selivanov Anton V. Zhukov 256
Degrees with Almost Universal Cupping Property Jiang Liu Guohua Wu 266
Incomputability in Physics Giuseppe Longo 276
Approximate Self-assembly of the Sierpinski Triangle Jack H. Lutz Brad Shutters 286
Hairpin Lenthening Florin Manea Carlos Martín-Vide Victor Mitrana 296
Infinities in Quantum Field Theory and in Classical Computing: Renormalization Program Yuri I. Manin 307
Computational Complexity Aspects in Membrane Computing Giancarlo Mauri Alberto Leporati Antonio E. Porreca Claudio Zandron 317
Computable Ordered Abelian Groups and Fields Alexander G. Melnikov 321
Focusing in Asynchronous Games Samuel Mimram 331
A Note on the Least Informative Model of a Theory Jeff B. Paris Soroush R. Rad 342
Three Roots for Leibniz's Contribution to the Computational Conception of Reason Olga Pombo 352
Development of a Bacteria Computer: From in silico Finite Automata to in vitro and in vivo Yasubumi Sakakibara 362
The Complexity of Explicit Constructions Rahul Santhanam 372
Kolmogorov Complexity Cores André Souto 376
Every δ02-Set Is Natural, Up to Turing Equivalence Dieter Spreen 386
Computable Fields and Weak Truth-Table Reducibility Rebecca M. Steiner 394
What Is the Problem with Proof Nets for Classical Logic? Lutz Straβburger 406
Quasi-linear Dialectica Extraction Trifon Trifonov 417
Computing with Concepts, Computing with Numbers: Llull, Leibniz, and Boole Sara L. Uckelman 427
Inference Concerning Physical Systems David H. Wolpert 438
Author Index 449
