42. STOC 2010: Cambridge, Massachusetts, USA

• 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
  
• Frank Thomson Leighton, Ankur Moitra:
  Extensions and limits to vertex sparsification. 47-56
  
• Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng:
  Subgraph sparsification and nearly optimal ultrasparsifiers. 57-66
  
• Boaz Barak, Mark Braverman, Xi Chen, Anup Rao:
  How to compress interactive communication. 67-76
  
• Hartmut Klauck:
  A strong direct product theorem for disjointness. 77-86
  
• Paul Beame, Trinh Huynh, Toniann Pitassi:
  Hardness amplification in proof complexity. 87-96
  
• 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, Andrew Drucker:
  A full characterization of quantum advice. 131-140
  
• Scott Aaronson:
  BQP and the polynomial hierarchy. 141-150
  
• Andris Ambainis, Julia Kempe, Or Sattath:
  A quantum lovász local lemma. 151-160
  
• Anindya De, Thomas Vidick:
  Near-optimal extractors against quantum storage. 161-170
  
• Benny Applebaum, Boaz Barak, Avi Wigderson:
  Public-key cryptography from different assumptions. 171-180
  
• Miklós Ajtai:
  Oblivious RAMs without cryptogrpahic assumptions. 181-190
  
• Vipul Goyal, Abhishek Jain:
  On the round complexity of covert computation. 191-200
  
• Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan:
  Detecting high log-densities: an O(n^1/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
  
• Ramamohan Paturi, Pavel Pudlák:
  On the complexity of circuit satisfiability. 241-250
  
• 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
  
• Vladimir Braverman, Rafail Ostrovsky:
  Measuring independence of datasets. 271-280
  
• Vladimir Braverman, Rafail Ostrovsky:
  Zero-one frequency laws. 281-290
  
• James B. Orlin:
  Improved algorithms for computing fisher's market clearing prices: computing fisher's market clearing prices. 291-300
  
• Jason D. Hartline, Brendan Lucier:
  Bayesian algorithmic mechanism design. 301-310
  
• Shuchi Chawla, Jason D. Hartline, David L. Malec, Balasubramanian Sivan:
  Multi-parameter mechanism design and sequential posted pricing. 311-320
  
• Daniel Lokshtanov, Jesper Nederlof:
  Saving space by algebraization. 321-330
  
• Elad Haramaty, Amir Shpilka:
  On the structure of cubic and quartic polynomials. 331-340
  
• Anirban Dasgupta, Ravi Kumar, Tamás Sarlós:
  A sparse Johnson: Lindenstrauss transform. 341-350
  
• 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
  
• Jon Lee, Maxim Sviridenko, Jan Vondrák:
  Matroid matching: the power of local search. 369-378
  
• 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
  
• Raghu Meka, David Zuckerman:
  Pseudorandom generators for polynomial threshold functions. 427-436
  
• 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
  
• Krzysztof Onak, Ronitt Rubinfeld:
  Maintaining a large matching and a small vertex cover. 457-464
  
• Ran Duan, Seth Pettie:
  Connectivity oracles for failure prone graphs. 465-474
  
• Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss:
  Approximate sparse recovery: optimizing time and measurements. 475-484
  
• Guillem Godoy, Omer Giménez, Lander Ramos, Carme Àlvarez:
  The HOM problem is decidable. 485-494
  
• Akitoshi Kawamura, Stephen A. Cook:
  Complexity theory for operators in analysis. 495-502
  
• Peter Bürgisser, Felipe Cucker:
  Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem. 503-512
  
• Fabian Kuhn, Nancy A. Lynch, Rotem Oshman:
  Distributed computation in dynamic networks. 513-522
  
• 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
  
• Prahladh Harsha, Adam Klivans, Raghu Meka:
  An invariance principle for polytopes. 543-552
  
• 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
  
• Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous:
  QIP = PSPACE. 573-582
  
• Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, Laura Sanità:
  An improved LP-based approximation for steiner tree. 583-592
  
• Yevgeniy Dodis, Mihai Patrascu, Mikkel Thorup:
  Changing base without losing space. 593-602
  
• Mihai Patrascu:
  Towards polynomial lower bounds for dynamic problems. 603-610
  
• Pierre Fraigniaud, Amos Korman:
  An optimal ancestry scheme and small universal posets. 611-620
  
• James R. Lee, Mohammad Moharrami:
  Bilipschitz snowflakes and metrics of negative type. 621-630
  
• 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
  
• Vikraman Arvind, Srikanth Srinivasan:
  On the hardness of the noncommutative determinant. 677-686
  
• Ken-ichi Kawarabayashi, Paul Wollan:
  A shorter proof of the graph minor algorithm: the unique linkage theorem. 687-694
  
• Ken-ichi Kawarabayashi, Bruce A. Reed:
  Odd cycle packing. 695-704
  
• Moritz Hardt, Kunal Talwar:
  On the geometry of differential privacy. 705-714
  
• Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum:
  Differential privacy under continual observation. 715-724
  
• Martin E. Dyer, David Richerby:
  On the complexity of #CSP. 725-734
  
• 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
  
• Prasad Raghavendra, David Steurer:
  Graph expansion and the unique games conjecture. 755-764
  
• Aaron Roth, Tim Roughgarden:
  Interactive privacy via the median mechanism. 765-774
  
• 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
  

Last update Fri May 25 08:42:24 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page