CSR 2009: Novosibirsk, Russia

Invited Papers

• Pedro Cabalar, Sergei P. Odintsov, David Pearce:
  Well-Founded and Partial Stable Semantics Logical Aspects. 1-11
  
• Wolfgang Thomas:
  The Reachability Problem over Infinite Graphs. 12-18
  
• Nikolay K. Vereshchagin:
  Kolmogorov Complexity and Model Selection. 19-24
  
• Hongseok Yang:
  Automatic Verification of Heap-Manipulating Programs Using Separation Logic. 25
  

Accepted Papers

• Arnon Avron, Agata Ciabattoni, Anna Zamansky:
  Canonical Calculi: Invertibility, Axiom Expansion and (Non)-determinism. 26-37
  
• Philippe Baptiste, Jacques Carlier, Alexander Kononov, Maurice Queyranne, Sergey Sevastyanov, Maxim Sviridenko:
  Integrality Property in Preemptive Parallel Machine Scheduling. 38-46
  
• Olaf Beyersdorff, Zenon Sadowski:
  Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes. 47-58
  
• Chris Calabro, Ramamohan Paturi:
  k-SAT Is No Harder Than Decision-Unique-k-SAT. 59-70
  
• Christian Choffrut, Juhani Karhumäki:
  Unique Decipherability in the Monoid of Languages: An Application of Rational Relations. 71-79
  
• Yi Deng, Giovanni Di Crescenzo, Dongdai Lin, Dengguo Feng:
  Concurrently Non-malleable Black-Box Zero Knowledge in the Bare Public-Key Model. 80-91
  
• Tommy Färnqvist, Peter Jonsson, Johan Thapper:
  Approximability Distance in the Space of H-Colourability Problems. 92-104
  
• Andreas Goerdt:
  On Random Ordering Constraints. 105-116
  
• Kristoffer Arnsfelt Hansen:
  Depth Reduction for Circuits with a Single Layer of Modular Counting Gates. 117-128
  
• Edward A. Hirsch, Sergey I. Nikolenko:
  A Feebly Secure Trapdoor Function. 129-142
  
• Pim van 't Hof, Daniël Paulusma, Gerhard J. Woeginger:
  Partitioning Graphs into Connected Parts. 143-154
  
• Dmitry Itsykson:
  Structural Complexity of AvgBPP. 155-166
  
• Maurice J. Jansen:
  Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials. 167-178
  
• Maurice J. Jansen, B. V. Raghavendra Rao:
  Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity. 179-190
  
• Artur Jez, Alexander Okhotin:
  One-Nonterminal Conjunctive Grammars over a Unary Alphabet. 191-202
  
• Galina Jirásková:
  Concatenation of Regular Languages and Descriptional Complexity. 203-214
  
• Peter Jonsson, Johan Thapper:
  Approximability of the Maximum Solution Problem for Certain Families of Algebras. 215-226
  
• Alexander Kononov, Sergey Sevastyanov, Maxim Sviridenko:
  Complete Complexity Classification of Short Shop Scheduling. 227-236
  
• Niko Haubold, Markus Lohrey:
  Compressed Word Problems in HNN-Extensions and Amalgamated Products. 237-249
  
• Daniil Musatov, Andrei E. Romashchenko, Alexander Shen:
  Variations on Muchnik's Conditional Complexity Theorem. 250-262
  
• Ely Porat:
  An Optimal Bloom Filter Replacement Based on Matrix Solving. 263-273
  
• Yuri Pritykin, Julya Ulyashkina:
  Aperiodicity Measure for Infinite Sequences. 274-285
  
• B. V. Raghavendra Rao, Jayalal M. N. Sarma:
  On the Complexity of Matroid Isomorphism Problems. 286-298
  
• Dogan Kesdogan, Daniel Mölle, Stefan Richter, Peter Rossmanith:
  Breaking Anonymity by Learning a Unique Minimum Hitting Set. 299-309
  
• Neeldhara Misra, Venkatesh Raman, Saket Saurabh, Somnath Sikdar:
  The Budgeted Unique Coverage Problem and Color-Coding. 310-321
  
• Mark A. Hillebrand, Sergey Tverdyshev:
  Formal Verification of Gate-Level Computer Systems. 322-333
  
• Mikhail N. Vyalyi:
  On Models of a Nondeterministic Computation. 334-345
  
• Magnus Wahlström:
  New Plain-Exponential Time Classes for Graph Homomorphism. 346-355
  
• Abuzer Yakaryilmaz, A. C. Cem Say:
  Languages Recognized with Unbounded Error by Quantum Finite Automata. 356-367