STACS 2004

Contenu

Invited Lectures.- Approximation Schemes for Metric Clustering Problems.- Positional Determinacy of Infinite Games.- Structural Complexity (I).- Individual Communication Complexity.- The Complexity of Satisfiability Problems over Finite Lattices.- Constant Width Planar Computation Characterizes ACC0.- Graph Algorithms (I).- A Simple and Fast Approach for Solving Problems on Planar Graphs.- Sum-Multicoloring on Paths.- Matching Algorithms Are Fast in Sparse Random Graphs.- Quantum Computations.- Algebraic Results on Quantum Automata.- Quantum Identification of Boolean Oracles.- Pattern Inference and Statistics.- Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models.- A Discontinuity in Pattern Inference.- Satisfiability - Constraint Satisfaction Problem.- Algorithms for SAT Based on Search in Hamming Balls.- Identifying Efficiently Solvable Cases of Max CSP.- The Complexity of Boolean Constraint Isomorphism.- Scheduling (I).- On Minimizing the Total Weighted Tardiness on a Single Machine.- Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs.- Optimal and Online Preemptive Scheduling on Uniformly Related Machines.- Algorithms.- Parallel Prefetching and Caching Is Hard.- Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem.- Approximation Algorithms for Minimizing Average Distortion.- Networks (I).- Digraphs Exploration with Little Memory.- Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks.- An Algorithmic View on OVSF Code Assignment.- Automata Theory and Words.- The Syntactic Graph of a Sofic Shift.- Periodicity and Unbordered Words.- Desert Automata and the Finite Substitution Problem.- Structural Complexity (II).- Satisfiability Problems Complete for Deterministic Logarithmic Space.- A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number.- The Minimal Logically-Defined NP-Complete Problem.- Path Algorithms.- Solving the 2-Disjoint Paths Problem in Nearly Linear Time.- Simpler Computation of Single-Source Shortest Paths in Linear Average Time.- Cryptography.- Lattices with Many Cycles Are Dense.- Automata-Based Analysis of Recursive Cryptographic Protocols.- Networks (II).- On Minimum Circular Arrangement.- Integral Symmetric 2-Commodity Flows.- Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks.- Logic and Formal Languages.- On the Expressiveness of Deterministic Transducers over Infinite Trees.- Definability and Regularity in Automatic Structures.- Active Context-Free Games.- Graphs Algorithms (II).- Worst Case Performance of an Approximation Algorithm for Asymmetric TSP.- On Visibility Representation of Plane Graphs.- Topology Matters: Smoothed Competitiveness of Metrical Task Systems.- Game Theory and Complexity.- A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees.- The Plurality Problem with Three Colors.- A Measured Collapse of the Modal ?-Calculus Alternation Hierarchy.- Networks (III).- An Information Theoretic Lower Bound for Broadcasting in Radio Networks.- A New Model for Selfish Routing.- Broadcast in the Rendezvous Model.- Structural Complexity (III).- Time-Space Tradeoff in Derandomizing Probabilistic Logspace.- What Can be Efficiently Reduced to the K-Random Strings?.- Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints between Regular Open Terms.- Scheduling (II).- Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines.- The Expected Competitive Ratio for Weighted Completion Time Scheduling.- Algorithmic Information.- Effective Strong Dimension in Algorithmic Information and Computational Complexity.- A Lower Bound on the Competitive Ratio of Truthful Auctions.- Errata to STACS 2003.- Errata to Analysis of the Harmonic Algorithm for Three Servers.