CSR 2008: Moscow, Russia

Opening Lecture

• Avi Wigderson:
  Randomness - A Computational Complexity Perspective. 1-2
  

Invited Papers

• Eric Allender:
  Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds. 3-10
  
• Zurab Khasidashvili:
  On Formal Equivalence Verification of Hardware. 11-12
  
• Pavel Pudlák:
  Twelve Problems in Proof Complexity. 13-27
  
• Limsoon Wong:
  Manifestation and Exploitation of Invariants in Bioinformatics. 28
  
• Uri Zwick:
  Simple Stochastic Games, Mean Payoff Games, Parity Games. 29
  

Theory Track

• Sergei N. Artëmov, Elena Nogina:
  Topological Semantics of Justification Logic. 30-39
  
• Vikraman Arvind, Bireswar Das, Johannes Köbler:
  A Logspace Algorithm for Partial 2-Tree Canonization. 40-51
  
• Arnon Avron, Anna Zamansky:
  A Triple Correspondence in Canonical Calculi: Strong Cut-Elimination, Coherence, and Non-deterministic Semantics. 52-63
  
• Maxim A. Babenko, Tatiana A. Starikovskaya:
  Computing Longest Common Substrings Via Suffix Arrays. 64-75
  
• Nicolas Bedon, Alexis Bès, Olivier Carton, Chloe Rispal:
  Logic and Rational Languages of Words Indexed by Linear Orderings. 76-85
  
• Markus Bläser, Holger Dell, Johann A. Makowsky:
  Complexity of the Bollobás-Riordan Polynomial. 86-98
  
• Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino, Vladimir Oudalov:
  A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames. 99-109
  
• Didier Caucal, Stéphane Hassen:
  Synchronization of Grammars. 110-121
  
• Dmitriy Yu. Cherukhin:
  Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates. 122-133
  
• Ugo Dal Lago, Martin Hofmann:
  A Semantic Proof of Polytime Soundness of Light Affine Logic. 134-145
  
• Rostislav Deviatov:
  On Subword Complexity of Morphic Sequences. 146-157
  
• Jirí Fiala, Daniël Paulusma:
  Comparing Universal Covers in Polynomial Time. 158-167
  
• Melvin Fitting:
  S4LPand Local Realizability. 168-179
  
• Uffe Flarup, Laurent Lyaudet:
  On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract). 180-193
  
• Enrico Formenti, Jarkko Kari, Siamak Taati:
  The Most General Conservation Law for a Cellular Automaton. 194-203
  
• Sumit Ganguly:
  Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract). 204-215
  
• Johannes Köbler, Oleg Verbitsky:
  From Invariants to Canonization in Parallel. 216-227
  
• Roman Kuznets:
  Self-referentiality of Justified Knowledge. 228-239
  
• Nutan Limaye, Meena Mahajan, Antoine Meyer:
  On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata. 240-251
  
• Denis Osin, Vladimir Shpilrain:
  Public Key Encryption and Encryption Emulation Attacks. 252-260
  
• Vladimir V. Podolskii:
  A Uniform Lower Bound on Weights of Perceptrons. 261-272
  
• Yury Savateev:
  Lambek Grammars with One Division Are Decidable in Polynomial Time. 273-282
  
• Vladimir Shpilrain:
  Cryptanalysis of Stickel's Key Exchange Scheme. 283-288
  
• Arseny M. Shur:
  Combinatorial Complexity of Regular Languages. 289-301
  
• Vladimir V. V'yugin:
  On Sequences with Non-learnable Subsequences. 302-313
  
• Mingyu Xiao:
  Algorithms for Multiterminal Cuts. 314-325
  
• Marius Zimand:
  Two Sources Are Better Than One for Increasing the Kolmogorov Complexity of Infinite Sequences. 326-338
  

Applications and Technology Track

• Yevgeniy Bodyanskiy, Sergiy Popov, Taras Rybalchenko:
  Multilayer Neuro-fuzzy Network for Short Term Electric Load Forecasting. 339-348
  
• Laura Kovács:
  Invariant Generation for P-Solvable Loops with Assignments. 349-359
  
• Valery A. Nepomniaschy, Dmitri M. Beloglazov, Tatiana G. Churina, Mikhail Mashukov:
  Using Coloured Petri Nets to Model and Verify Telecommunications Systems. 360-371
  
• Victor Y. Pan, Dmitriy Ivolgin, Brian Murphy, Rhys Eric Rosholt, Yuqing Tang, Xiaodong Yan:
  Additive Preconditioning for Matrix Computations. 372-383
  
• Dusko Pavlovic:
  Network as a Computer: Ranking Paths to Find Flows. 384-397
  
• Maxime Rebout, Louis Féraud, Sergei Soloviev:
  A Unified Categorical Approach for Attributed Graph Rewriting. 398-409
  

Last update Tue May 22 04:50:18 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page