E-raamat: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013, Proceedings

Spectral Sparsification in Dynamic Graph Streams.- The Online Stochastic
Generalized Assignment Problem.- On the NP-Hardness of Approximating Ordering
Constraint Satisfaction Problems.- Approximating Large Frequency Moments with
Pick-and-Drop Sampling.- Generalizing the Layering Method of Indyk and
Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams.-
Capacitated Network Design on Undirected Graphs.- Scheduling Subset Tests:
One-Time, Continuous, and How They Relate.- On the Total Perimeter of
Homothetic Convex Bodies in a Convex Container.- Partial Interval Set Cover
Trade-Offs between Scalability and Optimality.- Online Square-into-Square
Packing.- Online Non-clairvoyant Scheduling to Simultaneously Minimize All
Convex Functions.- Shrinking Maxima, Decreasing Costs: New Online Packing
and
Covering Problems.- Multiple Traveling Salesmen in Asymmetric Metrics.-
Approximate Indexability and Bandit Problems with Concave Rewards
and Delayed Feedback.- The Approximability of the Binary Paintshop Problem.-
Approximation Algorithms for Movement Repairmen.- Improved Hardness of
Approximating Chromatic Number.- A Pseudo-approximation for the Genus of
Hamiltonian Graphs.- A Local Computation Approximation Scheme to Maximum
Matching.- Sketching Earth-Mover Distance on Graph Metrics.- Online
Multidimensional Load Balancing.- A New Regularity Lemma and Faster
Approximation Algorithms for Low Threshold Rank Graphs.- Interdiction
Problems on Planar Graphs.- Conditional Random Fields, Planted Constraint
Satisfaction and Entropy Concentration.- Finding Heavy Hitters from Lossy or
Noisy Data.- Private Learning and Sanitization: Pure vs. Approximate
Differential Privacy.- Phase Coexistence and Slow Mixing for the Hard-Core
Model on Z2.- Fast Private Data Release Algorithms for Sparse Queries.- Local
Reconstructors and Tolerant Testers for Connectivity and Diameter.- An
Optimal Lower Bound for Monotonicity Testing over Hypergrids.- Small-Bias
Sets for NonabelianGroups: Derandomizations of the Alon-Roichman Theorem.-
What You Can Do with Coordinated Samples.- Robust Randomness Amplifiers:
Upper and Lower Bounds.- The Power of Choice for Random Satisfiability.-
Connectivity of Random High Dimensional Geometric Graphs.- Matching-Vector
Families and LDCs over Large Modulo.- Explicit Noether Normalization for
Simultaneous Conjugation via Polynomial Identity Testing.- Testing Membership
in Counter Automaton Languages.- Tight Lower Bounds for Testing Linear
Isomorphism.- Randomness-Efficient Curve Samplers.- Combinatorial Limitations
of Average-Radius List Decoding.- Zero Knowledge LTCs and Their
Applications.- A Tight Lower Bound for High Frequency Moment Estimation with
Small Error.- Improved FPTAS for Multi-spin Systems.- Pseudorandomness for
Regular Branching Programs via Fourier Analysis.- Absolutely Sound Testing of
Lifted Codes.- On the Average Sensitivity and Density of k-CNF Formulas.-
Improved Bounds on the Phase Transition for the Hard-Core Model in
2-Dimensions.