Theory and Applications of Models of Computation

Complexity theory .- Nondeterministic Communication Complexity of random Boolean functions.- Pebble games over ordered structural abstractions.- The Complexity of Finding Read-Once NAE-Resolution Refutations.- Bounds for Semi-disjoint Bilinear Forms in a Unit-cost Computational Model.- Learning AC0 under k-Dependent Distributions.- Algorithms.- Computing the Rectilinear Center of Uncertain Points in the Plane.- The Smoothed Number of Pareto-optimal Solutions in Non-integer Bicriteria Optimization.- Fast Searching on Cartesian Products of Graphs.- Parikh Images of Matrix Ins-del Systems.- Scheduling Fully Parallel Jobs with Integer Parallel Units.- An O(n2) Algorithm for Computing Optimal Continuous Voltage Schedules.- Continuous Firefighting on Infinite Square Grids.- Multi-interval Pairwise Compatibility Graphs.- Scheduling Tasks to Minimize Active Time on a Processor with Unlimited Capacity.- Efficient algorithms for touring a sequence of convex polygons and related problems.- Networks and game theory.- Hardness of Routing for Minimizing Superlinear Polynomial Cost in Directed Graphs.- P 3-Games.- The Price of Anarchy in Two-Stage Scheduling Games (Extended Abstract).- On Postoptimality Analysis of Maximum Reliability and Maximum Capacity Path Problems: Multiplicative Tolerances.- Fixed parameter tractability .- Kernelization and Parameterized Algorithms for 3-Path Vertex Cover.- Turbo-charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis.- Computability theory.- A Note on Effective Categoricity for Linear Orderings.- Degrees of Word Problem for Algebras without Finitely Presented Expansions.