default search action
24th STACS 2007: Aachen, Germany
- Wolfgang Thomas, Pascal Weil:
STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings. Lecture Notes in Computer Science 4393, Springer 2007, ISBN 978-3-540-70917-6
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
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
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
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 1 and L. 477-488 - Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf:
The Polynomially Bounded Perfect Matching Problem Is in NC 2. 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
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
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
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 W. Harrow
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
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-13 19:14 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: