52. FOCS 2011: Palm Springs, CA, USA

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 Bonsma, Jens Schulz, Andreas Wiese:
  A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths. 47-56
  

Session 1B

• David Bindel, Jon M. Kleinberg, Sigal Oren:
  How Bad is Forming Your Own Opinion? 57-66
  
• Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani:
  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, Fabio Martinelli, Fabio Lucio Toninelli:
  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, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk:
  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, Yahav Nussbaum, Christian Wulff-Nilsen:
  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, F. Bruce Shepherd:
  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, Aleksander Madry, Joseph Naor:
  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, Malik Magdon-Ismail:
  Near Optimal Column-Based Matrix Reconstruction. 305-314
  
• Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen:
  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, Krzysztof Onak:
  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, Penghui Yao:
  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, Constantinos Daskalakis:
  Extreme-Value Theorems for Optimal Multidimensional Pricing. 522-531
  
• Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik:
  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, Joseph Naor, Roy Schwartz:
  A Unified Continuous Greedy Algorithm for Submodular Maximization. 570-579
  
• Daniel Dadush, Chris Peikert, Santosh Vempala:
  Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings. 580-589
  
• Ioannis Koutis, Gary L. Miller, Richard Peng:
  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, Robert Kleinberg, Eyal Lubetzky:
  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, Madhu Sudan:
  Optimal Testing of Multivariate Polynomials over Small Prime Fields. 629-637
  
• Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, Shubhangi Saraf:
  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, Rafael Pass:
  The Randomness Complexity of Parallel Repetition. 658-667
  
• Yevgeniy Dodis, Xin Li, Trevor D. Wooley, David Zuckerman:
  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, Rachid Guerraoui:
  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, Sampath Kannan, Sanjeev Khanna:
  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 Klivans, Raghu Meka, Daniel Stefankovic, Santosh Vempala, Eric Vigoda:
  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
  

Last update Fri May 25 08:14:16 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page