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