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

Front Matter....Pages -
Spectral Sparsification in Dynamic Graph Streams....Pages 1-10
The Online Stochastic Generalized Assignment Problem....Pages 11-25
On the NP -Hardness of Approximating Ordering Constraint Satisfaction Problems....Pages 26-41
Approximating Large Frequency Moments with Pick-and-Drop Sampling....Pages 42-57
Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for Frequency-Based Vectors on Streams....Pages 58-70
Capacitated Network Design on Undirected Graphs....Pages 71-80
Scheduling Subset Tests: One-Time, Continuous, and How They Relate....Pages 81-95
On the Total Perimeter of Homothetic Convex Bodies in a Convex Container....Pages 96-109
Partial Interval Set Cover – Trade-Offs between Scalability and Optimality....Pages 110-125
Online Square-into-Square Packing....Pages 126-141
Online Non-clairvoyant Scheduling to Simultaneously Minimize All Convex Functions....Pages 142-157
Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems....Pages 158-172
Multiple Traveling Salesmen in Asymmetric Metrics....Pages 173-188
Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback....Pages 189-204
The Approximability of the Binary Paintshop Problem....Pages 205-217
Approximation Algorithms for Movement Repairmen....Pages 218-232
Improved Hardness of Approximating Chromatic Number....Pages 233-243
A Pseudo-approximation for the Genus of Hamiltonian Graphs....Pages 244-259
A Local Computation Approximation Scheme to Maximum Matching....Pages 260-273
Sketching Earth-Mover Distance on Graph Metrics....Pages 274-286
Online Multidimensional Load Balancing....Pages 287-302
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs....Pages 303-316
Interdiction Problems on Planar Graphs....Pages 317-331
Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration....Pages 332-346
Finding Heavy Hitters from Lossy or Noisy Data....Pages 347-362
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy....Pages 363-378
Phase Coexistence and Slow Mixing for the Hard-Core Model on ℤ 2 ....Pages 379-394
Fast Private Data Release Algorithms for Sparse Queries....Pages 395-410
Local Reconstructors and Tolerant Testers for Connectivity and Diameter....Pages 411-424
An Optimal Lower Bound for Monotonicity Testing over Hypergrids....Pages 425-435
Small-Bias Sets for Nonabelian Groups....Pages 436-451
What You Can Do with Coordinated Samples....Pages 452-467
Robust Randomness Amplifiers: Upper and Lower Bounds....Pages 468-483
The Power of Choice for Random Satisfiability....Pages 484-496
Connectivity of Random High Dimensional Geometric Graphs....Pages 497-512
Matching-Vector Families and LDCs over Large Modulo....Pages 513-526
Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing....Pages 527-542
Testing Membership in Counter Automaton Languages....Pages 543-558
Tight Lower Bounds for Testing Linear Isomorphism....Pages 559-574
Randomness-Efficient Curve Samplers....Pages 575-590
Combinatorial Limitations of Average-Radius List Decoding....Pages 591-606
Zero Knowledge LTCs and Their Applications....Pages 607-622
A Tight Lower Bound for High Frequency Moment Estimation with Small Error....Pages 623-638
Improved FPTAS for Multi-spin Systems....Pages 639-654
Pseudorandomness for Regular Branching Programs via Fourier Analysis....Pages 655-670
Absolutely Sound Testing of Lifted Codes....Pages 671-682
On the Average Sensitivity and Density of k -CNF Formulas....Pages 683-698
Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions....Pages 699-713
Back Matter....Pages -