|
|
|
47th Annual IEEE Foundations of Computer Science IEEE Computer Society.
|
||
|
Session 1A Statistical Zero-Knowledge Arguments for NP from Any One-Way Function Minh-Huyen Nguyen, Shien Jin Ong, and Salil Vadhan
Fault-Tolerant Distributed Computing in Full-Information Networks Shafi Goldwasser, Elan Pavlov and Vinod Vaikuntanathan
Explicit Exclusive Set Systems with Cryptographic Applications [presentation] Craig Gentry, Zulfikar Ramzan, and David P. Woodruff
Tomas Feder, Adam Guetz, Milena Mihail and Amin Saberi
Local Peering and Service Contracts in Strategic Network Formation Elliot Anshelevich, Bruce Shepherd and Gordon Wilfong
Towards Secure and Scalable Computation in Peer-to-Peer Networks Valerie King, Jared Saia, Vishal Sanwalani and Erik Vee
|
Session 1B A simple condition implying rapid mixing of single-site dynamics on spin systems Thomas P. Hayes
Heat flow and a faster algorithm to compute the surface area of a convex body [presentation] Mikhail Belkin, Hariharan Narayanan and Partha Niyogi
Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization Laszlo Lovasz and Santosh Vempala
Session 2B L_p metrics on the Heisenberg group and the Goemans-Linial conjecture James R. Lee and Assaf Naor
Ramsey partitions and proximity data structures Manor Mendel. Assaf Naor
Algorithms on negatively curved spaces Robert Krauthgamer and James R. Lee
|
|
||
|
|
|
|
|
|
Session 3, Invited Talk: Theory of Computation as a Lens on the Sciences: The Example of Computational Molecular Biology Richard Karp, UC Berkeley. |
|
|
Session 4A
Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method Roman Vershynin
Improved
Approximation Algorithms for Large Matrices via Random Projections Tamás Sarlós
Worst-case and Smoothed Analyses of the ICP Algorithm, With an Application to the k-means Method David Arthur and Sergei Vassilvitskii
The Effectiveness of Lloyd-type Methods for the k-Means Problem Rafail Ostrovsky, Yuval Rabani, Leonard Schulman and Chaitanya Swamy
Session 5A: 4:05-4:50 Chair: Moses Charikar
SDP gaps and UGC-hardness for MaxCutGain Subhash Khot and Ryan O'Donnell
Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets Venkatesan Guruswami and Anindya Patthak
|
Session 4B
Better lossless condensers through derandomized curve samplers Amnon Ta-Shma and Christopher Umans
List-decoding direct product codes and uniform hardness amplification Russell Impagliazzo, Ragesh Jaiswal and Valentine Kabanets
Index Coding with Side Information Ziv Bar-Yossef, Yitzhak Birk, T. S. Jayram and Tomer Kol
Subspace Polynomials and List Decoding of Reed-Solomon Codes Eli Ben-Sasson, Swastik Kopparty and Jaikumar Radhakrishnan
Session 5B: 4:05-4:50 Chair: Ashwin Nayak
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai
Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority Michael Ben-Or, Claude Crepeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith
|
|
Session 6, Best Paper Award: Settling the Complexity of 2-Player Nash-Equilibrium Xi Chen and Xiaotie Deng |
|
|
Session 7A Minimum Bounded Degree Spanning Trees Michel Goemans
Tight Approximate Min-Max Relations for Steiner Rooted-Orientations of Graphs and Hypergraphs Tamas Kiraly and Lap Chi Lau
Improved Bounds for Online Routing and Packing via a Primal-Dual Approach Niv Buchbinder and Seffi Naor
Session 8A Concurrent Non-Malleable Zero Knowledge Boaz Barak, Manoj Prabhakaran and Amit Sahai
Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP Yael Tauman Kalai and Ran Raz
Input-Indistinguishable Computation Silvio Micali,
|
Session 7B Improved Dynamic Planar Point Location Lars Arge, Gerth Stolting Brodal and Loukas Georgiadis
Coresets for Weighted Facilities and Their Applications Dan Feldman, Amos Fiat, and Micha Sharir
Planar Point Location in Sublogarithmic Time Mihai Patrascu AND Point Location in o(log n) Time, Voronoi diagrams in o(n log n) time, and Other Transdichotomous Results in Computational Geometry Timothy M. Chan
Session 8B Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders Krzysztof Onak and Pawel Parys
Lower Bounds for Additive Spanners, Emulators, and More [presentation] David P. Woodruff
Solving Evacuation Problems Efficiently - Earliest Arrival Flows with Multiple Sources Nadine Baumann and Martin Skutella
|
|
Session 9, Invited Talk: Terry Sejnowski, Salk Institute |
|
|
Session 10A New limits on fault-tolerant quantum computation Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver and Falk Unger
Postselection threshold against biased noise Ben W. Reichardt
On the Quantum Query Complexity of Local Search in Two and Three Dimensions Xiaoming Sun and Andrew C. Yao
On the time complexity of 2-tag systems and small universal Turing machines Damien Woods, Turlough Neary
Session 11A Norm of the inverse of a random matrix Mark Rudelson
Witnesses for non-satisfiability of dense random 3CNF formulas Uriel Feige, Jeong Han Kim and Eran Ofek
|
Session 10B On the Optimality of the Dimensionality Reduction Method Alexandr Andoni,
Piotr Indyk and Mihai Patrascu Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions Alexandr Andoni and Piotr Indyk
Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo
Local Graph Partitioning using PageRank Vectors Reid Andersen,
Fan Chung and Kevin Lang Session 11B: 4:05-4:50 Accidental Algorithms Leslie Valiant
The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels Christian Borgs, Jennifer Chayes, Elchanan Mossel, and Sebastien Roch
|
|
Session 12, Machtey Award for Best Student Paper: Algebraic Structures and Algorithms for Matching and Matroid Problems [presentation] Nicholas J. A. Harvey |
|
TUESDAY, Oct 24 |
|
|
Session 13A Hardness of Learning Halfspaces with Noise Venkatesan Guruswami and Prasad Raghavendra
Cryptographic Hardness Results for Learning Intersections of Halfspaces Adam R. Klivans and Alexander A. Sherstov
New Results for Learning Noisy Parities and Halfspaces Vitaly Feldman, Parikshit Gopalan, Subhash Khot and Ashok Kumar Ponnuswami
Session 14A Computing Nash Equilibria: Approximation and Smoothed Complexity Xi Chen, Xiaotie Deng and Shang-Hua Teng
On the Impact of Combinatorial Structure on Congestion Games Heiner Ackermann, Heiko Roeglin and Berthold Voecking
Balanced Allocations of Cake Jeff Edmonds and Kirk Pruhs
|
Session 13B Inclusion-Exclusion Algorithms for Counting Set Partitions [presentation (movie)] Andreas Björklund and Thore Husfeldt
An O(2^n) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion-Exclusion Mikko Koivisto
Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths Surender Baswana and Telikepalli Kavitha
Session 14B A Geometric Generalization of the Upper Bound Theorem Uli Wagner
Higher Lower Bounds for Near-Neighbor and Further Rich Problems Mihai Patrascu and Mikkel Thorup
Planar Earthmover is not in L_1 Assaf Naor and Gideon Schechtman
|
|
Session 15, Invited Talk: Jon Kleinberg, Cornell |
|
|
Session 16A Approximation algorithms for allocation problems: Improving the factor of 1-1/e Uriel Feige, Jan Vondrak
Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems Chandra Chekuri, MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour
How to Play Unique Games Using Embeddings
Improved approximation algorithms for multidimensional bin packing problems Nikhil Bansal, Alberto Caprara and Maxim Sviridenko
|
Session 16B Lower bounds for circuits with MOD_m gates Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlak and Denis Therien On the Compressibility of NP Instances and Cryptographic Applications [presentation] Danny Harnik and Moni Naor
Dispersion of Mass and the Complexity of Randomized Algorithms Luis Rademacher and Santosh Vempala
An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval Alexander A. Razborov and Sergey Yekhanin
|
For updates, corrections or comments please email focsinformal@gmail.com.