24. STACS 2007: Aachen, Germany

Invited Talks

• Serge Abiteboul:
  A Calculus and Algebra for Distributed Data Management. 1-11
  
• Moshe Y. Vardi:
  The Büchi Complementation Saga. 12-22
  
• Dorothea Wagner, Thomas Willhalm:
  Speed-Up Techniques for Shortest-Path Computations. 23-36
  

Session 1A

• Bruno Courcelle, Andrew Twigg:
  Compact Forbidden-Set Routing. 37-48
  
• Manfred Kunde:
  A New Bound for Pure Greedy Hot Potato Routing. 49-60
  
• Ioannis Caragiannis:
  Wavelength Management in WDM Rings to Maximize the Number of Connections. 61-72
  

Session 1B

• Jean Berstel, Luc Boasson, Olivier Carton, Isabelle Fagnot:
  A First Investigation of Sturmian Trees. 73-84
  
• Sylvain Lombardy:
  On the Size of the Universal Automaton of a Regular Language. 85-96
  
• Francine Blanchet-Sadri, Joshua D. Gafni, Kevin H. Wilson:
  Correlations of Partial Words. 97-108
  

Session 2A

• Eldar Fischer, Orly Yahalom:
  Testing Convexity Properties of Tree Colorings. 109-120
  
• Amin Coja-Oghlan, Michael Krivelevich, Dan Vilenchik:
  Why Almost All k -Colorable Graphs Are Easy. 121-132
  

Session 2B

• Peter Bürgisser:
  On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds. 133-144
  
• Troy Lee:
  A New Rank Technique for Formula Size Lower Bounds. 145-156
  

Session 3A

• Ilan Newman, Yuri Rabinovich:
  Hard Metrics from Cayley Graphs of Abelian Groups. 157-162
  
• Robert Elsässer, Thomas Sauerwald:
  Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs. 163-174
  
• Adrian Dumitrescu, Csaba D. Tóth:
  Light Orthogonal Networks with Constant Geometric Dilation. 175-187
  

Session 3B

• Dietmar Berwanger:
  Admissibility in Infinite Games. 188-199
  
• Hugo Gimbert:
  Pure Stationary Optimal Strategies in Markov Decision Processes. 200-211
  
• Felix Brandt, Felix A. Fischer, Markus Holzer:
  Symmetries and the Complexity of Pure Nash Equilibrium. 212-223
  

Session 4A

• Daniel Král:
  Computing Representations of Matroids of Bounded Branch-Width. 224-235
  
• Pinar Heggernes, Karol Suchan, Ioan Todinca, Yngve Villanger:
  Characterizing Minimal Interval Completions. 236-247
  

Session 4B

• Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner:
  The Complexity of Unions of Disjoint Sets. 248-259
  
• Laurent Bienvenu:
  Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity. 260-271
  

Session 5A

• Stefan Funke, Sören Laue:
  Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets. 272-283
  
• Christian Hundt, Maciej Liskiewicz:
  On the Complexity of Affine Image Matching. 284-295
  

Session 5B

• Javier Esparza, Stefan Kiefer, Michael Luttenberger:
  On Fixed Point Equations over Commutative Semirings. 296-307
  
• Andrea Sattler-Klein:
  An Exponential Lower Bound for Prefix Gröbner Bases in Free Monoid Rings. 308-319
  

Session 6A

• Hans L. Bodlaender:
  A Cubic Kernel for Feedback Vertex Set. 320-331
  
• Peter Damaschke:
  The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting. 332-343
  
• Marc Tedder, Derek G. Corneil:
  An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs. 344-355
  

Session 6B

• Enrico Formenti, Petr Kurka:
  A Search Algorithm for the Maximal Attractor of a Cellular Automaton. 356-366
  
• Grégory Lafitte, Michael Weiss:
  Universal Tilings. 367-380
  
• Alberto Bertoni, Massimiliano Goldwurm, Violetta Lonati:
  On the Complexity of Unary Tiling-Recognizable Picture Languages. 381-392
  

Session 7A

• Hans-Ulrich Simon:
  A Characterization of Strong Learnability in the Statistical Query Model. 393-404
  
• Jan Poland:
  On the Consistency of Discrete Bayesian Learning. 405-416
  

Session 7B

• Pascal Koiran, Sylvain Perifel:
  VPSPACE and a Transfer Theorem over the Reals. 417-428
  
• Jin-yi Cai, Pinyan Lu:
  On Symmetric Signatures in Holographic Algorithms. 429-440
  

Session 8A

• Benjamin Doerr:
  Randomly Rounding Rationals with Cardinality Constraints and Derandomizations. 441-452
  
• Chien-Chung Huang:
  Cheating to Get Better Roommates in a Random Stable Matching. 453-464
  
• Costas Busch, Srikanta Tirthapura:
  A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window. 465-476
  

Session 8B

• Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao:
  Arithmetizing Classes Around NC ¹ and L. 477-488
  
• Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf:
  The Polynomially Bounded Perfect Matching Problem Is in NC ². 489-499
  
• Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien:
  Languages with Bounded Multiparty Communication Complexity. 500-511
  

Session 9A

• Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail:
  New Approximation Algorithms for Minimum Cycle Bases of Graphs. 512-523
  
• Iman Hajirasouliha, Hossein Jowhari, Ravi Kumar, Ravi Sundaram:
  On Completing Latin Squares. 524-535
  
• Artur Czumaj, Christian Sohler:
  Small Space Representations for Metric Min-Sum k -Clustering and Their Applications. 536-548
  

Session 9B

• Davide Bresolin, Angelo Montanari, Pietro Sala:
  An Optimal Tableau-Based Decision Algorithm for Propositional Neighborhood Logic. 549-560
  
• Thomas Schwentick, Volker Weber:
  Bounded-Variable Fragments of Hybrid Logics. 561-572
  
• Lutz Schröder, Dirk Pattinson:
  Rank-1 Modal Logics Are Coalgebraic. 573-585
  

Session 10A

• Gábor Ivanyos, Luc Sanselme, Miklos Santha:
  An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups. 586-597
  
• Andrew M. Childs, Aram Wettroth Harrow, Pawel Wocjan:
  Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem. 598-609
  
• Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond Harry Putra, Shigeru Yamashita:
  Quantum Network Coding. 610-621
  

Session 10B

• Mikolaj Bojanczyk, Piotr Hoffman:
  Reachability in Unions of Commutative Rewriting Systems Is Decidable. 622-633
  
• Sergiu Bursuc, Hubert Comon-Lundh, Stéphanie Delaune:
  Associative-Commutative Deducibility Constraints. 634-645
  
• Ralf Küsters, Tomasz Truderung:
  On the Automatic Analysis of Recursive Security Protocols with XOR. 646-657
  

Session 11A

• Iftah Gamzu, Danny Segev:
  Improved Online Algorithms for the Sorting Buffer Problem. 658-669
  
• Janina A. Brenner, Guido Schäfer:
  Cost Sharing Methods for Makespan and Completion Time Scheduling. 670-681
  

Session 11B

• Oleg Verbitsky:
  Planar Graphs: Logical Complexity and Parallel Isomorphism Tests. 682-693
  
• Henning Schnoor, Ilka Schnoor:
  Enumerating All Solutions for Constraint Satisfaction Problems. 694-705