default search action
47th FOCS 2006: Berkeley, CA, USA
- 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings. IEEE Computer Society 2006, ISBN 0-7695-2720-5
- Minh-Huyen Nguyen, Shien Jin Ong, Salil P. Vadhan:
Statistical Zero-Knowledge Arguments for NP from Any One-Way Function. 3-14 - Shafi Goldwasser, Elan Pavlov, Vinod Vaikuntanathan:
Fault-Tolerant Distributed Computing in Full-Information Networks. 15-26 - Craig Gentry, Zulfikar Ramzan, David P. Woodruff:
Explicit Exclusive Set Systems with Applications to Broadcast Encryption. 27-38 - Thomas P. Hayes:
A simple condition implying rapid mixing of single-site dynamics on spin systems. 39-46 - Mikhail Belkin, Hariharan Narayanan
, Partha Niyogi:
Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body. 47-56 - László Lovász, Santosh S. Vempala:
Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization. 57-68 - Tomás Feder, Adam Guetz, Milena Mihail, Amin Saberi:
A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks. 69-76 - Elliot Anshelevich
Strategic Network Formation through Peering and Service Agreements. 77-86 - Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee:
Towards Secure and Scalable Computation in Peer-to-Peer Networks. 87-98 - James R. Lee, Assaf Naor:
Lp metrics on the Heisenberg group and the Goemans-Linial conjecture. 99-108 - Manor Mendel, Assaf Naor:
Ramsey partitions and proximity data structures. 109-118 - Robert Krauthgamer
Algorithms on negatively curved spaces. 119-132 - Roman Vershynin:
Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method. 133-142 - Tamás Sarlós:
Improved Approximation Algorithms for Large Matrices via Random Projections. 143-152 - David Arthur, Sergei Vassilvitskii:
Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method. 153-164 - Rafail Ostrovsky, Yuval Rabani
The Effectiveness of Lloyd-Type Methods for the k-Means Problem. 165-176 - Amnon Ta-Shma
Better lossless condensers through derandomized curve samplers. 177-186 - Russell Impagliazzo
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. 187-196 - Ziv Bar-Yossef, Yitzhak Birk
Index Coding with Side Information. 197-206 - Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan:
Subspace Polynomials and List Decoding of Reed-Solomon Codes. 207-216 - Subhash Khot, Ryan O'Donnell:
SDP gaps and UGC-hardness for MAXCUTGAIN. 217-226 - Venkatesan Guruswami, Anindya C. Patthak:
Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. 227-238 - Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai:
Cryptography from Anonymity. 239-248 - Michael Ben-Or
Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority. 249-260 - Xi Chen
Settling the Complexity of Two-Player Nash Equilibrium. 261-272 - Michel X. Goemans:
Minimum Bounded Degree Spanning Trees. 273-282 - Tamás Király, Lap Chi Lau:
Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs. 283-292 - Niv Buchbinder
Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach. 293-304 - Lars Arge, Gerth Stølting Brodal
Improved Dynamic Planar Point Location. 305-314 - Dan Feldman, Amos Fiat, Micha Sharir:
Coresets forWeighted Facilities and Their Applications. 315-324 - Mihai Patrascu:
Planar Point Location in Sublogarithmic Time. 325-332 - Timothy M. Chan:
Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry. 333-344 - Boaz Barak, Manoj Prabhakaran, Amit Sahai:
Concurrent Non-Malleable Zero Knowledge. 345-354 - Yael Tauman Kalai, Ran Raz
Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. 355-366 - Silvio Micali, Rafael Pass
Input-Indistinguishable Computation. 367-378 - Krzysztof Onak, Pawel Parys
Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. 379-388 - David P. Woodruff:
Lower Bounds for Additive Spanners, Emulators, and More. 389-398 - Nadine Baumann, Martin Skutella:
Solving Evacuation Problems Efficiently--Earliest Arrival Flows with Multiple Sources. 399-410 - Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, Falk Unger:
New Limits on Fault-Tolerant Quantum Computation. 411-419 - Ben Reichardt:
Postselection threshold against biased noise. 420-428 - Xiaoming Sun
On the Quantum Query Complexity of Local Search in Two and Three Dimensions. 429-438 - Damien Woods, Turlough Neary
On the time complexity of 2-tag systems and small universal Turing machines. 439-448 - Alexandr Andoni, Piotr Indyk, Mihai Patrascu:
On the Optimality of the Dimensionality Reduction Method. 449-458 - Alexandr Andoni, Piotr Indyk:
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. 459-468 - Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo
Points on Computable Curves. 469-474 - Reid Andersen, Fan R. K. Chung, Kevin J. Lang:
Local Graph Partitioning using PageRank Vectors. 475-486 - Mark Rudelson:
Norm of the inverse of a random matrix. 487-496 - Uriel Feige, Jeong Han Kim, Eran Ofek:
Witnesses for non-satisfiability of dense random 3CNF formulas. 497-508 - Leslie G. Valiant:
Accidental Algorithms. 509-517 - Christian Borgs
The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels. 518-530 - Nicholas J. A. Harvey:
Algebraic Structures and Algorithms for Matching and Matroid Problems. 531-542 - Venkatesan Guruswami, Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise. 543-552 - Adam R. Klivans, Alexander A. Sherstov:
Cryptographic Hardness for Learning Intersections of Halfspaces. 553-562 - Vitaly Feldman
New Results for Learning Noisy Parities and Halfspaces. 563-574 - Andreas Björklund, Thore Husfeldt:
Inclusion--Exclusion Algorithms for Counting Set Partitions. 575-582 - Mikko Koivisto:
An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion. 583-590 - Surender Baswana, Telikepalli Kavitha:
Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths. 591-602 - Xi Chen
Computing Nash Equilibria: Approximation and Smoothed Complexity. 603-612 - Heiner Ackermann, Heiko Röglin
On the Impact of Combinatorial Structure on Congestion Games. 613-622 - Jeff Edmonds, Kirk Pruhs:
Balanced Allocations of Cake. 623-634 - Uli Wagner
On a Geometric Generalization of the Upper Bound Theorem. 635-645 - Mihai Patrascu, Mikkel Thorup:
Higher Lower Bounds for Near-Neighbor and Further Rich Problems. 646-654 - Assaf Naor, Gideon Schechtman:
Planar Earthmover is not in L_1. 655-666 - Uriel Feige, Jan Vondrák:
Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. 667-676 - Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. 677-686 - Eden Chlamtac, Konstantin Makarychev, Yury Makarychev:
How to Play Unique Games Using Embeddings. 687-696 - Nikhil Bansal, Alberto Caprara, Maxim Sviridenko:
Improved approximation algorithms for multidimensional bin packing problems. 697-708 - Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien:
Lower bounds for circuits with MOD_m gates. 709-718 - Danny Harnik, Moni Naor:
On the Compressibility of NP Instances and Cryptographic Applications. 719-728 - Luis Rademacher
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. 729-738 - Alexander A. Razborov, Sergey Yekhanin:
An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval. 739-748
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-12-13 19:00 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: