Opening Lecture
Randomness - A Computational Complexity Perspective ............. 1
Avi Wigderson
Invited Papers
Cracks in the Defenses: Scouting Out Approaches on
Circuit Lower Bounds ............................................ 3
Eric Allender
On Formal Equivalence Verification of Hardware ................. 11
Zurab Khasidashvili
Twelve Problems in Proof Complexity ............................ 13
Pavel Pudlák
Manifestation and Exploitation of Invariants
in Bioinformatics .............................................. 28
Limsoon Wong
Simple Stochastic Games, Mean Payoff Games, Parity Games ....... 29
Uri Zwick
Theory Track
Topological Semantics of Justification Logic ................... 30
Sergei Artemov and Elena Nogina
A Logspace Algorithm for Partial 2-Tree Canonization ........... 40
Vikraman Arvind, Bireswar Das, and Johannes Köbler
A Triple Correspondence in Canonical Calculi: Strong
Cut-Elimination, Coherence, and Non-deterministic Semantics .... 52
Arnon Avron and Anna Zamansky
Computing Longest Common Substrings Via Suffix Arrays .......... 64
Maxim A. Babenko and Tatiana A. Starikovskaya
Logic and Rational Languages of Words Indexed
by Linear Orderings ............................................ 76
Nicolas Bedon, Alexis Bés, Olivier Carton,
and Chloé Rispal
Complexity of the Bollobás-Riordan Polynomial:
Exceptional Points and Uniform Reductions ...................... 86
Markus Bläser, Holger Dell, and Johann A. Makowsky
A Complete Characterization of Nash-Solvability of Bimatrix
Games in Terms of the Exclusion of Certain 2x2 Subgames ........ 99
Endre Bows, Khaled Elbassioni, Vladimir Gurvich,
Kazuhisa Makino, and Vladimir Oudalov
Synchronization of Grammars ................................... 110
Didier Caucal and Stéphane Hassen
Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with
Arbitrary Gates ............................................... 122
Dmitriy Yu. Cherukhin
A Semantic Proof of Polytime Soundness of
Light Affine Logic ............................................ 134
Ugo Dal Lago and Martin Hofmann
On Subword Complexity of Morphic Sequences .................... 146
Rostislav Deviatov
Comparing Universal Covers in Polynomial Time ................. 158
Jiřjí Fiala and Daniël Paulusma
S4LP and Local Realizability .................................. 168
Melvin Fitting
On the Expressive Power of Permanents and Perfect Matchings
of Matrices of Bounded Pathwidth/Cliquewidth
(Extended Abstract) ........................................... 180
Uffe Flarup and Laurent Lyaudet
The Most General Conservation Law for a Cellular Automaton .... 194
Enrico Formenti, Jarkko Kari, and Siamak Taati
Lower Bounds on Frequency Estimation of Data Streams
(Extended Abstract) ........................................... 204
Sumit Ganguly
From Invariants to Canonization in Parallel ................... 216
Johannes Кöbler and Oleg Verbitsky
Self-referentiality of Justified Knowledge .................... 228
Roman Kuznets
On the Complexity of Membership and Counting in
Height-Deterministic Pushdown Automata ........................ 240
Nutan Limaye, Meena Mahajan, and Antoine Meyer
Public Key Encryption and Encryption Emulation Attacks ........ 252
Denis Оsin and Vladimir Shpilrain
A Uniform Lower Bound on Weights of Perceptrons ............... 261
Vladimir V. Podolskii
Lambek Grammars with One Division Are Decidable in
Polynomial Time ............................................... 273
Yury Savateev
Cryptanalysis of Stickel's Key Exchange Scheme ................ 283
Vladimir Shpilrain
Combinatorial Complexity of Regular Languages ................. 289
Arseny M. Shur
On Sequences with Non-learnable Subsequences .................. 302
Vladimir V. V'yugin
Algorithms for Multiterminal Cuts ............................. 314
Mingyu Xiao
Two Sources Are Better Than One for Increasing the
Kolmogorov Complexity of Infinite Sequences ................... 326
Marius Zimand
Applications and Technology Track
Multilayer Neuro-fuzzy Network for Short Term Electric
Load Forecasting .............................................. 339
Yevgeniy Bodyanskiy, Sergiy Popov, and Taras Rybalchenko
Invariant Generation for P-Solvable Loops with Assignments .... 349
Laura Kovács
Using Coloured Petri Nets to Model and Verify
Telecommunications Systems .................................... 360
Valery Nepomniaschy, Dmitry Beloglazov, Tatiana Churina,
and Mikhail Mashukov
Additive Preconditioning for Matrix Computations .............. 372
Victor Y. Pan, Dmitriy Ivolgin, Brian Murphy, Rhys Eric
Rosholt, Yuqing Tang, and Xiaodong Yan
Network as a Computer: Ranking Paths to Find Flows ............ 384
Dusko Pavlovic
A Unified Categorical Approach for Attributed Graph
Rewriting ..................................................... 398
Maxime Rebout, Louis Féraud, and Sergei Soloviev
Author Index .................................................. 411
|
