12. RANDOM / 11. APPROX 2008: Boston, MA, USA

Contributed Talks of APPROX

• Micah Adler, Brent Heeringa:
  Approximating Optimal Binary Decision Trees. 1-9
  
• Arash Asadpour, Uriel Feige, Amin Saberi:
  Santa Claus Meets Hypergraph Matchings. 10-20
  
• Mihai Badoiu, Erik D. Demaine, MohammadTaghi Hajiaghayi, Anastasios Sidiropoulos, Morteza Zadimoghaddam:
  Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction. 21-34
  
• Jean Cardinal, Eythan Levy:
  Connected Vertex Covers in Dense Graphs. 35-48
  
• Eden Chlamtac, Gyanit Singh:
  Improved Approximation Guarantees through Higher Levels of SDP Hierarchies. 49-62
  
• Adrian Dumitrescu, Minghui Jiang:
  Sweeping Points. 63-76
  
• Venkatesan Guruswami, Prasad Raghavendra:
  Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness. 77-90
  
• Nir Halman, Chung-Lun Li, David Simchi-Levi:
  Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project Networks. 91-103
  
• David R. Karger, Jacob Scott:
  Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP. 104-117
  
• Guy Kortsarz, Michael Langberg, Zeev Nutov:
  Approximating Maximum Subgraphs without Short Cycles. 118-131
  
• Lukasz Kowalik, Marcin Mucha:
  Deterministic 7/8-Approximation for the Metric Maximum TSP. 132-145
  
• Yuval Lando, Zeev Nutov:
  Inapproximability of Survivable Networks. 146-152
  
• Monaldo Mastrolilli, Nikolaus Mutsanas, Ola Svensson:
  Approximating Single Machine Scheduling with Scenarios. 153-164
  
• Richard Matthew McCutchen, Samir Khuller:
  Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity. 165-178
  
• Shashi Mittal, Andreas S. Schulz:
  A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One. 179-192
  
• Viswanath Nagarajan, R. Ravi:
  The Directed Minimum Latency Problem. 193-206
  
• Thành Nguyen:
  A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem. 207-218
  
• Zeev Nutov:
  Approximating Directed Weighted-Degree Constrained Networks. 219-232
  
• MohammadAli Safari, Mohammad R. Salavatipour:
  A Constant Factor Approximation for Minimum lambda-Edge-Connected k-Subgraph with Metric Costs. 233-246
  
• Aravind Srinivasan:
  Budgeted Allocations in the Full-Information Setting. 247-253
  

Contributed Talks of RANDOM

• Jeff Abrahamson, Béla Csaba, Ali Shokoufandeh:
  Optimal Random Matchings on Trees and Applications. 254-265
  
• Noga Alon, Ido Ben-Eliezer, Michael Krivelevich:
  Small Sample Spaces Cannot Fool Low Degree Polynomials. 266-275
  
• Vikraman Arvind, Partha Mukhopadhyay:
  Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size. 276-289
  
• Eli Ben-Sasson, Michael Viderman:
  Tensor Products of Weakly Smooth Codes Are Robust. 290-302
  
• Nicla Bernasconi, Konstantinos Panagiotou, Angelika Steger:
  On the Degree Sequences of Random Outerplanar and Series-Parallel Graphs. 303-316
  
• Eric Blais:
  Improved Bounds for Testing Juntas. 317-330
  
• Andrej Bogdanov, Elchanan Mossel, Salil P. Vadhan:
  The Complexity of Distinguishing Markov Random Fields. 331-342
  
• Guy Bresler, Elchanan Mossel, Allan Sly:
  Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms. 343-356
  
• Kai-Min Chung, Salil P. Vadhan:
  Tight Bounds for Hashing Block Sources. 357-370
  
• Matei David, Toniann Pitassi, Emanuele Viola:
  Improved Separations between Nondeterministic and Randomized Multiparty Communication. 371-384
  
• Hang Dinh, Alexander Russell:
  Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs. 385-401
  
• Eldar Fischer, Oded Lachish, Ilan Newman, Arie Matsliah, Orly Yahalom:
  On the Query Complexity of Testing Orientations for Being Eulerian. 402-415
  
• Martin Fürer, Shiva Prasad Kasiviswanathan:
  Approximately Counting Embeddings into Random Graphs. 416-429
  
• Ariel Gabizon, Ronen Shaltiel:
  Increasing the Output Length of Zero-Error Dispersers. 430-443
  
• Venkatesan Guruswami, James R. Lee, Avi Wigderson:
  Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. 444-454
  
• Dan Gutfreund, Guy N. Rothblum:
  The Complexity of Local List Decoding. 455-468
  
• Dan Gutfreund, Salil P. Vadhan:
  Limitations of Hardness vs. Randomness under Uniform Reductions. 469-482
  
• Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan:
  Learning Random Monotone DNF. 483-497
  
• Tali Kaufman, Simon Litsyn, Ning Xie:
  Breaking the epsilon-Soundness Bound of the Linearity Test over GF(2). 498-511
  
• Edo Liberty, Nir Ailon, Amit Singer:
  Dense Fast Random Projections and Lean Walsh Transforms. 512-522
  
• Avner Magen, Anastasios Zouzias:
  Near Optimal Dimensionality Reductions That Preserve Volumes. 523-534
  
• Hariharan Narayanan, Partha Niyogi:
  Sampling Hypersurfaces through Diffusion. 535-548
  
• Anup Rao:
  A 2-Source Almost-Extractor for Linear Entropy. 549-556
  
• Anup Rao, David Zuckerman:
  Extractors for Three Uneven-Length Sources. 557-570
  
• Gregory B. Sorkin:
  The Power of Choice in a Generalized Pólya Urn Model. 571-583
  
• David P. Woodruff:
  Corruption and Recovery-Efficient Locally Decodable Codes. 584-595
  
• Raphael Yuster:
  Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets. 596-601