Format:
1 Online-Ressource (780 pages)
ISBN:
0818691727
,
9780818691720
Content:
Annotation, Partial Contents: The Access Network Design Problem; Jitter Control in QoS Networks; Delayed Information & Action in On-line Algorithms; The Complexity of the Approximation of the Bandwidth Problem; Satisfiability of Word Equations with Constants is in Exponential Space; A Primitive Recursive Algorithm for the General Petri Net Reachability Problem; Algorithms to Tile the Infinite Grid with Finite Clusters; On Approximate Nearest Neighbors in Non-Euclidean Spaces; Pattern Matching for Spatial Point Sets; Overcoming the Memory Bottleneck in Suffix Tree Construction; Unsatisfiable Systems of Equations, Over a Finite Field; Local Search in Smooth Convex Sets; Geometric Separator Theorems & Applications; Time-Space Tradeoffs for Branching Programs; Optimal Time-Space Trade-Offs for Sorting; On the Single-Source Unsplittable Flow Problem; A Divide- & -Conquer Algorithm for Min-Cost Perfect Matching in the Plane; The Quantum Communication Complexity of Sampling; Quantum Lower Bounds by Polynomials; Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations; Approximating a Finite Metric by a Small Number of Tree Metrics; Random Projection: A New Approach to VLSI Layout; Map Graphs in Polynomial Time; Testing Monotonicity; The Finite Capacity Dial-A-Ride Problem; Semidefinite Relaxations for Parallel Machine Scheduling; Lower Bounds for Zero Knowledge on the Internet; Oblivious Transfer with a Memory-Bounded Receiver; Quantum Cryptography with Imperfect Apparatus; Protocols for Asymmetric Communication Channels; Towards an Optimal Bit-Reversal Permutation Program; Concurrent Reachability Games; Which Problems Have Strongly Exponential Complexity?; Recommendation Systems: A Probabilistic Analysis; Improved Bounds & Algorithms for Hypergraph Two-Coloring; A Characterization of NC by Tree Recurrence; Randomness vs. Time: De-Randomization under a Uniform Assumption
Content:
The Access Network Design Problem; Jitter Control in QoS Networks; Delayed Information & Action in On-line Algorithms; The Complexity of the Approximation of the Bandwidth Problem; Satisfiability of Word Equations with Constants is in Exponential Space; A Primitive Recursive Algorithm for the General Petri Net Reachability Problem; Algorithms to Tile the Infinite Grid with Finite Clusters; On Approximate Nearest Neighbors in Non-Euclidean Spaces; Pattern Matching for Spatial Point Sets; Overcoming the Memory Bottleneck in Suffix Tree Construction; Unsatisfiable Systems of Equations, Over a Finite Field; Local Search in Smooth Convex Sets; Geometric Separator Theorems & Applications; Time-Space Tradeoffs for Branching Programs; Optimal Time-Space Trade-Offs for Sorting; On the Single-Source Unsplittable Flow Problem; A Divide- & -Conquer Algorithm for Min-Cost Perfect Matching in the Plane; The Quantum Communication Complexity of Sampling; Quantum Lower Bounds by Polynomials; Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations; Approximating a Finite Metric by a Small Number of Tree Metrics; Random Projection: A New Approach to VLSI Layout; Map Graphs in Polynomial Time; Testing Monotonicity; The Finite Capacity Dial-A-Ride Problem; Semidefinite Relaxations for Parallel Machine Scheduling; Lower Bounds for Zero Knowledge on the Internet; Oblivious Transfer with a Memory-Bounded Receiver; Quantum Cryptography with Imperfect Apparatus; Protocols for Asymmetric Communication Channels; Towards an Optimal Bit-Reversal Permutation Program; Concurrent Reachability Games; Which Problems Have Strongly Exponential Complexity?; Recommendation Systems: A Probabilistic Analysis; Improved Bounds & Algorithms for Hypergraph Two-Coloring; A Characterization of NC by Tree Recurrence; Randomness vs. Time: De-Randomization under a Uniform Assumption
Language:
English
Keywords:
Konferenzschrift
Bookmarklink
