Combinatorics, Computing and Complexity

Inhaltsverzeichnis

• What is structural complexity theory?.
• Constructing oracles by lower bound techniques for circuits.
• Randomness, tally sets, and complexity classes.
• On one-way functions.
• A new lower bound for parity circuits.
• How to design round Robin schedules.
• Bandwidth in multigrids for random graphs.
• A flavor of matroids, graphs and optimal job assignment problems in operations research.
• Algorithms for polymatroid optimization.
• Free partially commutative groups.
• Some results on VLSI parallel algorithms.
• On optimal arrangement of 12 points.
• Some discussions on vehicle routing problems.