Table of Contents

Contributed Talks of APPROX.- Approximating Optimal Binary Decision Trees.- Santa Claus Meets Hypergraph Matchings.- Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction.- Connected Vertex Covers in Dense Graphs.- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies.- Sweeping Points.- Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness.- Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks.- Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP.- Approximating Maximum Subgraphs without Short Cycles.- Deterministic 7/8-Approximation for the Metric Maximum TSP.- Inapproximability of Survivable Networks.- Approximating Single Machine Scheduling with Scenarios.- Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity.- A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One.- The Directed Minimum Latency Problem.- A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem.- Approximating Directed Weighted-Degree Constrained Networks.- A Constant Factor Approximation for Minimum ?-Edge-Connected k-Subgraph with Metric Costs.- Budgeted Allocations in the Full-Information Setting.- Contributed Talks of RANDOM.- Optimal Random Matchings on Trees and Applications.- Small Sample Spaces Cannot Fool Low Degree Polynomials.- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size.- Tensor Products of Weakly Smooth Codes Are Robust.- On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs.- Improved Bounds for Testing Juntas.- The Complexity of Distinguishing MarkovRandom Fields.- Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms.- Tight Bounds for Hashing Block Sources.- Improved Separations between Nondeterministic and Randomized Multiparty Communication.- Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs.- On the Query Complexity of Testing Orientations for Being Eulerian.- Approximately Counting Embeddings into Random Graphs.- Increasing the Output Length of Zero-Error Dispersers.- Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals.- The Complexity of Local List Decoding.- Limitations of Hardness vs. Randomness under Uniform Reductions.- Learning Random Monotone DNF.- Breaking the ?-Soundness Bound of the Linearity Test over GF(2).- Dense Fast Random Projections and Lean Walsh Transforms.- Near Optimal Dimensionality Reductions That Preserve Volumes.- Sampling Hypersurfaces through Diffusion.- A 2-Source Almost-Extractor for Linear Entropy.- Extractors for Three Uneven-Length Sources.- The Power of Choice in a Generalized Pólya Urn Model.- Corruption and Recovery-Efficient Locally Decodable Codes.- Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets.