Invited speakers

• Johan Håstad (KTH, Sweden).
  On non trivial approximations of CSPs
  
  
• Nick Wormald (University of Waterloo, Canada).
  Analysis of algorithms on the cores of random graphs

Papers accepted at APPROX'06

• Chandra Chekuri and Martin Pal.
  An O(log n) Approximation Ratio for the Asymmetric Traveling Salesman Path Problem
  
  
• T-H. Hubert Chan, Donglin Xia, Goran Konjevod and Andrea Richa.
  A Tight Lower Bound for the Steiner Point Removal Problem on Trees
  
  
• Inge Li Goertz.
  Hardness of Preemptive Finite Capacity Dial-a-Ride
  
  
• MohammadTaghi Hajiaghayi, Guy Kortsarz and MohammadReza Salavatipour.
  Approximating Buy-at-Bulk and Shallow-light $-Steiner trees
  
  
• Viswanath Nagarajan and R Ravi.
  Minimum vehicle routing with a common deadline
  
  
• Christoph Ambühl, Monaldo Mastrolilli and Ola Svensson.
  Approximating Precedence-Constrained Single Machine Scheduling by Coloring
  
  
• Leah Epstein, Magnus Halldorsson, Asaf Levin and Hadas Shachnai.
  Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs
  
  
• Zeev Nutov.
  Approximating minimum power covers of intersecting families and directed connectivity problems
  
  
• Jean Cardinal, Samuel Fiorini and Gwenaël Joret.
  Tight Results on Minimum Entropy Set Cover
  
  
• Christoph Ambühl, Thomas Erlebach, Matus Mihalak and Marc Nunkesser.
  Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs
  
  
• Alexander Grigoriev, Maxim Sviridenko and Marc Uetz.
  LP Rounding and an Almost Harmonic Algorithm for Scheduling with Resource Dependent Processing Times
  
  
• Retsef Levi and Maxim Sviridenko.
  Improved Approximation Algorithm for the One-Warehouse Multi-Retailer Problem
  
  
• Michael Langberg, Yuval Rabani and Chaitanya Swamy.
  Approximation Algorithms for Graph Homomorphism Problems
  
  
• Samir Khuller, Azarakhsh Malekian and Yoo-Ah Kim.
  Improved Algorithms for Data Migration
  
  
• Rajiv Gandhi and Julian Mestre.
  Combinatorial Algorithms for Data Migration to Minimize Average Completion Time
  
  
• Anthony Man-Cho So, Jiawei Zhang and Yinyu Ye.
  Stochastic Combinatorial Optimization with Controllable Risk Aversion Level
  
  
• Nikhil Bansal, Don Coppersmith and Baruch Schieber.
  Minimizing Setup and Beam-On Times in Radiation Therapy
  
  
• David Woodruff.
  Better Approximations for the Minimum Common Integer Partition Problem
  
  
• Sashka Davis, Jeff Edmonds and Russell Imagliazzo.
  Online Algorithms To Minimize Resource Reallocations and Network Communication
  
  
• Rene Sitters, Gil Shallom, Yair Bartal and Stefano Leonardi.
  On the Value of Preemption in Scheduling
  
  
• Shuchi Chawla and Tim Roughgarden.
  Single-Source Stochastic Routing
  
  
• Benjamin Birnbaum and Kenneth Goldman.
  An Improved Analysis for a Greedy Remote-Clique Algorithm using Factor-Revealing LPs
  
  

Papers accepted at RANDOM'06

• Oded Lachish, Ilan Newman and Asaf Shapira.
  Space Complexity vs. Query Complexity
  
  
• Sharon Marko and Dana Ron.
  Distance Approximation in Bounded-Degree and General Sparse Graphs
  
  
• Dana Ron and Oded Goldreich.
  Approximating Average Parameters of Graphs
  
  
• Martin Dyer, Leslie Goldberg and Mark Jerrum.
  Dobrushin conditions and Systematic Scan
  
  
• Avner magen, Shlomo hoory and Toniann Pitassi.
  Monotone circuits for the majority function
  
  
• Irit Dinur, Madhu Sudan and Avi Wigderson.
  Robust local testability of tensor products of LDPC
  
  
• Rajeev Motwani, Rina Panigrahy and Ying Xu.
  Fractional Matching via Balls-and-Bins
  
  
• Uriel Feige, Elchanan Mossel and Dan Vilenchik.
  Complete convergence of message passing algorithms for some satisfiability problems
  
  
• Amit Deshpande and Santosh Vempala.
  Adaptive Sampling and Fast Low-Rank Matrix Approximation
  
  
• Petros Drineas, Michael Mahoney and S. (Muthu) Muthukrishnan.
  Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
  
  
• Sanjeev Arora, Elad Hazan and Satyen Kale.
  A Fast Random Sampling Algorithm for Sparsifying Matrices
  
  
• Murali Ganapathy.
  Robust Mixing Time
  
  
• Alexander Healy.
  Randomness-Efficient Sampling within NC1
  
  
• Thomas Strohmer and Roman Vershynin.
  A randomized solver for linear systems with exponential convergence
  
  
• Nayantara Bhatnagar, Sam Greenberg and Dana Randall.
  The Effect of Boundary Conditions on Mixing Rates of Markov Chains
  
  
• Dan Gutfreund.
  Optimal worst-case to average-case reductions within the polynomial-time hierarchy
  
  
• Martin Marciniszyn, Jozef Skokan, Reto Spöhel and Angelika Steger
  Threshold Functions for Asymmetric Ramsey Properties Involving Cliques
  
  
• Elena Grigorescu, Swastik Kopparty and Madhu Sudan.
  Local Decoding and Testing for Homomorphisms
  
  
• Philipp Woelfel.
  Maintaining External Memory Efficient Hash Tables
  
  
• Yi-Kai Liu, Vadim Lyubashevsky and Daniele Micciancio.
  On Bounded Distance Decoding for General Lattices
  
  
• Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
  On Pseudorandom Generators with Linear Stretch in NC0
  
  
• Yi-Kai Liu.
  Consistency of Local Density Matrices is QMA-complete