29. MFCS 2004: Prague, Czech Republic

Invited Lectures

• Jerzy Tiuryn, Ryszard Rudnicki, Damian Wójtowicz:
  A Case Study of Genome Evolution: From Continuous to Discrete Time Model. 1-24
  
• Magnús M. Halldórsson, Guy Kortsarz:
  Multicoloring: Problems and Techniques. 25-41
  
• Rodney G. Downey:
  Some Recent Progress in Algorithmic Randomness. 42-83
  
• Rolf Niedermeier:
  Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms. 84-103
  
• Uzi Vishkin:
  PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness. 104-105
  
• Matthew Brand, Sarah F. Frisken Gibson, Neal Lesh, Joe Marks, Daniel Nikovski, Ronald B. Perry, Jonathan S. Yedidia:
  Theory and Applied Computing: Observations and Anecdotes. 106-118
  
• Eduardo Bonelli, Adriana B. Compagnoni, Mariangiola Dezani-Ciancaglini, Pablo Garralda:
  Boxed Ambients with Communication Interfaces. 119-148
  
• Pascal Weil:
  Algebraic Recognizability of Languages. 149-175
  
• Emo Welzl:
  Geometric Optimization and Unique Sink Orientations of Cubes p. 176
  
• Elias Koutsoupias:
  Congestion Games and Coordination Mechanisms. 177-179
  

Graph Algorithms

• Hans L. Bodlaender, Fedor V. Fomin:
  Equitable Colorings of Bounded Treewidth Graphs. 180-190
  
• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos:
  The Bidimensional Theory of Bounded-Genus Graphs. 191-203
  
• Hajo Broersma, Fedor V. Fomin, Gerhard J. Woeginger:
  Parallel Knock-Out Schemes in Networks. 204-214
  
• Ioannis Caragiannis, Aleksei V. Fishkin, Christos Kaklamanis, Evi Papaioannou:
  Online Algorithms for Disk Graphs. 215-226
  

Approximations

• Hans-Joachim Böckenhauer, Dirk Bongartz:
  Protein Folding in the HP Model on Grid Lattices with Diagonals (Extended Abstract). 227-238
  
• Hubie Chen, Martin Pál:
  Optimization, Games, and Quantified Constraint Satisfaction. 239-250
  
• Andre Gronemeier:
  Approximating Boolean Functions by OBDDs. 251-262
  
• Miroslav Chlebík, Janka Chlebíková:
  On Approximation Hardness of the Minimum 2SAT-DELETION Problem. 263-273
  

Graphs and Complexity

• Daniel Král, Pavel Nejedlý:
  Group Coloring and List Group Coloring Are Pi₂P-Complete (Extended Abstract). 274-286
  
• Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski, Rahul Tripathi:
  Complexity Results in Graph Reconstruction. 287-297
  
• Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino:
  Generating Paths and Cuts in Multi-pole (Di)graphs. 298-309
  
• Zeev Nutov, Raphael Yuster:
  Packing Directed Cycles Efficiently. 310-321
  

Circuits

• Stephen D. Travers:
  The Complexity of Membership Problems for Circuits over Sets of Integers. 322-333
  
• Kristoffer Arnsfelt Hansen, Peter Bro Miltersen:
  Some Meet-in-the-Middle Circuit Lower Bounds. 334-345
  
• Alina Beygelzimer, Mitsunori Ogihara:
  The Enumerability of P Collapses P to NC. 346-355
  
• Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano:
  On NC¹ Boolean Circuit Composition of Non-interactive Perfect Zero-Knowledge. 356-367
  

General Complexity

• Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel:
  All Superlinear Inverse Schemes Are coNP-Hard. 368-379
  
• Gustav Nordh:
  The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups. 380-391
  
• Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner:
  Generation Problems. 392-403
  
• Sebastian Bab, Arfst Nickelsen:
  One Query Reducibilities Between Partial Information Classes. 404-415
  

Automata

• Vincent Bernardi, Bruno Durand, Enrico Formenti, Jarkko Kari:
  A New Dimension Sensitive Property for Cellular Automata. 416-426
  
• Guillaume Theyssier:
  Captive Cellular Automata. 427-438
  
• Victor Poupet:
  Simulating 3D Cellular Automata with 2D Cellular Automata. 439-450
  
• Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg:
  Graph Exploration by a Finite Automaton. 451-462
  

Parametrized and Kolmogorov Complexity

• Troy Lee, Andrei E. Romashchenko:
  On Polynomially Time Bounded Symmetry of Information. 463-475
  
• John M. Hitchcock, María López-Valdés, Elvira Mayordomo:
  Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. 476-487
  
