13. RANDOM / 12. APPROX 2009: Berkeley, CA, USA

Contributed Talks of APPROX

• Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani:
  Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs. 1-14
  
• Ankit Aggarwal, Amit Deshpande, Ravi Kannan:
  Adaptive Sampling for k-Means Clustering. 15-28
  
• Douglas E. Carroll, Adam Meyerson, Brian Tagiku:
  Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs. 29-41
  
• Chandra Chekuri, Alina Ene, Nitish Korula:
  Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs. 42-55
  
• Chandra Chekuri, Iftah Gamzu:
  Truthful Mechanisms via Greedy Iterative Packing. 56-69
  
• Julia Chuzhoy, Paolo Codenotti:
  Resource Minimization Job Scheduling. 70-83
  
• José R. Correa, Martin Skutella, José Verschae:
  The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders. 84-97
  
• Friedrich Eisenbrand, Thomas Rothvoß:
  New Hardness Results for Diophantine Approximation. 98-110
  
• Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh:
  PASS Approximation. 111-124
  
• Konstantinos Georgiou, Avner Magen, Madhur Tulsiani:
  Optimal Sherali-Adams Gaps from Pairwise Independence. 125-139
  
• Matt Gibson, Gaurav Kanade, Erik Krohn, Kasturi R. Varadarajan:
  An Approximation Scheme for Terrain Guarding. 140-148
  
• Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Danny Segev:
  Scheduling with Outliers. 149-162
  
• Venkatesan Guruswami, Ali Kemal Sinop:
  Improved Inapproximability Results for Maximum k-Colorable Subgraph. 163-176
  
• Rolf Harren, Rob van Stee:
  Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems. 177-189
  
• Alexander Jaffe, James R. Lee, Mohammad Moharrami:
  On the Optimality of Gluing over Scales. 190-201
  
• Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, Maxim Sviridenko:
  On Hardness of Pricing Items for Single-Minded Bidders. 202-216
  
• Ronald Koch, Britta Peis, Martin Skutella, Andreas Wiese:
  Real-Time Message Routing and Scheduling. 217-230
  
• Guy Kortsarz, Zeev Nutov:
  Approximating Some Network Design Problems with Node Costs. 231-243
  
• Jon Lee, Maxim Sviridenko, Jan Vondrák:
  Submodular Maximization over Multiple Matroids via Generalized Exchange Properties. 244-257
  
• Avner Magen, Mohammad Moharrami:
  Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy. 258-271
  
• Adam Meyerson, Brian Tagiku:
  Minimizing Average Shortest Path Distances via Shortcut Edge Addition. 272-285
  
• Zeev Nutov:
  Approximating Node-Connectivity Augmentation Problems. 286-297
  
• Katarzyna Paluch, Marcin Mucha, Aleksander Madry:
  A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem. 298-311
  
• Saurav Pandit, Sriram V. Pemmaraju, Kasturi R. Varadarajan:
  Approximation Algorithms for Domatic Partitions of Unit Disk Graphs. 312-325
  
• Thomas Rothvoß, Laura Sanità:
  On the Complexity of the Asymmetric VPN Problem. 326-338
  

Contributed Talks of RANDOM

• Noga Alon, Rina Panigrahy, Sergey Yekhanin:
  Deterministic Approximation Algorithms for the Nearest Codeword Problem. 339-351
  
• Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen, Ronen Shaltiel:
  Strong Parallel Repetition Theorem for Free Projection Games. 352-365
  
• Ido Ben-Eliezer, Rani Hod, Shachar Lovett:
  Random Low Degree Polynomials are Hard to Approximate. 366-377
  
• Eli Ben-Sasson, Michael Viderman:
  Composition of Semi-LTCs by Two-Wise Tensor Products. 378-391
  
• Andrej Bogdanov, Youming Qiao:
  On the Security of Goldreich's One-Way Function. 392-405
  
• S. Charles Brubaker, Santosh Vempala:
  Random Tensors and Planted Cliques. 406-419
  
• Karthekeyan Chandrasekaran, Amit Deshpande, Santosh Vempala:
  Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry. 420-433
  
• Prasad Chebolu, Alan M. Frieze, Páll Melsted, Gregory B. Sorkin:
  Average-Case Analyses of Vickrey Costs. 434-447
  
• Victor Chen:
  A Hypergraph Dictatorship Test with Perfect Completeness. 448-461
  
• Anindya De, Luca Trevisan:
  Extractors Using Hardness Amplification. 462-475
  
• Klim Efremenko, Omer Reingold:
  How Well Do Random Walks Parallelize?. 476-489
  
• Alan M. Frieze, Páll Melsted, Michael Mitzenmacher:
  An Analysis of Random-Walk Cuckoo Hashing. 490-503
  
• Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
  Hierarchy Theorems for Property Testing. 504-519
  
• Oded Goldreich, Dana Ron:
  Algorithmic Aspects of Property Testing in the Dense Graphs Model. 520-533
  
• Elena Grigorescu, Tali Kaufman, Madhu Sudan:
  Succinct Representation of Codes with Applications to Testing. 534-547
  
• Aram Wettroth Harrow, Richard A. Low:
  Efficient Quantum Tensor Product Expanders and k-Designs. 548-561
  
• T. S. Jayram:
  Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND. 562-573
  
• Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel:
  Pseudorandom Generators and Typically-Correct Derandomization. 574-587
  
• Adam R. Klivans, Philip M. Long, Alex K. Tang:
  Baum's Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions. 588-600
  
• Swastik Kopparty, Shubhangi Saraf:
  Tolerant Linearity Testing and Locally Testable Codes. 601-614
  
• Shachar Lovett, Omer Reingold, Luca Trevisan, Salil P. Vadhan:
  Pseudorandom Bit Generators That Fool Modular Sums. 615-630
  
• Brendan Lucier, Michael Molloy, Yuval Peres:
  The Glauber Dynamics for Colourings of Bounded Degree Trees. 631-645
  
• Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
  Testing ±1-weight halfspace. 646-657
  
• Raghu Meka, David Zuckerman:
  Small-Bias Spaces for Group Products. 658-672
  
• Lorenz Minder, Dan Vilenchik:
  Small Clique Detection and Approximate Nash Equilibria. 673-685
  
• Dana Ron, Gilad Tsur:
  Testing Computability by Width Two OBDDs. 686-699
  
• Amir Shpilka, Ilya Volkovich:
  Improved Polynomial Identity Testing for Read-Once Formulas. 700-713
  
• Terence Tao, Van H. Vu:
  Smooth Analysis of the Condition Number and the Least Singular Value. 714-737