STACS 2005 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005. Proceedings /
| Συγγραφή απο Οργανισμό/Αρχή: | |
|---|---|
| Άλλοι συγγραφείς: | , |
| Μορφή: | Ηλεκτρονική πηγή Ηλ. βιβλίο |
| Γλώσσα: | English |
| Έκδοση: |
Berlin, Heidelberg :
Springer Berlin Heidelberg,
2005.
|
| Σειρά: | Lecture Notes in Computer Science,
3404 |
| Θέματα: | |
| Διαθέσιμο Online: | Full Text via HEAL-Link |
Πίνακας περιεχομένων:
- Invited Talks
- Automorphisms of Finite Rings and Applications to Complexity of Problems
- Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages
- Algorithmics in Exponential Time
- Session 1A
- Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics
- Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms
- Truthful Approximation Mechanisms for Scheduling Selfish Related Machines
- Session 1B
- Counting in the Two Variable Guarded Logic with Transitivity
- The Variable Hierarchy of the ?-Calculus Is Strict
- The Core of a Countably Categorical Structure
- Session 2A
- How Common Can Be Universality for Cellular Automata?
- Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods
- Session 2B
- On the Decidability of Temporal Properties of Probabilistic Pushdown Automata
- Deciding Properties of Contract-Signing Protocols
- Session 3A
- Polylog-Time Reductions Decrease Dot-Depth
- On the Computational Complexity of the Forcing Chromatic Number
- More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP
- Session 3B
- Three Optimal Algorithms for Balls of Three Colors
- Cost Sharing and Strategyproof Mechanisms for Set Cover Games
- On Weighted Balls-into-Bins Games
- Session 4A
- Computing Minimal Multi-homogeneous Bézout Numbers Is Hard
- Dynamic Complexity Theory Revisited
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Session 4B
- Shortest Monotone Descent Path Problem in Polyhedral Terrain
- Packet Buffering: Randomization Beats Deterministic Algorithms
- Solving Medium-Density Subset Sum Problems in Expected Polynomial Time
- Session 5A
- Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms
- Regular Tree Languages Definable in FO
- Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations
- Session 5B
- Connectivity for Wireless Agents Moving on a Cycle or Grid
- Improved Algorithms for Dynamic Page Migration
- Approximate Range Mode and Range Median Queries
- Session 6A
- Topological Automata
- Minimizing NFA’s and Regular Expressions
- Session 6B
- Increasing Kolmogorov Complexity
- Kolmogorov-Loveland Randomness and Stochasticity
- Session 7A
- Information Theory in Property Testing and Monotonicity Testing in Higher Dimension
- On Nash Equilibria in Non-cooperative All-Optical Networks
- Speed Scaling to Manage Temperature
- Session 7B
- The Complexity of Solving Linear Equations over a Finite Ring
- A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields
- Characterizing TC0 in Terms of Infinite Groups
- Session 8A
- Fast Pruning of Geometric Spanners
- The PIGs Full Monty – A Floor Show of Minimal Separators
- Centrality Measures Based on Current Flow
- Session 8B
- Varieties of Codes and Kraft Inequality
- Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes
- The Power of Commuting with Finite Sets of Words
- Session 9A
- Exact Quantum Algorithms for the Leader Election Problem
- Robust Polynomials and Quantum Algorithms
- Quantum Interactive Proofs with Competing Provers
- Session 9B
- Roundings Respecting Hard Constraints
- Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves
- Cycle Cover with Short Cycles
- Session 10A
- A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs
- All-Pairs Nearly 2-Approximate Shortest-Paths in O(n 2 polylog n) Time
- Session 10B
- Pattern Occurrences in Multicomponent Models
- Automatic Presentations for Finitely Generated Groups.
