| Monday, August 22 |
| 9:00 |
Conference opening |
| 9:10 |
Invited lecture: Mai Gehrke Duality and recognition |
| 10:30 |
Coffee break |
| 11:00 |
Complexity and lower bounds |
Synthesis and verification |
|
E. Demenkov, A. Kulikov An Elementary Proof of a 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
O. Beyersdorff, S. Datta, M. Mahajan, G. Scharfenberger-Fabian, K. Sreenivasaiah, M. Thomas, H. Vollmer Verifying Proofs in Constant Depth
K. Uchizawa, E. Takimoto Lower Bounds for Linear Decision Trees via An Energy Complexity Argument |
B. Puchala, W. Fridman Distributed Synthesis for Regular and Contextfree Specifications
B. Bollig, A. Cyriac, P. Gastin, M. Zeitoun Temporal Logics for Concurrent Recursive Programs: Satisfiability and Model Checking
S. Bauer, U. Fahrenberg, L. Juhl, K. G. Larsen, A. Legay, C. Thrane Quantitative Refinement for Weighted Modal Transition Systems |
| 12:30 |
Lunch |
| 14:00 |
Invited lecture: Paul Wollan New Proofs in Graph Minors |
| 15:30 |
Coffee break |
| 16:00 |
Young Researchers Forum: Graphs and Algorithms |
|
K. Junosza-Szaniawski, J. Kratochvil, M. Liedloff, P. Rossmanith, P. Rzążewski Fast Exact Algorithm for L(2,1)-Labeling of Graphs
J. Arjona, A. Fernández Anta Exact Bisection Width of the Torus and Other Multidimensional Product Graphs
A. Nenca, J. Dybizbański Oriented chromatic number of grids |
| 16:45 |
Coffee break |
| 17:00 |
Young Researchers Forum: Algorithms I
|
|
O. Moriš Generalized Maneuvers in Route Planning SEQ
N. Nicolaou Seeking Fast Operations in MWMR Atomic Register Implementations
S. Köhler Fault-containing Self-stabilization
M. Pilipczuk The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem) |
| 18:00 |
Welcome reception at Kazimierzowski Palace |
|
| Tuesday, August 23 |
| 9:00 |
Invited lecture: Daniel Kirsten Some Variants of the Star Height Problem |
| 10:30 |
Coffee break |
| 11:00 |
Parametrized complexity |
Logic |
|
C. Paul, S. Thomassé, A. Perez Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and related problems
J. Wang, Y. Yang, J. Guo, J. Chen Linear Problem Kernels for Planar Graph Problems with Small Distance Property
M. Xiao, T. Kloks, S. Poon New Parameterized Algorithms for Edge Dominating Set |
E. Hemaspaandra, H. Schnoor A Universally Defined Undecidable Unimodal Logic
A. Facchini, B. Ten Cate Characterizing EF over Infinite Trees and Modal Logic on Transitive Graphs
M. Vanden Boom Weak Cost Monadic Logic Over Infinite Trees |
| 12:30 |
Lunch |
| 14:00 |
Math and physics |
Logic, automata, words |
|
P. Franek, S. Ratschan, P. Zgliczynski Satisfiability of Systems of Equations of Real Analytic Functions is Quasi-decidable
O. Bournez, D. Graça, A. Pouly Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains
K. Perrot, E. Rémila Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence |
D. Kuske, T. Weidner Size and computation of injective tree automatic presentations
M. Lohrey Compressed word problems for inverse monoids
M. Pilipczuk Problems parameterized by treewidth tractable in single exponential time: a logical approach |
| 15:30 |
Coffee break |
| 16:00 |
Young Researchers Forum: Automata and Languages I |
|
F. Mazowiecki Continuous reductions of regular languages
D. Quernheim Hyper-minimisation of weighted finite automata Aspects of non-deterministic finite automata minimisation
M. Bilkowski Strongly unambiguous regular languages of infinite trees |
| 16:45 |
Coffee break |
| 17:00 |
Young Researchers Forum: Logic and Games |
|
M. Skrzypczak Equational theories of profinite structures
W. Charatonik, P. Witkowski Complexity of Two-Variable Logics Extended with Monadic Datalog Programs
O. Skibski Steady Marginality: A Uniform Approach to Shapley Value for Games with Externalities
J. Ortega The Effects of Tie-Breaking Rules on Repeated Auctions with Discrete Bidding |
| 18:00 |
|
| Wednesday, August 24 |
| 9:00 |
Invited lecture: Prasad Raghavendra Generic techniques to round SDP relaxations |
| 10:30 |
Coffee break |
| 11:00 |
String algorithms |
Quantitative and quantum automata |
|
C. Boucher The Bounded Search Tree Algorithm for the Closest String Problem has Quadratic Smoothed Complexity
F. Manea, R. Mercas, C. Tiseanu Periodicity Algorithms for Partial Words
A. Krebs, N. Limaye, S. Srinivasan Streaming algorithms for recognizing nearly well-parenthesized expressions
|
A. Maletti and D. Quernheim Pushing for weighted tree automata
O. Sankur Untimed Language Preservation in Timed Systems
M. Golovkins, M. Kravtsev, V. Kravcevs Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages |
| 12:30 |
Lunch |
| 13:30 |
Young Researchers Forum: Algorithms II
|
|
P. Floderus Preventing Cactus Fire SEQ
P. Gawrychowski Optimal (fully) LZW-compressed pattern matching |
| 14:00 |
Coffee break |
| 14:15 |
Young Researchers Forum: Automata and Languages II |
|
G. Madejski Permutation languages D. Quernheim Hyper-minimisation of weighted finite automata
K. Moroz A dynamic parsing algorithm for pregroup grammars |
| 15:00 |
Social event |
|
| Thursday, August 25 |
| 9:00 |
Invited lecture: Jörg Flum Invariantization of listings |
| 10:30 |
Coffee break |
| 11:00 |
Graphs |
Automata |
|
A.-M. Kermarrec, C. Thraves Can everybody sit closer to their friends than their enemies?
P. Golovach, M. Kaminski, D. Paulusma Contracting a chordal graph to a split graph or a tree
M. Blaeser, R. Curticapean The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree |
P. Gawrychowski, A. Jeż, A. Maletti On minimising automata with errors
A. Okhotin, K. Salomaa State complexity of operations on input-driven pushdown automata
S. Böhm, S. Göller Language equivalence of deterministic real-time one-counter automata is NL-complete |
| 12:30 |
Lunch |
| 14:00 |
Invited lecture: Alexandr Andoni Nearest Neighbor Search in High-Dimensional Spaces |
| 15:30 |
Coffee break |
| 16:00 |
Social networks and k-anonymity |
VAS and data words |
|
R. Bredereck, A. Nichterlein, R. Niedermeier, G. Philip Pattern-Guided Data Anonymization and Clustering
R. Dondi, G. Mauri, I. Zoppis On the Complexity of the l-diversity Problem
J. Hosoda, J. Hromkovic, T. Izumi, H. Ono, M. Steinová, K. Wada On the Approximability of Minimum Topic Connected Overlay and Its Special Instances |
R. Bonnet The reachability problem for Vector Addition Systems with one zero-test
M. Blockelet, S. Schmitz Model Checking Coverability Graphs of Vector Addition Systems
T. Colcombet, C. Ley, G. Puppis On the use of guards for logics with data |
| 17:30 |
Break |
| 19:00 |
Conference dinner |
|
| Friday, August 26 |
| 9:00 |
Functions |
Games and automata |
|
A. Bogdanov, A. Kawachi, H. Tanaka Hard Functions for Low-degree Polynomials over Prime Fields
R. J. Lipton, K. Regan, A. Rudra Symmetric Functions Capture General Functions
V. Kolmogorov Submodularity on a tree: Unifying L♮-convex and bisubmodular functions |
J. Fearnley, O. Lachish Parity Games On Graphs With Medium Tree-width
K. Chatterjee, L. Doyen Energy and Mean-Payoff Parity Markov Decision Processes
L. Doyen, T. Massart, M. Shirmohammadi Infinite Synchronizing Words for Probabilistic Automata |
| 10:30 |
Coffee break |
| 11:00 |
Networks and distributed algorithms |
Algebra and types |
|
K. Rybarczyk, K. Krzywdziński Geometric Graphs with Randomly Deleted Edges - Connectivity and Routing Protocols
P. Berenbrink, R. Elsaesser, T. Friedetzky, L. Nagel, T. Sauerwald Faster Coupon Collecting via Replication with Applications in Gossiping
Y. Bachrach The Least-Core of Threshold Network Flow Games |
D. A. Cohen, P. Creed, P. G. Jeavons, S. Zivny An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
J. Chrząszcz, A. Schubert The role of polymorphism in the characterisation of complexity by soft types
P. Baldan, F. Gadducci, P. Sobocinski Adhesivity is not enough: Local Church-Rosser revisited
|
| 12:30 |
Lunch |
