TCC 2009, the 6th Theory of Cryptography Conference, was held in San Fr- cisco, CA, USA, March 15-17, 2009. TCC 2009 was sponsored by the Inter- tional Association for Cryptologic Research (IACR) and was organized in - operation with the Applied Crypto Group at Stanford University. The General Chair of the conference was Dan Boneh. The conference received 109 submissions, of which the Program Comm- tee selected 33 for presentation at the conference. These proceedings consist of revised versions of those 33 papers. The revisions were not reviewed, and the authors bear full responsibility for the contents of their papers. The conference program also included two invited talks: "The Di?erential Privacy Frontier," given by Cynthia Dwork and "Some Recent Progress in Lattice-Based Crypt- raphy," given by Chris Peikert. I thank the Steering Committee of TCC for entrusting me with the resp- sibility for the TCC 2009 program. I thank the authors of submitted papers for their contributions. The general impression of the Program Committee is that the submissions were of very high quality, and there were many more papers we wanted to accept than we could. The review process was therefore very - warding but the selection was very delicate and challenging. I am grateful for the dedication, thoroughness, and expertise ofthe ProgramCommittee. Obse- ing the way the members of the committee operated makes me as con?dent as possible of the outcome of our selection process.

This book constitutes the joint refereed proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and the 11th International Workshop on Randomization and Computation, RANDOM 2007, held in Princeton, NJ, USA, in August 2007.

The 44 revised full papers presented were carefully reviewed and selected from 99 submissions. Topics of interest covered by the papers are design and analysis of approximation algorithms, hardness of approximation, small space and data streaming algorithms, sub-linear time algorithms, embeddings and metric space methods, mathematical programming methods, coloring and partitioning, cuts and connectivity, geometric problems, game theory and applications, network design and routing, packing and covering, scheduling, design and analysis of randomized algorithms, randomized complexity theory, pseudorandomness and derandomization, random combinatorial structures, random walks/Markov chains, expander graphs and randomness extractors, probabilistic proof systems, random projections and embeddings, error-correcting codes, average-case analysis, property testing, computational learning theory, and other applications of approximation and randomness.