42. STOC 2010: Cambridge, Massachusetts, USA
Leonard J. Schulman (Ed.): Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010. ACM 2010 ISBN 978-1-4503-0050-6- Ravindran Kannan: Spectral methods for matrices and tensors. 1-12
- Michel Talagrand: Are many small sets explicitly small? 13-36
- Andrea Montanari: Message passing algorithms: a success looking for theoreticians. 37-38
- Ashish Goel, Michael Kapralov, Sanjeev Khanna: Perfect matchings in o(n log n) time in regular bipartite graphs. 39-46
- Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng: Subgraph sparsification and nearly optimal ultrasparsifiers. 57-66
- Hartmut Klauck: A strong direct product theorem for disjointness. 77-86
- Pu Gao, Nicholas C. Wormald: Load balancing and orientability thresholds for random hypergraphs. 97-104
- Mohsen Bayati, David Gamarnik, Prasad Tetali: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. 105-114
- Hiroshi Hirai: The maximum multiflow problems with bounded fractionality. 115-120
- Aleksander Madry: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. 121-130
- Scott Aaronson: BQP and the polynomial hierarchy. 141-150
- Benny Applebaum, Boaz Barak, Avi Wigderson: Public-key cryptography from different assumptions. 171-180
- Miklós Ajtai: Oblivious RAMs without cryptogrpahic assumptions. 181-190
- Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan: Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. 201-210
- MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx: Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. 211-220
- Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy: Optimal homologous cycles, total unimodularity, and linear programming. 221-230
- Ryan Williams: Improving exhaustive search implies superpolynomial lower bounds. 231-240
- Holger Dell, Dieter van Melkebeek: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. 251-260
- Frédéric Magniez, Claire Mathieu, Ashwin Nayak: Recognizing well-parenthesized expressions in the streaming model. 261-270
- James B. Orlin: Improved algorithms for computing fisher's market clearing prices: computing fisher's market clearing prices. 291-300
- Shuchi Chawla, Jason D. Hartline, David L. Malec, Balasubramanian Sivan: Multi-parameter mechanism design and sequential posted pricing. 311-320
- Daniele Micciancio, Panagiotis Voulgaris: A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. 351-358
- Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro: Sorting under partial information (without the ellipsoid algorithm). 359-368
- Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala: Budget constrained auctions with heterogeneous items. 379-388
- Pierre Fraigniaud, George Giakkoupis: On the searchability of small-world networks with arbitrary underlying structure. 389-398
- Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi: Almost tight bounds for rumour spreading with conductance. 399-408
- Venkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the list-decodability of random linear codes. 409-416
- Swastik Kopparty, Shubhangi Saraf: Local list-decoding and testing of random linear codes from high error. 417-426
- Iftach Haitner, Omer Reingold, Salil P. Vadhan: Efficiency improvements in constructing pseudorandom generators from one-way functions. 437-446
- Elad Verbin, Qin Zhang: The limits of buffering: a tight lower bound for dynamic membership in the external memory model. 447-456
- Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss: Approximate sparse recovery: optimizing time and measurements. 475-484
- Peter Bürgisser, Felipe Cucker: Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem. 503-512
- Alexander A. Sherstov: Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. 523-532
- Ilias Diakonikolas, Prahladh Harsha, Adam Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan: Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. 533-542
- Adam Tauman Kalai, Ankur Moitra, Gregory Valiant: Efficiently learning mixtures of two Gaussians. 553-562
- László A. Végh: Augmenting undirected node-connectivity by one. 563-572
- Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità: An improved LP-based approximation for steiner tree. 583-592
- Mihai Patrascu: Towards polynomial lower bounds for dynamic problems. 603-610
- Prasad Raghavendra, David Steurer, Prasad Tetali: Approximations for the isoperimetric and spectral profile of graphs and related parameters. 631-640
- Kasturi Varadarajan: Weighted geometric set cover via quasi-uniform sampling. 641-648
- Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich: Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. 649-658
- Ran Raz: Tensor-rank and lower bounds for arithmetic formulas. 659-666
- Pavel Hrubes, Avi Wigderson, Amir Yehudayoff: Non-commutative circuits and the sum-of-squares problem. 667-676
- Ken-ichi Kawarabayashi, Paul Wollan: A shorter proof of the graph minor algorithm: the unique linkage theorem. 687-694
- Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum: Differential privacy under continual observation. 715-724
- Dániel Marx: Tractable hypergraph properties for constraint satisfaction and conjunctive queries. 735-744
- Ola Svensson: Conditional hardness of precedence constrained scheduling on identical machines. 745-754
- Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, Jonathan Ullman: The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. 775-784
- Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, Leonid Reyzin: Privacy amplification with asymptotically optimal entropy loss. 785-794
- Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz: Erratum for: on basing one-way functions on NP-hardness. 795-796
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team