51. FOCS 2010: Las Vegas, Nevada, USA

• Nikhil Bansal:
  Constructive Algorithms for Discrepancy Minimization. 3-10
  
• Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson:
  Bounded Independence Fools Degree-2 Threshold Functions. 11-20
  
• Nitin Saxena, C. Seshadhri:
  From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits. 21-29
  
• Joshua Brody, Elad Verbin:
  The Coin Problem and Pseudorandomness for Branching Programs. 30-39
  
• Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff:
  Pseudorandom Generators for Regular Branching Programs. 40-47
  
• Cynthia Dwork, Guy N. Rothblum, Salil P. Vadhan:
  Boosting and Differential Privacy. 51-60
  
• Moritz Hardt, Guy N. Rothblum:
  A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis. 61-70
  
• Hai Brenner, Kobbi Nissim:
  Impossibility of Differentially Private Universally Optimal Mechanisms. 71-80
  
• Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan:
  The Limits of Two-Party Differential Privacy. 81-90
  
• Ankur Moitra, Gregory Valiant:
  Settling the Polynomial Learnability of Mixtures of Gaussians. 93-102
  
• Mikhail Belkin, Kaushik Sinha:
  Polynomial Learning of Distribution Families. 103-112
  
• Karl Wimmer:
  Agnostically Learning under Permutation Invariant Distributions. 113-122
  
• Santosh Vempala:
  Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces. 123
  
• Santosh Vempala:
  Learning Convex Concepts from Gaussian Distributions with PCA. 124-130
  
• Zdenek Dvorak, Daniel Král, Robin Thomas:
  Deciding First-Order Properties for Sparse Graphs. 133-142
  
• Michael Elberfeld, Andreas Jakoby, Till Tantau:
  Logspace Versions of the Theorems of Bodlaender and Courcelle. 143-152
  
• Ken-ichi Kawarabayashi, Bruce A. Reed:
  A Separator Theorem in Minor-Closed Classes. 153-162
  
• Anastasios Sidiropoulos:
  Optimal Stochastic Planarization. 163-170
  
• Andreas Björklund:
  Determinant Sums for Undirected Hamiltonicity. 173-182
  
• Rahul Santhanam:
  Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability. 183-192
  
• Benjamin Rossman:
  The Monotone Complexity of k-clique on Random Graphs. 193-201
  
• Emanuele Viola:
  The Complexity of Distributions. 202-211
  
• Irit Dinur, Subhash Khot, Will Perkins, Muli Safra:
  Hardness of Finding Independent Sets in Almost 3-Colorable Graphs. 212-221
  
• Noga Alon, Raphael Yuster:
  Solving Linear Systems through Nested Dissection. 225-234
  
• Ioannis Koutis, Gary L. Miller, Richard Peng:
  Approaching Optimality for Solving SDD Linear Systems. 235-244
  
• Aleksander Madry:
  Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs. 245-254
  
• Konstantin Makarychev, Yury Makarychev:
  Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability. 255-264
  
• Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra:
  Vertex Sparsifiers and Abstract Rounding Algorithms. 265-274
  
• Matthew Andrews:
  Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions. 277-286
  
• Allan Sly:
  Computational Transition at the Uniqueness Threshold. 287-296
  
• Amit Kumar, Ravindran Kannan:
  Clustering with Spectral Norm and the k-Means Algorithm. 299-308
  
• Pranjal Awasthi, Avrim Blum, Or Sheffet:
  Stability Yields a PTAS for k-Median and k-Means Clustering. 309-318
  
• Marcus Isaksson, Guy Kindler, Elchanan Mossel:
  The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem. 319-328
  
• Amit Deshpande, Luis Rademacher:
  Efficient Volume Sampling for Row/Column Subset Selection. 329-338
  
• Noga Alon:
  A Non-linear Lower Bound for Planar Epsilon-Nets. 341-346
  
• Bartlomiej Bosek, Tomasz Krawczyk:
  The Sub-exponential Upper Bound for On-Line Chain Partitioning. 347-354
  
• Natan Rubin, Haim Kaplan, Micha Sharir:
  Improved Bounds for Geometric Permutations. 355-364
  
• Giuseppe Di Battista, Fabrizio Frati, János Pach:
  On the Queue Number of Planar Graphs. 365-374
  
• Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak:
  Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. 377-386
  
• Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, Andrew McGregor:
  Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. 387-396
  
• Bernhard Haeupler, Barna Saha, Aravind Srinivasan:
  New Constructive Aspects of the Lovasz Local Lemma. 397-406
  
• Nikhil Bansal, Kirk Pruhs:
  The Geometry of Scheduling. 407-414
  
