zbMATH — the first resource for mathematics

Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. (English) Zbl 1257.68017
New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). xiii, 736 p. (2009).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding symposium see [Zbl 1147.68001].
Indexed articles:
Arora, Sanjeev; Daskalakis, Constantinos; Steurer, David, Message passing algorithms and improved LP decoding, 3-12 [Zbl 1304.94117]
Gopalan, Parikshit; Guruswami, Venkatesan; Raghavendra, Prasad, List decoding tensor products and interleaved codes, 13-22 [Zbl 1304.94119]
Guruswami, Venkatesan, Artin automorphisms, cyclotomic function fields, and folded list-decodable codes, 23-32 [Zbl 1304.94116]
Cheng, Qi; Wan, Daqing, A deterministic reduction for the gap minimum distance problem (extended abstract), 33-38 [Zbl 1304.94111]
Efremenko, Klim, 3-query locally decodable codes of subexponential length, 39-44 [Zbl 1304.94124]
Sellie, Linda, Exact learning of random DNF over the uniform distribution, 45-54 [Zbl 1304.68088]
Babai, László; Beals, Robert; Seress, Ákos, Polynomial-time theory of matrix groups, 55-64 [Zbl 1304.68065]
Ben-Sasson, Eli; Kopparty, Swastik, Affine dispersers from subspace polynomials, 65-74 [Zbl 1304.68135]
Daskalakis, Constantinos; Papadimitriou, Christos H., On oblivious PTAS’s for Nash equilibrium, 75-84 [Zbl 1304.91014]
Gafni, Eli, The extended BG-simulation and the characterization of \(t\)-resiliency, 85-92 [Zbl 1304.68133]
Cardinal, Jean; Fiorini, Samuel; Joret, Gwenaël; Jungers, Raphaël M.; Munro, J. Ian, An efficient algorithm for partial order production, 93-100 [Zbl 1304.68068]
Bernstein, Aaron; Karger, David, A nearly optimal oracle for avoiding failed vertices and edges, 101-110 [Zbl 1304.68066]
Barenboim, Leonid; Elkin, Michael, Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time, 111-120 [Zbl 1304.05129]
Friedrich, Tobias; Sauerwald, Thomas, Near-perfect load balancing by randomized rounding, 121-130 [Zbl 1304.68019]
Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi, New direct-product testers and \(2\)-query PCPs, 131-140 [Zbl 1304.68048]
Goldreich, Oded; Ron, Dana, On proximity oblivious testing, 141-150 [Zbl 1304.05134]
Blais, Eric, Testing juntas nearly optimally, 151-158 [Zbl 1304.68059]
Shapira, Asaf, Green’s conjecture and testing linear-invariant properties, 159-166 [Zbl 1304.68204]
Gentry, Craig, Fully homomorphic encryption using ideal lattices, 169-178 [Zbl 1304.94059]
Lin, Huijia; Pass, Rafael; Venkitasubramaniam, Muthuramakrishnan, A unified framework for concurrent security, universal composability from stand-alone non-malleability, 179-188 [Zbl 1304.68017]
Lin, Huijia; Pass, Rafael, Non-malleability amplification, 189-198 [Zbl 1304.94073]
Andoni, Alexandr; Onak, Krzysztof, Approximating edit distance in near-linear time, 199-204 [Zbl 1304.68206]
Clarkson, Kenneth L.; Woodruff, David P., Numerical linear algebra in the streaming model, 205-214 [Zbl 1304.65138]
Nguyen, Nam H.; Do, Thong T.; Tran, Trac D., A fast and efficient algorithm for low-rank approximation of a matrix, 215-224 [Zbl 1304.65140]
Yoshida, Yuichi; Yamamoto, Masaki; Ito, Hiro, An improved constant-time approximation algorithm for maximum matchings, 225-234 [Zbl 1304.05112]
Andersen, Reid; Peres, Yuval, Finding sparse cuts locally using evolving sets, 235-244 [Zbl 1304.05128]
Lee, James R.; Sidiropoulos, Anastasios, On the geometry of graphs with a forbidden minor, 245-254 [Zbl 1304.05137]
Batson, Joshua D.; Spielman, Daniel A.; Srivastava, Nikhil, Twice-Ramanujan sparsifiers, 255-262 [Zbl 1304.05130]
Trevisan, Luca, Max CUT and the smallest eigenvalue, 263-272 [Zbl 1304.05140]
Chambers, Erin W.; Erickson, Jeff; Nayyeri, Amir, Homology flows, cohomology cuts, 273-282 [Zbl 1304.05065]
Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury, Integrality gaps for Sherali-Adams relaxations, 283-292 [Zbl 1304.90143]
Mathieu, Claire; Sinclair, Alistair, Sherali-Adams relaxations of the matching polytope, 293-302 [Zbl 1304.90144]
Tulsiani, Madhur, CSP gaps and reductions in the Lasserre hierarchy, 303-312 [Zbl 1304.90157]
Karpinski, Marek; Schudy, Warren, Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems, 313-322 [Zbl 1304.68218]
Lee, Jon; Mirrokni, Vahab S.; Nagarajan, Viswanath; Sviridenko, Maxim, Non-monotone submodular maximization under matroid and knapsack constraints, 323-332 [Zbl 1304.90173]
Peikert, Chris, Public-key cryptosystems from the worst-case shortest vector problem (extended abstract), 333-342 [Zbl 1304.94079]
Moser, Robin A., A constructive proof of the Lovász local lemma, 343-350 [Zbl 1304.68079]
Ghosh, Arpita; Roughgarden, Tim; Sundararajan, Mukund, Universally utility-maximizing privacy mechanisms, 351-360 [Zbl 1304.94060]
Feldman, Dan; Fiat, Amos; Kaplan, Haim; Nissim, Kobbi, Private coresets, 361-370 [Zbl 1304.94054]
Dwork, Cynthia; Lei, Jing, Differential privacy and robust statistics, 371-380 [Zbl 1304.94049]
Dwork, Cynthia; Naor, Moni; Reingold, Omer; Rothblum, Guy N.; Vadhan, Salil, On the complexity of differentially private data release, efficient algorithms and hardness results, 381-390 [Zbl 1304.94050]
Liu, Yi-Kai, Quantum algorithms using the curvelet transform, 391-400 [Zbl 1304.68052]
Ta-Shma, Amnon, Short seed extractors against quantum storage, 401-408 [Zbl 1304.68053]
Cleve, Richard; Gottesman, Daniel; Mosca, Michele; Somma, Rolando D.; Yonge-Mallo, David, Efficient discrete-time simulations of continuous-time quantum query algorithms, 409-416 [Zbl 1304.68051]
Aharonov, Dorit; Arad, Itai; Landau, Zeph; Vazirani, Umesh, The detectability lemma and quantum gap amplification, 417-426 [Zbl 1304.68049]
Lattanzi, Silvio; Sivakumar, D., Affiliation networks, 427-434 [Zbl 1304.05127]
Chechik, S.; Langberg, M.; Peleg, David; Roditty, L., Fault-tolerant spanners for general graphs, 435-444 [Zbl 1304.68138]
Kawarabayashi, Ken-ichi; Reed, Bruce, Hadwiger’s conjecture is decidable, 445-454 [Zbl 1304.05047]
Vassilevska, Virginia; Williams, Ryan, Finding, minimizing, and counting weighted subgraphs, 455-464 [Zbl 1304.05102]
Kushilevitz, Eyal; Weinreb, Enav, On the complexity of communication complexity, 465-474 [Zbl 1304.68077]
Viola, Emanuele, Bit-probe lower bounds for succinct data structures, 475-482 [Zbl 1304.68035]
Austrin, Per; Håstad, Johan, Randomly supported independence and resistance, 483-492 [Zbl 1304.68134]
O’Donnell, Ryan; Wu, Yi, Conditional hardness for satisfiable 3-CSPs, 493-502 [Zbl 1304.68080]
Chen, Jing; Micali, Silvio, A new approach to auctions and resilient mechanism design, 503-512 [Zbl 1304.91083]
Roughgarden, Tim, Intrinsic robustness of the price of anarchy, 513-522 [Zbl 1304.91019]
Even-dar, Eyal; Mansour, Yishay; Nadav, Uri, On the convergence of regret minimization dynamics in concave games, 523-532 [Zbl 1304.91015]
Kleinberg, Robert; Piliouras, Georgios; Tardos, Eva, Multiplicative updates outperform generic no-regret learning in congestion games (extended abstract), 533-542 [Zbl 1304.91017]
Bateni, MohammadHossein; Charikar, Moses; Guruswami, Venkatesan, MaxMin Allocation via degree lower-bounded arborescences, 543-552 [Zbl 1304.91143]
Montenegro, Ravi; Tetali, Prasad, How long does it take to catch a wild kangaroo?, 553-560 [Zbl 1304.94103]
Kannan, Ravi; Narayanan, Hariharan, Random walks on polytopes and an affine interior point method for linear programming, 561-570 [Zbl 1304.90138]
Martinelli, Fabio; Sinclair, Alistair, Mixing time for the solid-on-solid model, 571-580 [Zbl 1304.82071]
Sly, Allan, Reconstruction for the Potts model, 581-590 [Zbl 1304.68137]
Dietzfelbinger, Martin; Woelfel, Philipp, Tight lower bounds for greedy routing in uniform small world rings, 591-600 [Zbl 1304.68014]
Dodis, Yevgeniy; Wichs, Daniel, Non-malleable extractors and symmetric key cryptography from weak secrets, 601-610 [Zbl 1304.94048]
Haitner, Iftach; Reingold, Omer; Vadhan, Salil; Wee, Hoeteck, Inaccessible entropy, 611-620 [Zbl 1304.94014]
Dodis, Yevgeniy; Kalai, Yael Tauman; Lovett, Shachar, On cryptography with auxiliary input, 621-630 [Zbl 1304.94046]
Chalopin, Jérémie; Gonçalves, Daniel, Every planar graph is the intersection graph of segments in the plane (extended abstract), 631-638 [Zbl 1304.05115]
Aronov, Boris; Ezra, Esther; Shair, Micha, Small-size \({\varepsilon}\)-nets for axis-parallel rectangles and boxes, 639-648 [Zbl 1304.68181]
Rabani, Yuval; Shpilka, Amir, Explicit construction of a small epsilon-net for linear threshold functions, 649-658 [Zbl 1304.94136]
Gupta, Anupam; Kumar, Amit, A constant-factor approximation for stochastic Steiner forest, 659-668 [Zbl 1304.68217]
Azar, Yossi; Gamzu, Iftah; Yin, Xiaoxin, Multiple intents re-ranking, 669-678 [Zbl 1304.68037]
Chadha, Jivitej S.; Garg, Naveen; Kumar, Amit; Muralidhara, V. N., A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation, 679-684 [Zbl 1304.90089]
Gupta, Anupam; Krishnaswamy, Ravishankar; Ravi, R., Online and stochastic survivable network design, 685-694 [Zbl 1304.68139]
Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina, An axiomatic approach to algebrization, 695-704 [Zbl 1304.68055]
Kolaitis, Phokion G.; Kopparty, Swastik, Random graphs and the parity quantifier, 705-714 [Zbl 1304.03074]
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji, Holant problems and counting CSP, 715-724 [Zbl 1304.68067]
Kun, Gábor; Szegedy, Mario, A new line of attack on the dichotomy conjecture, 725-734 [Zbl 1304.68076]

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
94-06 Proceedings, conferences, collections, etc. pertaining to information and communication theory
00B25 Proceedings of conferences of miscellaneous specific interest
Full Text: DOI