Computer Science - Theory and Applications

Opening Lecture.- Randomness - A Computational Complexity Perspective.- Invited Papers.- Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds.- On Formal Equivalence Verification of Hardware.- Twelve Problems in Proof Complexity.- Manifestation and Exploitation of Invariants in Bioinformatics.- Simple Stochastic Games, Mean Payoff Games, Parity Games.- Theory Track.- Topological Semantics of Justification Logic.- A Logspace Algorithm for Partial 2-Tree Canonization.- A Triple Correspondence in Canonical Calculi: Strong Cut-Elimination, Coherence, and Non-deterministic Semantics.- Computing Longest Common Substrings Via Suffix Arrays.- Logic and Rational Languages of Words Indexed by Linear Orderings.- Complexity of the Bollobás-Riordan Polynomial.- A Complete Characterization of Nash-Solvability of Bimatrix Games in Terms of the Exclusion of Certain 2×2 Subgames.- Synchronization of Grammars.- Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates.- A Semantic Proof of Polytime Soundness of Light Affine Logic.- On Subword Complexity of Morphic Sequences.- Comparing Universal Covers in Polynomial Time.- S4LP and Local Realizability.- On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract).- The Most General Conservation Law for a Cellular Automaton.- Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract).- From Invariants to Canonization in Parallel.- Self-referentiality of Justified Knowledge.- On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata.- Public Key Encryption and Encryption Emulation Attacks.- A Uniform Lower Bound on Weights of Perceptrons.- Lambek Grammars with One Division Are Decidable in Polynomial Time.- Cryptanalysis of Stickel's Key Exchange Scheme.- Combinatorial Complexity of Regular Languages.- On Sequences with Non-learnable Subsequences.- Algorithms for Multiterminal Cuts.- Two Sources