default search action
51st FOCS 2010: Las Vegas, Nevada, USA
- 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA. IEEE Computer Society 2010, ISBN 978-0-7695-4244-7
- 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
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
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 S. Vempala:
Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces. 123 - Santosh S. Vempala:
Learning Convex Concepts from Gaussian Distributions with PCA. 124-130 - Zdenek Dvorák
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
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
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
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
The Sub-exponential Upper Bound for On-Line Chain Partitioning. 347-354 - Natan Rubin
Improved Bounds for Geometric Permutations. 355-364 - Giuseppe Di Battista
On the Queue Number of Planar Graphs. 365-374 - Alexandr Andoni, Robert Krauthgamer
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. 377-386 - Amit Chakrabarti
Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. 387-396 - Bernhard Haeupler
New Constructive Aspects of the Lovasz Local Lemma. 397-406 - Nikhil Bansal, Kirk Pruhs:
The Geometry of Scheduling. 407-414 - David Doty
Strong Fault-Tolerance for Self-Assembly with Fuzzy Temperature. 417-426 - Jin-yi Cai, Pinyan Lu
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
Sublinear Optimization for Machine Learning. 449-457 - Michael E. 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
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
Sequential Rationality in Cryptographic Protocols. 623-632 - Aram W. Harrow
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
Replacement Paths via Fast Matrix Multiplication. 655-662 - Yuval Peres, Dmitry Sotnikov, Benny Sudakov, Uri Zwick:
All-Pairs Shortest Paths in O(n2) 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
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
Local List Decoding with a Constant Number of Queries. 715-722 - Venkatesan Guruswami, Adam D. 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
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-04 20:31 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: