default search action
52nd FOCS 2011: Palm Springs, CA, USA
- Rafail Ostrovsky:
IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011. IEEE Computer Society 2011, ISBN 978-1-4577-1843-4
Tutorials
- Cynthia Dwork:
The Promise of Differential Privacy: A Tutorial on Algorithmic Techniques. 1-2 - Kirk Pruhs:
Green Computing Algorithmics. 3-4 - Vinod Vaikuntanathan:
Computing Blindfolded: New Developments in Fully Homomorphic Encryption. 5-16
Session 1A
- Nikhil Bansal, Uriel Feige, Robert Krauthgamer
, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz:
Min-max Graph Partitioning and Small Set Expansion. 17-26 - Ken-ichi Kawarabayashi, Bruce A. Reed, Paul Wollan:
The Graph Minor Algorithm with Parity Conditions. 27-36 - Christian Wulff-Nilsen:
Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications. 37-46 - Paul S. Bonsma, Jens Schulz, Andreas Wiese:
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths. 47-56
Session 1B
- David Bindel
How Bad is Forming Your Own Opinion? 57-66 - Paul W. Goldberg
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. 67-76 - Avrim Blum, Anupam Gupta, Yishay Mansour, Ankit Sharma:
Welfare and Profit Maximization with Production Costs. 77-86 - Jing Chen, Silvio Micali:
Mechanism Design with Set-Theoretic Beliefs. 87-96
Session 2A
- Zvika Brakerski, Vinod Vaikuntanathan:
Efficient Fully Homomorphic Encryption from (Standard) LWE. 97-106 - Craig Gentry, Shai Halevi:
Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits. 107-109 - Iftach Haitner, Eran Omri
Coin Flipping with Constant Bias Implies One-Way Functions. 110-119 - Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
How to Garble Arithmetic Circuits. 120-129
Session 2B
- Pietro Caputo
Sharp Mixing Time Bounds for Sampling Random Surfaces. 130-139 - Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, Eric Vigoda, Linji Yang:
Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets. 140-149 - Marek Cygan
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time. 150-159 - Ken-ichi Kawarabayashi, Mikkel Thorup
The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable. 160-169
Session 3A
- Glencora Borradaile, Philip N. Klein, Shay Mozes
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. 170-179 - Liam Roditty, Virginia Vassilevska Williams:
Minimum Weight Cycles and Triangles: Equivalences and Algorithms. 180-189 - Ho Yee Cheung, Lap Chi Lau, Kai Man Leung:
Graph Connectivities, Network Coding, and Expander Graphs. 190-199 - Loïc Seguin-Charbonneau
Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2. 200-209 - Joseph Naor, Debmalya Panigrahi, Mohit Singh:
Online Node-Weighted Steiner Tree and Related Problems. 210-219
Session 3B
- Emanuele Viola:
Extractors for Circuit Sources. 220-229 - Emanuele Viola:
Randomness Buys Depth for Approximate Counting. 230-239 - Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan:
Pseudorandomness for Read-Once Formulas. 240-246 - Ronen Shaltiel:
Dispersers for Affine Sources with Sub-polynomial Entropy. 247-256 - Daniel M. Kane:
A Small PRG for Polynomial Threshold Functions of Gaussians. 257-266
Session 4
- Nikhil Bansal, Niv Buchbinder
A Polylogarithmic-Competitive Algorithm for the k-Server Problem. 267-276 - Timon Hertli:
3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General. 277-284
Session 5A
- Piotr Indyk, Eric Price, David P. Woodruff:
On the Power of Adaptivity in Sparse Recovery. 285-294 - Eric Price, David P. Woodruff:
(1 + eps)-Approximate Sparse Recovery. 295-304 - Christos Boutsidis, Petros Drineas
Near Optimal Column-Based Matrix Reconstruction. 305-314 - Alexandr Andoni, Moses Charikar
Near Linear Lower Bound for Dimension Reduction in L1. 315-323
Session 5B
- Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani:
The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach. 324-333 - Dorit Aharonov, Lior Eldar:
On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems. 334-343 - Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy:
Quantum Query Complexity of State Conversion. 344-353 - André Chailloux, Iordanis Kerenidis:
Optimal Bounds for Quantum Bit Commitment. 354-362
Session 6A
- Alexandr Andoni, Robert Krauthgamer
Streaming Algorithms via Precision Sampling. 363-372 - Michael Elkin, Shay Solomon:
Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones. 373-382 - Surender Baswana, Manoj Gupta, Sandeep Sen:
Fully Dynamic Maximal Matching in O (log n) Update Time. 383-392 - Lawrence E. Blume, David A. Easley, Jon M. Kleinberg, Robert Kleinberg, Éva Tardos:
Which Networks are Least Susceptible to Cascading Failures? 393-402
Session 6B
- Gregory Valiant, Paul Valiant:
The Power of Linear Estimators. 403-412 - Dvir Falik, Ehud Friedgut:
An Algebraic Proof of a Robust Social Choice Impossibility Theorem. 413-422 - Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler
Planar Graphs: Random Walks and Bipartiteness Testing. 423-432 - Madhav Jha, Sofya Raskhodnikova:
Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. 433-442
Session 7A
- Alexandra Kolla, Konstantin Makarychev, Yury Makarychev:
How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. 443-452 - Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor:
The Grothendieck Constant is Strictly Smaller than Krivine's Bound. 453-462 - Rahul Jain
A Parallel Approximation Algorithm for Positive Semidefinite Programming. 463-471 - Boaz Barak, Prasad Raghavendra, David Steurer
Rounding Semidefinite Programming Hierarchies via Global Correlation. 472-481 - Venkatesan Guruswami, Ali Kemal Sinop:
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. 482-491
Session 7B
- Flavio Chierichetti, Ravi Kumar, Prabhakar Raghavan
Markov Layout. 492-501 - Shaddin Dughmi, Jan Vondrák:
Limitations of Randomized Mechanisms for Combinatorial Auctions. 502-511 - Saeed Alaei
Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. 512-521 - Yang Cai
Extreme-Value Theorems for Optimal Multidimensional Pricing. 522-531 - Ioannis Caragiannis
Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games. 532-541
Session 8
- Kasper Green Larsen:
On Range Searching in the Group Model and Combinatorial Discrepancy. 542-549 - Shayan Oveis Gharan, Amin Saberi, Mohit Singh:
A Randomized Rounding Approach to the Traveling Salesman Problem. 550-559 - Tobias Mömke, Ola Svensson:
Approximating Graphic TSP by Matchings. 560-569
Session 9A
- Moran Feldman
A Unified Continuous Greedy Algorithm for Submodular Maximization. 570-579 - Daniel Dadush
Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings. 580-589 - Ioannis Koutis
A Nearly-m log n Time Solver for SDD Linear Systems. 590-598 - L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder:
Balls and Bins: Smaller Hash Families and Faster Evaluation. 599-608
Session 9B
- Anna Blasiak
Lexicographic Products and the Power of Non-linear Network Coding. 609-618 - Madhur Tulsiani, Julia Wolf:
Quadratic Goldreich-Levin Theorems. 619-628 - Elad Haramaty, Amir Shpilka
Optimal Testing of Multivariate Polynomials over Small Prime Fields. 629-637 - Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka
Tight Lower Bounds for 2-query LCCs over Finite Fields. 638-647
Session 10A
- Subhash Khot, Muli Safra
A Two Prover One Round Game with Strong Soundness. 648-657 - Kai-Min Chung
The Randomness Complexity of Parallel Repetition. 658-667 - Yevgeniy Dodis, Xin Li, Trevor D. Wooley
Privacy Amplification and Non-malleable Extractors via Character Sums. 668-677 - Vipul Goyal, Hemanta K. Maji:
Stateless Cryptographic Protocols. 678-687 - Yevgeniy Dodis, Allison B. Lewko, Brent Waters, Daniel Wichs:
Storing Secrets on Continually Leaky Devices. 688-697
Session 10B
- Devavrat Shah, Jinwoo Shin, Prasad Tetali:
Medium Access Using Queues. 698-707 - Pierre Fraigniaud, Amos Korman, David Peleg:
Local Distributed Decision. 708-717 - Dan Alistarh, James Aspnes, Seth Gilbert
The Complexity of Renaming. 718-727 - Michael A. Bender, Seth Gilbert
Mutual Exclusion with O(log^2 Log n) Amortized Work. 728-737 - Zhiyi Huang
Algorithms for the Generalized Sorting Problem. 738-747
Session 11A
- Mark Braverman, Anup Rao:
Information Equals Amortized Communication. 748-757 - Sanjeev Khanna, Madhu Sudan:
Delays and the Capacity of Continuous-Time Channels. 758-767 - Ran Gelles, Ankur Moitra, Amit Sahai:
Efficient and Explicit Coding for Interactive Communication. 768-777 - Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam:
Efficient Reconstruction of Random Multilinear Formulas. 778-787 - Tali Kaufman, Shachar Lovett
New Extension of the Weil Bound for Character Sums with Applications to Coding. 788-796
Session 11B
- Jian Li, Amol Deshpande:
Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems. 797-806 - Chandra Chekuri, Alina Ene:
Approximation Algorithms for Submodular Multiway Partition. 807-816 - Parikshit Gopalan, Adam R. Klivans, Raghu Meka, Daniel Stefankovic
An FPTAS for #Knapsack and Related Counting Problems. 817-826 - Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi:
Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits. 827-836 - Varun Kanade
Evolution with Recombination. 837-846
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-12 21:06 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: