Computer Science - Theory and Applications

- Invited Papers

- Well-Founded and Partial Stable Semantics Logical Aspects

- The Reachability Problem over Infinite Graphs

- Kolmogorov Complexity and Model Selection

- Automatic Verification of Heap-Manipulating Programs Using Separation Logic

- Accepted Papers

- Canonical Calculi: Invertibility, Axiom Expansion and (Non)-determinism

- Integrality Property in Preemptive Parallel Machine Scheduling

- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes

- k-SAT Is No Harder Than Decision-Unique-k-SAT

- Unique Decipherability in the Monoid of Languages: An Application of Rational Relations

- Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model

- Approximability Distance in the Space of H-Colourability Problems

- On Random Ordering Constraints

- Depth Reduction for Circuits with a Single Layer of Modular Counting Gates

- A Feebly Secure Trapdoor Function

- Partitioning Graphs into Connected Parts

- Structural Complexity of AvgBPP

- Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

- Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity

- One-Nonterminal Conjunctive Grammars over a Unary Alphabet

- Concatenation of Regular Languages and Descriptional Complexity

- Approximability of the Maximum Solution Problem for Certain Families of Algebras

- Complete Complexity Classification of Short Shop Scheduling

- Compressed Word Problems in HNN-Extensions and Amalgamated Products

- Variations on Muchnik's Conditional Complexity Theorem

- An Optimal Bloom Filter Replacement Based on Matrix Solving

- Aperiodicity Measure for Infinite Sequences

- On the Complexity of Matroid Isomorphism Problems

- Breaking Anonymity by Learning a Unique Minimum Hitting Set

- The Budgeted Unique Coverage Problem and Color-Coding

- Formal