Mathematical Foundations of Computer Science 2004

Inhalt

Invited Lectures.- A Case Study of Genome Evolution: From Continuous to Discrete Time Model.- Multicoloring: Problems and Techniques.- Some Recent Progress in Algorithmic Randomness.- Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms.- PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness.- Theory and Applied Computing: Observations and Anecdotes.- Boxed Ambients with Communication Interfaces.- Algebraic Recognizability of Languages.- Geometric Optimization and Unique Sink Orientations of Cubes.- Congestion Games and Coordination Mechanisms.- Graph Algorithms.- Equitable Colorings of Bounded Treewidth Graphs.- The Bidimensional Theory of Bounded-Genus Graphs.- Parallel Knock-Out Schemes in Networks.- Online Algorithms for Disk Graphs.- Approximations.- Protein Folding in the HP Model on Grid Lattices with Diagonals.- Optimization, Games, and Quantified Constraint Satisfaction.- Approximating Boolean Functions by OBDDs.- On Approximation Hardness of the Minimum 2SAT-DELETION Problem.- Graphs and Complexity.- Group Coloring and List Group Coloring Are ?2 P -Complete.- Complexity Results in Graph Reconstruction.- Generating Paths and Cuts in Multi-pole (Di)graphs.- Packing Directed Cycles Efficiently.- Circuits.- The Complexity of Membership Problems for Circuits over Sets of Integers.- Some Meet-in-the-Middle Circuit Lower Bounds.- The Enumerability of P Collapses P to NC.- On NC1 Boolean Circuit Composition of Non-interactive Perfect Zero-Knowledge.- General Complexity.- All Superlinear Inverse Schemes Are coNP-Hard.- The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups.- Generation Problems.- One Query Reducibilities Between Partial Information Classes.- Automata.- A New Dimension Sensitive Property for Cellular Automata.- Captive Cellular Automata.- Simulating 3D Cellular Automata with 2D Cellular Automata.- Graph Exploration by a Finite Automaton.- Parametrized and Kolmogorov Complexity.- On Polynomially Time Bounded Symmetry of Information.- Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets.- A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs.- Polynomial Time Approximation Schemes and Parameterized Complexity.- Semantics.- Epistemic Foundation of the Well-Founded Semantics over Bilattices.- Structural Model Checking for Communicating Hierarchical Machines.- Compositional Verification: Decidability Issues Using Graph Substitutions.- Event Structures for Resolvable Conflict.- Scheduling.- Optimal Preemptive Scheduling for General Target Functions.- The Price of Anarchy for Polynomial Social Cost.- Agent-Based Information Handling in Large Networks.- Approximating Earliest Arrival Flows with Flow-Dependent Transit Times.- Algebraic Theory of Languages.- A Hierarchy of Irreducible Sofic Shifts.- Membership and Reachability Problems for Row-Monomial Transformations.- On Pseudovarieties of Semiring Homomorphisms.- An Algebraic Generalization of ?-Regular Languages.- Games.- A Protocol for Serializing Unique Strategies.- A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games.- When Can You Play Positionally?.- Languages.- The Dual of Concatenation.- Computational Aspects of Disjunctive Sequences.- Decidability of Trajectory-Based Equations.- Geometry.- Efficient View Point Selection for Silhouettes of Convex Polyhedra.- Angles and Lengths in Reconfigurations of Polygons and Polyhedra.- Improved Bounds and Schemes for the Declustering Problem.- Crossing Number Is Hard for Cubic Graphs.- Languages and Complexity.- A Reducibility for the Dot-Depth Hierarchy.- Sublogarithmic Ambiguity.- An Elementary Proof for the Non-parametrizability of the Equation xyz=zvx.- A Generalization of Repetition Threshold.- Quantum Computing.- An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation.- Universal Test for Quantum One-Way Permutations.- A Common Algebraic Description for Probabilistic and Quantum Computations.- XML.- Extraction and Implication of Path Constraints.- Schema Evolution for XML: A Consistency-Preserving Approach.- Complexity of Decision Problems for Simple Regular Expressions.