Maria J. Serna
, Ronen Shaltiel
, Klaus Jansen
, José D. P. Rolim
(Eds.): Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings.
Springer 2010 Lecture Notes in Computer Science
Contributed Talks of APPROX
: Improved Inapproximability for Submodular Maximization.
, Igor Shinkar
: On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors.
: Approximation Algorithms for Reliable Stochastic Combinatorial Optimization.
Contributed Talks of RANDOM
, Dana Ron
: Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries.
: On Testing Computability by Small Width OBDDs.
, Stanislaw Szarek
: Almost-Euclidean Subspaces of l1N\ell_1^N via Tensor Products: A Simple Approach to Randomness Reduction.
: Differential Privacy and the Fat-Shattering Dimension of Linear Queries.
: Improved Rounding for Parallel Repeated Unique Games.
: Relativized Worlds without Worst-Case to Average-Case Reductions for NP.
David P. Woodruff
: A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field.