A calculus and algebra for distributed data management | p. 1 |
The Buchi complementation saga | p. 12 |
Speed-up techniques for shortest-path computations | p. 23 |
Compact forbidden-set routing | p. 37 |
A new bound for pure greedy hot potato routing | p. 49 |
Wavelength management in WDM rings to maximize the number of connections | p. 61 |
A first investigation of Sturmian trees | p. 73 |
On the size of the universal automaton of a regular language | p. 85 |
Correlations of partial words | p. 97 |
Testing convexity properties of tree colorings | p. 109 |
Why almost all k-colorable graphs are easy | p. 121 |
On defining integers in the counting hierarchy and proving arithmetic circuit lower bounds | p. 133 |
A new rank technique for formula size lower bounds | p. 145 |
Hard metrics from Cayley graphs of Abelian groups | p. 157 |
Broadcasting vs. mixing and information dissemination on Cayley graphs | p. 163 |
Light orthogonal networks with constant geometric dilation | p. 175 |
Admissibility in infinite games | p. 188 |
Pure stationary optimal strategies in Markov decision processes | p. 200 |
Symmetries and the complexity of pure Nash equilibrium | p. 212 |
Computing representations of matroids of bounded branch-width | p. 224 |
Characterizing minimal interval completions | p. 236 |
The complexity of unions of disjoint sets | p. 248 |
Kolmogorov-Loveland stochasticity and Kolmogorov complexity | p. 260 |
Bounded-hop energy-efficient broadcast in low-dimensional metrics via coresets | p. 272 |
On the complexity of affine image matching | p. 284 |
On fixed point equations over commutative semirings | p. 296 |
An exponential lower bound for prefix Grobner bases in free monoid rings | p. 308 |
A cubic kernel for feedback vertex set | p. 320 |
The union of minimal hitting sets : parameterized combinatorial bounds and counting | p. 332 |
An optimal, edges-only fully dynamic algorithm for distance-hereditary graphs | p. 344 |
A search algorithm for the maximal attractor of a cellular automaton | p. 356 |
Universal tilings | p. 367 |
On the complexity of unary tiling-recognizable picture languages | p. 381 |
A characterization of strong learnability in the statistical query model | p. 393 |
On the consistency of discrete Bayesian learning | p. 405 |
VPSPACE and a transfer theorem over the reals | p. 417 |
On symmetric signatures in holographic algorithms | p. 429 |
Randomly rounding rationals with cardinality constraints and derandomizations | p. 441 |
Cheating to get better roommates in a random stable matching | p. 453 |
A deterministic algorithm for summarizing asynchronous streams over a sliding window | p. 465 |
Arithmetizing classes around NC[superscript 1] and L | p. 477 |
The polynomially bounded perfect matching problem is in NC[superscript 2] | p. 489 |
Languages with bounded multiparty communication complexity | p. 500 |
New approximation algorithms for minimum cycle bases of graphs | p. 512 |
On completing Latin squares | p. 524 |
Small space representations for metric min-sum k-clustering and their applications | p. 536 |
An optimal tableau-based decision algorithm for propositional neighborhood logic | p. 549 |
Bounded-variable fragments of hybrid logics | p. 561 |
Rank-1 modal logics are coalgebraic | p. 573 |
An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups | p. 586 |
Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem | p. 598 |
Quantum network coding | p. 610 |
Reachability in unions of commutative rewriting systems is decidable | p. 622 |
Associative-commutative deducibility constraints | p. 634 |
On the automatic analysis of recursive security protocols with XOR | p. 646 |
Improved online algorithms for the sorting buffer problem | p. 658 |
Cost sharing methods for makespan and completion time scheduling | p. 670 |
Planar graphs : logical complexity and parallel isomorphism tests | p. 682 |
Enumerating all solutions for constraint satisfaction problems | p. 694 |
Table of Contents provided by Blackwell. All Rights Reserved. |