Computing and Combinatorics

Improved bounds for on-line load balancing.- O(n log n)-average-time algorithm for shortest network under a given topology.- Steiner problems on directed acyclic graphs.- Wormhole versus deflection routing: A case study on the mesh.- On sparse parity check matrices (extended abstract).- Finding a hidden code by asking questions.- Improved length lower bounds for reflecting sequences.- Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders.- Output-sensitive reporting of disjoint paths (extended abstract).- Rectangular grid drawings of plane graphs.- Area-efficient algorithms for upward straight-line tree drawings.- Straight skeletons for general polygonal figures in the plane.- A note on uniform circuit lower bounds for the counting hierarchy (extended abstract).- A note on the simulation of exponential threshold weights.- Harmonic analysis, real approximation, and the communication complexity of Boolean functions.- Finding large planar subgraphs and large subgraphs of a given genus.- Efficient deterministic algorithms for embedding graphs on books.- Optimal bi-level augmentation for selective! enhancing graph connectivity with applications.- Exact learning of subclasses of CDNF formulas with membership queries.- Fast separator decomposition for finite element meshes.- Reduction algorithms for constructing solutions in graphs with small treewidth.- Fast RNC and NC algorithms for finding a maximal set of paths with an application.- Sparse suffix trees.- Depth-efficient threshold circuits for multiplication and symmetric function computation.- A note on the self-witnessing property of computational problems.- The inverse satisfiability problem.- The join can lower complexity.- On the distribution of eigenvalues of graphs.- On the difficulty of designing good classifiers.- Approximating latin square extensions.- Approximating minimum keys and optimal substructure screens.- Reductions and convergence rates of average time.- On the complexity of computational problems associated with simple stochastic games.- On the complexity of commutativity analysis.- Improved non-approximability results for vertex cover with density constraints.- Some notes on the nearest neighbour interchange distance.- Distributed computing in asynchronous networks with byzantine edges.- Weight biased leftist trees and modified skip lists.- Probabilistic analysis of local search and NP-completeness result for constraint satisfaction.- On the reconfiguration of chains.- Two-guarding a rectilinear polygon.- Three systems for shared generation of authenticators.- Efficient generation of elliptic curve cryptosystems.- Superconnectivity for minimal multi-loop networks.