2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. (English) Zbl 1293.00016

Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). xiv, 778 p. (2009).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For FOCS 2008, see [Zbl 1255.68014].
Indexed articles:
Moitra, Ankur, Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size, 3-12 [Zbl 1292.05251]
Kelner, Jonathan A.; Madry, Aleksander, Faster generation of random spanning trees, 13-21 [Zbl 1292.05248]
Hassidim, Avinatan; Kelner, Jonathan A.; Nguyen, Huy N.; Onak, Krzysztof, Local graph partitions for approximation and testing, 22-31 [Zbl 1292.68126]
Englert, Matthias; Räcke, Harald, Oblivious routing for the \(L_p\)-norm, 32-40 [Zbl 1292.68125]
Chattopadhyay, Arkadev; Wigderson, Avi, Linear systems over composite moduli, 43-52 [Zbl 1292.68072]
Beame, Paul; Huynh-Ngoc, Dang-Trinh, Multiparty communication complexity and threshold circuit size of \(\mathrm{AC}^0\), 53-62 [Zbl 1292.68071]
Kushilevitz, Eyal; Weinreb, Enav, The communication complexity of set-disjointness with small sets and \(0\)-\(1\) intersection, 63-72 [Zbl 1292.68077]
Basu, Saugata; Zell, Thierry, Polynomial hierarchy, Betti numbers and a real analogue of Toda’s theorem, 73-82 [Zbl 1292.14036]
Doty, David, Randomized self-assembly for exact shapes, 85-94 [Zbl 1292.68155]
Gottesman, Daniel; Irani, Sandy, The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems, 95-104 [Zbl 1292.68067]
Chakrabarty, Deeparnab; Chuzhoy, Julia; Khanna, Sanjeev, On allocating goods to maximize fairness, 107-116 [Zbl 1292.91102]
Feldman, Jon; Mehta, Aranyak; Mirrokni, Vahab; Muthukrishnan, S., Online stochastic matching: beating \(1-\frac1e\), 117-126 [Zbl 1292.68173]
Afshani, Peyman; Barbay, Jérémy; Chan, Timothy M., Instance-optimal geometric algorithms, 129-138 [Zbl 1292.68142]
Buchin, Kevin; Mulzer, Wolfgang, Delaunay triangulations in \({O(\mathrm{sort}(n))}\) time and more, 139-148 [Zbl 1292.68143]
Afshani, Peyman; Arge, Lars; Larsen, Kasper Dalgaard, Orthogonal range reporting in three and higher dimensions, 149-158 [Zbl 1292.68141]
Gibson, Matt; Varadarajan, Kasturi, Decomposing coverings and the planar sensor cover problem, 159-168 [Zbl 1292.68144]
Diakonikolas, Ilias; Gopalan, Parikshit; Jaiswal, Ragesh; Servedio, Rocco A.; Viola, Emanuele, Bounded independence fools halfspaces, 171-180 [Zbl 1292.68111]
Dvir, Zeev; Kopparty, Swastik; Saraf, Shubhangi; Sudan, Madhu, Extensions to the method of multiplicities, with applications to Kakeya sets and mergers, 181-190 [Zbl 1292.68119]
Ben-Aroya, Avraham; Ta-Shma, Amnon, Constructing small-bias sets from algebraic-geometric codes, 191-197 [Zbl 1292.94182]
Kayal, Neeraj; Saraf, Shubhangi, Blackbox polynomial identity testing for depth 3 circuits, 198-207 [Zbl 1292.68095]
Kannan, Ravindran, A new probability inequality using typical moments and concentration results, 211-220 [Zbl 1292.68113]
Unger, Falk, A probabilistic inequality with applications to threshold direct-product theorems, 221-229 [Zbl 1292.68116]
Alon, Noga; Lubetzky, Eyal; Gurel-Gurevich, Ori, Choice-memory tradeoff in allocations, 230-238 [Zbl 1292.60010]
Haitner, Iftach, A parallel repetition theorem for any interactive argument, 241-250 [Zbl 1292.68022]
Deng, Yi; Goyal, Vipul; Sahai, Amit, Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy, 251-260 [Zbl 1292.94054]
Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail; Sahai, Amit, Extracting correlations, 261-270 [Zbl 1292.94080]
Chen, Xi; Dai, Decheng; Du, Ye; Teng, Shang-Hua, Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities, 273-282 [Zbl 1292.91113]
Kintali, Shiva; Poplawski, Laura J.; Rajaraman, Rajmohan; Sundaram, Ravi; Teng, Shang-Hua, Reducibility among fractional stability problems, 283-292 [Zbl 1292.68076]
Azar, Yossi; Birnbaum, Benjamin; Celis, L. Elisa; Devanur, Nikhil R.; Peres, Yuval, Convergence of local dynamics to balanced outcomes in exchange networks, 293-302 [Zbl 1292.91122]
Montanari, Andrea; Saberi, Amin, Convergence to equilibrium in local interaction games, 303-312 [Zbl 1292.91036]
Porat, Benny; Porat, Ely, Exact and approximate pattern matching in the streaming model, 315-323 [Zbl 1292.68174]
Andoni, Alexandr; Do Ba, Khanh; Indyk, Piotr; Woodruff, David, Efficient sketches for Earth-mover distance, with applications, 324-330 [Zbl 1292.68160]
Chierichetti, Flavio; Kumar, Ravi; Lattanzi, Silvio; Panconesi, Alessandro; Raghavan, Prabhakar, Models for the compressible web, 331-340 [Zbl 1292.05238]
Sherstov, Alexander A., The intersection of two halfspaces has high threshold degree, 343-362 [Zbl 1292.68100]
Sherman, Jonah, Breaking the multicommodity flow barrier for \(O(\sqrt{\log n})\)-approximations to sparsest cut, 363-372 [Zbl 1292.68172]
Feldman, Vitaly, A complete characterization of statistical query learning with applications to evolvability, 375-384 [Zbl 1292.68096]
Feldman, Vitaly; Guruswami, Venkatesan; Raghavendra, Prasad; Wu, Yi, Agnostic learning of monomials by halfspaces is hard, 385-394 [Zbl 1292.68097]
Kalai, Adam Tauman; Samorodnitsky, Alex; Teng, Shang-Hua, Learning and smoothed analysis, 395-404 [Zbl 1292.68132]
Arthur, David; Manthey, Bodo; Röglin, Heiko, \(k\)-means has polynomial smoothed complexity, 405-414 [Zbl 1292.68187]
Nutov, Zeev, Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions, 417-426 [Zbl 1292.68170]
Archer, Aaron; Bateni, MohammadHossein; Hajiaghayi MohammadTaghi; Karloff, Howard, Improved approximation algorithms for prize-collecting Steiner tree and TSP, 427-436 [Zbl 1292.68161]
Chuzhoy, Julia; Khanna, Sanjeev, An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design, 437-441 [Zbl 1292.68090]
Goel, Ashish; Post, Ian, An oblivious \(O(1)\)-approximation for single source buy-at-bulk, 442-450 [Zbl 1292.68166]
Bansal, Nikhil; Khot, Subhash, Optimal long code test with one free bit, 453-462 [Zbl 1292.68081]
Meir, Or, Combinatorial PCPs with efficient verifiers, 463-471 [Zbl 1292.68078]
Dinur, Irit; Harsha, Prahladh, Composition of low-error 2-query PCPs using decodable PCPs, 472-481 [Zbl 1292.68083]
Kalyanaraman, Shankar; Umans, Christopher, The complexity of rationalizing network formation, 485-494 [Zbl 1292.91151]
Chakraborty, Tanmoy; Huang, Zhiyi; Khanna, Sanjeev, Dynamic and non-uniform pricing strategies for revenue maximization, 495-504 [Zbl 1292.91069]
Dobzinski, Shahar; Dughmi, Shaddin, On the power of randomization in algorithmic mechanism design, 505-514 [Zbl 1292.91081]
Broadbent, Anne; Fitzsimons, Joseph; Kashefi, Elham, Universal blind quantum computation, 517-526 [Zbl 1292.81023]
Chailloux, André; Kerenidis, Iordanis, Optimal quantum strong coin flipping, 527-533 [Zbl 1292.81029]
Jain, Rahul; Upadhyay, Sarvagya; Watrous, John, Two-message quantum interactive proofs are in PSPACE, 534-543 [Zbl 1292.68068]
Reichardt, Ben W., Span programs and quantum query complexity: the general adversary bound is nearly tight for every Boolean function, 544-551 [Zbl 1292.68070]
Cheeger, Jeff; Kleiner, Bruce; Naor, Assaf, A \((\log n)^{\Omega(1)}\) integrality gap for the sparsest cut SDP, 555-564 [Zbl 1291.90318]
Khot, Subhash; Saket, Rishi, SDP integrality gaps with local \(\ell_1\)-embeddability, 565-574 [Zbl 1292.90228]
Raghavendra, Prasad; Steurer, David, Integrality gaps for strong SDP relaxations of unique games, 575-585 [Zbl 1292.90230]
Raghavendra, Prasad; Steurer, David, How to round any CSP, 586-594 [Zbl 1292.90231]
Barto, Libor; Kozik, Marcin, Constraint satisfaction problems of bounded width, 595-603 [Zbl 1292.68088]
Myers, Steven; Shelat, Abhi, Bit encryption is complete, 607-616 [Zbl 1292.94119]
Kalai, Yael Tauman; Li, Xin; Rao, Anup, 2-source extractors under computational assumptions and cryptography with defective randomness, 617-626 [Zbl 1292.94088]
Bodlaender, Hans L.; Fomin, Fedor V.; Lokshtanov, Daniel; Penninkx, Eelko; Saurabh, Saket; Thilikos, Dimitrios M., (Meta) kernelization, 629-638 [Zbl 1292.68089]
Kawarabayashi, Ken-ichi, Planarity allowing few error vertices in linear time, 639-648 [Zbl 1292.68093]
Vondrák, Jan, Symmetry and approximability of submodular maximization problems, 651-670 [Zbl 1292.90262]
Iwata, Satoru; Nagano, Kiyohito, Submodular function minimization under covering constraints, 671-680 [Zbl 1292.68168]
Röglin, Heiko; Teng, Shang-Hua, Smoothed analysis of multiobjective optimization, 681-690 [Zbl 1292.90273]
Bernstein, Aaron, Fully dynamic \((2+\epsilon)\) approximate all-pairs shortest paths with fast query and close to linear update time, 693-702 [Zbl 1292.05243]
Sommer, Christian; Verbin, Elad; Yu, Wei, Distance oracles for sparse graphs, 703-712 [Zbl 1292.05253]
Hon, Wing-Kai; Shah, Rahul; Vitter, Jeffrey Scott, Space-efficient framework for top-\(k\) string retrieval problems, 713-722 [Zbl 1292.68182]
O’Donnell, Ryan; Wimmer, Karl, KKL, Kruskal-Katona, and monotone nets, 725-734 [Zbl 1292.68099]
Kelner, Jonathan A.; Lee, James R.; Price, Gregory N.; Teng, Shang-Hua, Higher eigenvalues of graphs, 735-744 [Zbl 1292.05172]
Bansal, Nikhil; Williams, Ryan, Regularity lemmas and combinatorial algorithms, 745-754 [Zbl 1292.05242]
Goel, Gagan; Karande, Chinmay; Tripathi, Pushkar; Wang, Lei, Approximability of combinatorial problems with multi-agent submodular cost functions, 755-764 [Zbl 1292.05245]
Jayram, T. S.; Woodruff, David P., The data stream space complexity of cascaded norms, 765-774 [Zbl 1292.68087]


00B25 Proceedings of conferences of miscellaneous specific interest
68-06 Proceedings, conferences, collections, etc. pertaining to computer science
05-06 Proceedings, conferences, collections, etc. pertaining to combinatorics
90-06 Proceedings, conferences, collections, etc. pertaining to operations research and mathematical programming


Zbl 1255.68014
Full Text: Link