• David Doty, Matthew J. Patitz, Dustin Reishus, Robert T. Schweller, Scott M. Summers:
  Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature. 417-426
  
• Jin-yi Cai, Pinyan Lu, Mingji Xia:
  Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP. 427-436
  
• Jin-yi Cai, Xi Chen:
  A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights. 437-446
  
• Kenneth L. Clarkson, Elad Hazan, David P. Woodruff:
  Sublinear Optimization for Machine Learning. 449-457
  
• Michael Saks, C. Seshadhri:
  Estimating the Longest Increasing Sequence in Polylogarithmic Time. 458-467
  
• Gilad Tsur, Dana Ron:
  Testing Properties of Sparse Images. 468-477
  
• Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira:
  A Unified Framework for Testing Linear-Invariant Properties. 478-487
  
• Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman:
  Optimal Testing of Reed-Muller Codes. 488-497
  
• Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz, Vinod Vaikuntanathan:
  Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage. 501-510
  
• Yevgeniy Dodis, Kristiyan Haralambiev, Adriana López-Alt, Daniel Wichs:
  Cryptography against Continuous Memory Attacks. 511-520
  
• Allison B. Lewko, Brent Waters:
  On the Insecurity of Parallel Repetition for Leakage Resilience. 521-530
  
• Hoeteck Wee:
  Black-Box, Round-Efficient Secure Computation via Non-malleability Amplification. 531-540
  
• Ran Canetti, Huijia Lin, Rafael Pass:
  Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions. 541-550
  
• Aaron Potechin:
  Bounds on Monotone Switching Networks for Directed Connectivity. 553-562
  
• Sanjeev Arora, Boaz Barak, David Steurer:
  Subexponential Algorithms for Unique Games and Related Problems. 563-572
  
• Chandra Chekuri, Jan Vondrák, Rico Zenklusen:
  Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. 575-584
  
• Matthew Andrews, Spyridon Antonakopoulos, Lisa Zhang:
  Minimum-Cost Network Design with (Dis)economies of Scale. 585-592
  
• Ashish Goel, Ian Post:
  One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk. 593-600
  
• Glencora Borradaile, Piotr Sankowski, Christian Wulff-Nilsen:
  Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time. 601-610
  
• Hemanta K. Maji, Manoj Prabhakaran, Amit Sahai:
  On the Computational Complexity of Coin Flipping. 613-622
  
• Ronen Gradwohl, Noam Livne, Alon Rosen:
  Sequential Rationality in Cryptographic Protocols. 623-632
  
• Aram Wettroth Harrow, Ashley Montanaro:
  An Efficient Test for Product States with Applications to Quantum Merlin-Arthur Games. 633-642
  
• Virginia Vassilevska Williams, Ryan Williams:
  Subcubic Equivalences between Path, Matrix and Triangle Problems. 645-654
  
• Oren Weimann, Raphael Yuster:
  Replacement Paths via Fast Matrix Multiplication. 655-662
  
• Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick:
  All-Pairs Shortest Paths in O(n²) Time with High Probability. 663-672
  
• Ran Duan, Seth Pettie:
  Approximating Maximum Weight Matching in Near-Linear Time. 673-682
  
• Parikshit Gopalan:
  A Fourier-Analytic Approach to Reed-Muller Decoding. 685-694
  
• Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka:
  Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields. 695-704
  
• Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin:
  Matching Vector Codes. 705-714
  
• Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma:
  Local List Decoding with a Constant Number of Queries. 715-722
  
• Venkatesan Guruswami, Adam Smith:
  Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. 723-732
  
• Renato Paes Leme, Éva Tardos:
  Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction. 735-744
  
• David Kempe, Mahyar Salek, Cristopher Moore:
  Frugal and Truthful Auctions for Vertex Covers, Flows and Cuts. 745-754
  
• Ning Chen, Edith Elkind, Nick Gravin, Fedor Petrov:
  Frugal Mechanism Design via Spectral Techniques. 755-764
  
• Yaron Singer:
  Budget Feasible Mechanisms. 765-774
  
• Shaddin Dughmi, Tim Roughgarden:
  Black-Box Randomized Reductions in Algorithmic Mechanism Design. 775-784
  
• Yuriy Arbitman, Moni Naor, Gil Segev:
  Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation. 787-796
  
• Shachar Lovett, Ely Porat:
  A Lower Bound for Dynamic Approximate Membership Data Structures. 797-804
  
• Rina Panigrahy, Kunal Talwar, Udi Wieder:
  Lower Bounds on Near Neighbor Search via Metric Expansion. 805-814
  
• Mihai Patrascu, Liam Roditty:
  Distance Oracles beyond the Thorup-Zwick Bound. 815-823
  

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