Uri Feige

Christos Papadimitriou

Madhu Sudan

Avi Wigderson


Organizer:   Klaus Jansen


                         Susanne Albers

                          Evripidis Bampis

                           Stefano Leonardi







TITLE: Testing the Diameter of Graphs
AUTHORS: Michal Parnas and Dana Ron

TITLE: Improved derandomization of BPP using a hitting set generator.
AUTHORS: Oded Goldreich and Avi Wigderson.

TITLE: Probablistic Construction of Small Strongly
Sum-Free Sets via Large Sidon Sets
AUTHOR: Andreas Baltz, Tomasz Schoen, Anand Srivastav

TITLE: Completeness and robustness properties of min-wise
independent permutations
AUTHORS: Andrei Broder and Michael Mitzenmacher

TITLE:  Discrepant Sets Yield Approximate Min-Wise Independent Permutation
AUTHORS: Michael Saks, Aravind Srinivasan, Shiyu Zhou and David Zuckerman

TITLE: Algorithms for Graph Partitioning on the Planted Partition Model
AUTHORS: Anne E. Condon and Richard M. Karp

TITLE: Pfaffian Algorithms for Sampling Routings on Regions with
Free Boundary Conditions
AUTHOR: Russell Martin and Dana Randall

TITLE: "Improved Testing Algorithms for Monotonicity"
AUTHORS: Yevgeniy Dodis, Oded Goldreich, Eric Lehman,
Sofya Raskhodnikova, Dana Ron and Alex Samorodnitsky

TITLE: Linear Consistency Testing
AUTHORS: Yonatan Aumann, Michael O. Rabin and Madhu Sudan

TITLE: A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum
Spanning Forest
AUTHORS: Seth Pettie and Vijaya Ramachandran

TITLE: Fast Approximate PCPs for Multidimensional Bin-packing Problems
AUTHORS: Tugkan Batu, Ronitt Rubinfeld, Patrick White

TITLE: Improved Bounds for Sampling Contigency Tables
AUTHOR: Benjamin James Morris




TITLE: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
AUTHOR: Hans Kellerer

TITLE: Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths
AUTHORS: Noga Alon, Uri Arad, Yossi Azar

TITLE: Stochastic Machine Scheduling:
Performance Guarantees for LP-based Priority Policies
AUTHOR: Rolf H. Moehring, Andreas S. Schulz, and Marc Uetz

TITLE: Scheduling with Machine Cost
AUTHORS: Csan\'ad Imreh and John Noga

TITLE: Efficient Redundant Assignments under Fault-Tolerance Constraints
AUTHORS: Dimitris Fotakis and Paul Spirakis

TITLE: Approximating Minimum Manhattan Networks
AUTHORS: Joachim Gudmundsson, Christos Levcopoulos and Giri Narasimhan

TITLE: Approximation of Multi-Color Discrepancy
AUTHORS: Benjamin Doerr, Anand Srivastav

TITLE: A linear time approximation scheme for the job shop scheduling problem.
AUTHORS:Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko

TITLE: Hardness Results for the Power Range Assignment
Problem in Packet Radio Networks
AUTHORS: Andrea E. F. Clementi , Paolo Penna , and Riccardo Silvestri

TITLE: A New Approximation Algorithm for the Demand Routing and Slotting Problem
with Unit Demands on Rings
AUTHOR: Christine Cheng

TITLE: Set Cover with Requirements and Costs Evolving over Time
AUTHORS: Milena Mihail

TITLE: Multi-coloring Planar graphs and Partial k-Trees
AUTHORS: Magnus M Halldorsson and Guy Kortsarz