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