Show indexed articles as search result.

Contents: Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakovand Avi Wigderson, Simulating independence: new constructions of condensers, Ramsey graphs, dispersers, and extractors (1–10); Ran Raz, Extractors with weak random seeds (11–20); Andrej Bogdanov, Pseudorandom generators for low degree polynomials (21–30); Luca Trevisan, On uniform amplification of hardness in NP (31–38); Patrick Briest, Piotr Krysta and Berthold Vöcking, Approximation techniques for utilitarian mechanism design (39–48); Christos H. Papadimitriou, Computing correlated equilibria in multi-player games (49–56) ; BaruchAwerbuch, Yossi Azar and Amir Epstein, The price of routing unsplittable flow (57–66); GeorgeChristodoulou and Elias Koutsoupias, The price of anarchy of finite congestion games (67–73); Bruno Codenotti, Benton McCune and Kasturi Varadarajan, Market equilibrium via the excess demand function (74–83); OdedRegev, On lattices, learning with errors, random linear codes, and cryptography (84–93).
Miklós Ajtai, Representing hard lattices with \(O(n\log n)\) bits (extended abstract) (94–103); Christian Worm Mortensen, Rasmus Pagh and Mihai Pǎtraşcu, On dynamic range reporting in one dimension (extended abstract) (104–111); Mikkel Thorup, Worst-case update times for fully-dynamic all-pairs shortest paths (112–119); Lance Fortnow, Beyond NP: the work and legacy of Larry Stockmeyer (120–127); Noga Alon and Asaf Shapira, Every monotone graph property is testable (128–137); Eldar Fischer and Ilan Newman, Testing versus estimation of graph properties (extended abstract) (138–146); Ronitt Rubinfeld and Rocco A. Servedio, Testing monotone high-dimensional distributions (147–156); Katalin Friedl, Gábor Ivanyos and MiklosSantha, Efficient testing of groups (157–166); Joseph Cheriyan and Adrian Vetta, Approximation algorithms for network design with metric costs (167–175); Moses Charikar and Adriana Karagiozova, On non-uniform multicommodity buy-at-bulk network design (176–182).
Chandra Chekuri, Sanjeev Khanna and F.Bruce Shepherd, Multicommodity flow, well-linked terminals, and routing problems (183–192); MohammadTaghi Hajiaghayi, Jeong Han Kim, Tom Leighton and Harald Räcke, Oblivious routing in directed graphs with random demands (193–201); PiotrIndyk and David Woodruff, Optimal approximations of the frequency moments of data streams (202–208); Gereon Frahling and Christian Sohler, Coresets in dynamic geometric data streams (209–217); Rafail Ostrovsky and Yuval Rabani, Low distortion embeddings for edit distance (218–224); Mihai Bădoiu, Julia Chuzhoy, Piotr Indyk and Anastasios Sidiropoulos, Low-distortion embeddings of general metrics into the line (225–233); MikolajBojanczyk and Thomas Colcombet, Tree-walking automata do not recognize all regular languages (234–243); Itai Benjamini, Oded Schramm and David B. Wilson, Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read (244–250); Michael Alekhnovich, Lower bounds for \(k\)-DNF resolution on random 3-CNFs (extended abstract) (251–256); Michal Koucký, PavelPudlák and Denis Thérien, Bounded-depth circuits: separating wires from gates (extended abstract) (257–265).
Eli Ben-Sasson and Madhu Sudan, Simple PCPs with poly-log rate and query complexity (266–275); Matthew Andrews and Lisa Zhang, Hardness of the undirected edge-disjoint paths problem (276–283); Matthew Andrews and Lisa Zhang, Hardness of the undirected congestion minimization problem (284–293); Mikhail Alekhnovich, Sanjeev Arora and IannisTourlakis, Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy (294–303); Saugata Basu, Richard Pollack and Marie-Francoise Roy, Computing the first Betti number and the connected components of semi-algebraic sets (304–312); Saugata Basu, Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities (313–322); Xi Chenand Xiaotie Deng, On algorithms for discrete and approximate Brouwer fixed points (extended abstract) (323–330); Yossi Azar and Amir Epstein, Convex programming for scheduling unrelated parallel machines (331–337); Saurabh Sanghvi and Salil Vadhan, The round complexity of two-party random selection (338–347); Lance Fortnow, Rahul Santhanam and Luca Trevisan, Hierarchies for semantic classes (extended abstract) (348–355).
HaimKaplan, Eyal Kushilevitz and Yishay Mansour, Learning with attribute costs (356–365); ElchananMossel and Sébastien Roch, Learning nonsingular phylogenies and hidden Markov models (366–375); OmerReingold, Undirected ST-connectivity in log-space (376–385); Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman and Ravi Sundaram, Universal approximations for TSP, Steiner tree, and set cover (386–395); Naveen Garg, Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs (396–402); Ben Morris, The mixing time of the Thorp shuffle (403–412); Mary Cryan, Martin Dyer and Dana Randall, Approximately counting integral flows and cell-bounded contingency tables (413–422); V. H. Vu, Spectral norm of random matrices (423–430); Terence Taoand Van Vu, On random \(\pm1\) matrices: singularity and determinant (431–440); Abraham D. Flaxman, Alan M.Frieze and Juan C. Vera, On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem (441–449).
Micah Adler, Jeff Edmonds and Jiří Matoušek, Towards asymptotic optimality in probabilistic packet marking (450–459); Yaoyun Shi, Tensor norms and the classical communication complexity of nonlocal quantum measurement (extended abstract) (460–467); Sean Hallgren, Fast quantum algorithms for computing the unit group and class group of a number field (468–474); Arthur Schmidtand Ulrich Vollmer, Polynomial time quantum algorithm for the computation of the unit group of a number field (extended abstract) (475–480); Michael Ben-Or and AvinatanHassidim, Fast quantum Byzantine agreement (extended abstract) (481–485); Noga Alon, KonstantinMakarychev, Yury Makarychev and Assaf Naor, Quadratic forms on graphs (extended abstract) (486–493); Michael Elkin, Yuval Emek, Daniel A. Spielman and Shang-HuaTeng, Lower-stretch spanning trees (494–503); Daniel Gonçalves, Edge partition of planar graphs into two outerplanar graphs (504–512); Luis von Ahn, Nicholas Hopper and JohnLangford, Covert two-party computation (513–522); Hoeteck Wee, On obfuscating point functions (523–532).
Rafael Pass and Alon Rosen, New and improved constructions of non-malleable cryptographic protocols (533–542); Matt Lepinksi, Silvio Micali and Abhi Shelat, Collusion-free protocols (543–552); Sanjeev Arora, James R. Lee and Assaf Naor, Euclidean distortion and the sparsest cut (extended abstract) (553–562); Uriel Feige, Mohammad Taghi Hajiaghayi and James R. Lee, Improved approximation algorithms for minimum-weight vertex separators (extended abstract) (563–572) ; Amit Agarwal, MosesCharikar, Konstantin Makarychev and Yury Makarychev, \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems (573–581); JosephNaor and Roy Schwartz, Balanced metric labeling (extended abstract) (582–591) ; Zeev Dvir and Amir Shpilka, Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits (592–601); VenkatesanGuruswami and Atri Rudra, Limits to list decoding Reed-Solomon codes (602–609); Shahar Dobzinski, Noam Nisanand Michael Schapira, Approximation algorithms for combinatorial auctions with complement-free bidders (610–618); Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica and Madhu Sudan, Derandomization of auctions (619–625).
Vladimir Trifonov, An \(O(\log n\log\log n)\) space algorithm for undirected st-connectivity (extended abstract) (626–633); Scott Aaronson, The complexity of agreement (634–643); Yael Tauman Kalai, YehudaLindell and Manoj Prabhakaran, Concurrent general composition of secure protocols in the timing model (644–653); Yevgeniy Dodis and Adam Smith, Correcting errors without leaking partial information (654–663); Thomas Holenstein, Key agreement from weak bit agreement (664–673); FerdinandoCicalese and Eduardo Sany Laber, A new strategy for querying priced information (674–683); Nir Ailon, MosesCharikar and Alantha Newman, Aggregating inconsistent information: ranking and clustering (684–693); DimitrisAchlioptas, Aaron Clauset, David Kempe and Cristopher Moore, On the bias of traceroute sampling or, power-law degree distributions in regular graphs (694–703); Christian Scheideler, How to spread adversarial nodes? Rotate! (704–713); Eli Gafni, Rachid Guerraouiand Bastian Pochon, From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement (714–722).
Prasad Jayanti, An optimal multi-writer snapshot algorithm (extended abstract) (723–732); Bogdan S. Chlebus and Dariusz R. Kowalski, Cooperative asynchronous update of shared memory (733–739); Johan Håstad, Every 2-CSP allows nontrivial approximation (740–746); W. Fernandez de la Vega, Ravi Kannan, MarekKarpinski and Santosh Vempala, Tensor decomposition and approximation schemes for constraint satisfaction problems (747–754); Klaus Jansen and Rob van Stee, On strip packing with rotations (755–761).
The articles of this volume will not be indexed individually. The preceding conference has been reviewed (see Zbl 1074.68504).