• Henning Fernau, David W. Juedes:
  A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs. 488-499
  
• Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia:
  Polynomial Time Approximation Schemes and Parameterized Complexity. 500-512
  

Semantics

• Yann Loyer, Umberto Straccia:
  Epistemic Foundation of the Well-Founded Semantics over Bilattices. 513-524
  
• Ruggero Lanotte, Andrea Maggiolo-Schettini, Adriano Peron:
  Structural Model Checking for Communicating Hierarchical Machines. 525-536
  
• Olivier Ly:
  Compositional Verification: Decidability Issues Using Graph Substitutions. 537-549
  
• Rob J. van Glabbeek, Gordon D. Plotkin:
  Event Structures for Resolvable Conflict. 550-561
  

Scheduling

• Leah Epstein, Tamir Tassa:
  Optimal Preemptive Scheduling for General Target Functions. 562-573
  
• Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien:
  The Price of Anarchy for Polynomial Social Cost. 574-585
  
• Robert Elsässer, Ulf Lorenz, Thomas Sauerwald:
  Agent-Based Information Handling in Large Networks. 586-598
  
• Nadine Baumann, Ekkehard Köhler:
  Approximating Earliest Arrival Flows with Flow-Dependent Transit Times. 599-610
  

Algebraic Theory of Languages

• Marie-Pierre Béal, Francesca Fiorenzi, Dominique Perrin:
  A Hierarchy of Irreducible Sofic Shifts. 611-622
  
• Alexei Lisitsa, Igor Potapov:
  Membership and Reachability Problems for Row-Monomial Transformations. 623-634
  
• Libor Polák:
  On Pseudovarieties of Semiring Homomorphisms. 635-647
  
• Zoltán Ésik, Werner Kuich:
  An Algebraic Generalization of omega-Regular Languages. 648-659
  

Games

• Marcel Crâsmaru, Christian Glaßer, Kenneth W. Regan, Samik Sengupta:
  A Protocol for Serializing Unique Strategies. 660-672
  
• Henrik Björklund, Sven Sandberg, Sergei G. Vorobyov:
  A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games. 673-685
  
• Hugo Gimbert, Wieslaw Zielonka:
  When Can You Play Positionally? 686-697
  

Languages

• Alexander Okhotin:
  The Dual of Concatenation. 698-710
  
• Klaus Ambos-Spies, Edgar Busse:
  Computational Aspects of Disjunctive Sequences. 711-722
  
• Michael Domaratzki, Kai Salomaa:
  Decidability of Trajectory-Based Equations. 723-734
  

Geometry

• Therese C. Biedl, Masud Hasan, Alejandro López-Ortiz:
  Efficient View Point Selection for Silhouettes of Convex Polyhedra. 735-747
  
• Therese C. Biedl, Anna Lubiw, Michael J. Spriggs:
  Angles and Lengths in Reconfigurations of Polygons and Polyhedra. 748-759
  
• Benjamin Doerr, Nils Hebbinghaus, Sören Werth:
  Improved Bounds and Schemes for the Declustering Problem. 760-771
  
• Petr Hlinený:
  Crossing Number Is Hard for Cubic Graphs. 772-782
  

Languages and Complexity

• Victor L. Selivanov, Klaus W. Wagner:
  A Reducibility for the Dot-Depth Hierarchy. 783-793
  
• Klaus Wich:
  Sublogarithmic Ambiguity. 794-806
  
• Elena Petre:
  An Elementary Proof for the Non-parametrizability of the Equation xyz=zvx. 807-817
  
• Lucian Ilie, Pascal Ochem, Jeffrey Shallit:
  A Generalization of Repetition Threshold. 818-826
  

Quantum Computing

• Harumichi Nishimura, Tomoyuki Yamakami:
  An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation (Extended Abstract). 827-838
  
• Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, Raymond H. Putra:
  Universal Test for Quantum One-Way Permutations. 839-850
  
• Martin Beaudry, José M. Fernandez, Markus Holzer:
  A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract). 851-862
  

XML

• Yves Andre, Anne-Cécile Caron, Denis Debarbieux, Yves Roos, Sophie Tison:
  Extraction and Implication of Path Constraints. 863-875
  
• Béatrice Bouchou, Denio Duarte, Mirian Halfeld Ferrari Alves, Dominique Laurent, Martin A. Musicante:
  Schema Evolution for XML: A Consistency-Preserving Approach. 876-888
  
• Wim Martens, Frank Neven, Thomas Schwentick:
  Complexity of Decision Problems for Simple Regular Expressions. 889-900