FOCS 2011 Schedule
Saturday, October 22
11:00	-12:30	Tutorial 1: Cynthia Dwork. The Promise of Differential Privacy.
12:30	- 1:45	Lunch (your own)
1:45	- 3:15	Tutorial 2: Kirk Pruhs. Green Computing Algorithmics.
3:30	- 5:00	Tutorial 3: Vinod Vaikuntanathan. Computing Blindfolded: New Developments in Fully Homomorphic Encryption.
7:00	- 9:00	Welcoming Reception.
Sunday, October 23
7:30	- 8:25	Continental Breakfast. Foyer.
		Session 1A.	Session 1B.
8:25	- 8:45	Min-Max Graph Partitioning and Small-Set Expansion	How Bad is Forming Your Own Opinion?
		Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph (Seffi) Naor, Roy Schwartz	David Bindel, Jon Kleinberg, Sigal Oren
8:50	- 9:10	The Graph Minor Algorithm with Parity Conditions	The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
		Ken-ichi Kawarabayashi, Bruce Reed, Paul Wollan	Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani
9:15	- 9:35	Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications	Welfare and Profit Maximization with Production Costs
		Christian Wulff-Nilsen	Avrim Blum, Anupam Gupta, Yishay Mansour, Ankit Sharma
9:40	- 10.00	A constant factor approximation algorithm for unsplittable flow on paths	Mechanism Design with Set-Theoretic Beliefs
		Paul Bonsm, Jens Schulz, Andreas Wiese	Jing Chen, Silvio Micali
10.00	-10:45	Coffee Break. Foyer.
		Session 2A.	Session 2B.
10:45	- 11:05	Efficient Fully Homomorphic Encryption from (Standard) LWE	Sharp mixing time bounds for sampling random surfaces
		Zvika Brakerski, Vinod Vaikuntanathan	Pietro Caputo, Fabio Martinelli, Fabio Lucio Toninelli
11:10	- 11:30	Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits	Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
		Craig Gentry, Shai Halevi	Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, Eric Vigoda, Linji Yang
11:35	- 11:55	Coin Flipping with Constant Bias Implies One-Way Functions	Solving connectivity problems parameterized by treewidth in single exponential time
		Iftach Haitner, Eran Omri	Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Joham M. M. van Rooij, Jakub Onufry Wojtaszczyk
12:00	- 12:20	How to Garble Arithmetic Circuits	The minimum k-way cut of bounded size is fixed-parameter tractable
		Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	Mikkel Thorup, Ken-ichi Kawarabayashi
12:30	- 1:45	Lunch.
		Session 3A.	Session 3B.
2:00	- 2:20	Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time	Extractors for circuit sources
		Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen	Emanuele Viola
2:25	- 2:45	Minimum Weight Cycles and Triangles_c_ Equivalences and Algorithms.pdf">Minimum Weight Cycles and Triangles: Equivalences and Algorithms	Randomness buys depth for approximate counting.pdf">Randomness buys depth for approximate counting
		Liam Roditty, Virginia Vassilevska Williams	Emanuele Viola
2:50	- 3:10	Graph Connectivities, Network Coding, and Expander Graphs	Pseudorandomness for read-once formulas
		Ho Yee Cheung, Lap Chi Lau, Kai Man Leung	Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan
3:15	- 3:35	Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2	Dispersers for affine sources with sub-polynomial entropy
		Loïc Séguin-Charbonneau, F. Bruce Shepherd	Ronen Shaltiel
3:40	- 4:00	Online Node-weighted Steiner Tree and Related Problems	A Small PRG for Polynomial Threshold Functions of Gaussians
		Joseph (Seffi) Naor, Debmalya Panigrahi, Mohit Singh	Daniel M. Kane
4:00	- 4:30	Coffee Break. Foyer.
		Session 4.
4:30	- 4:50	A Polylogarithmic-Competitive Algorithm for the k-Server Problem
		Nikhil Bansal, Niv Buchbinde, Aleksander Madry, Joseph (Seffi) Naor
4:55	- 5:15	3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
		Timon Hertli
5:20	- 6:20	Piore Award Presentation to Shafi Goldwasser Michael R. Williams on behalf of IEEE Piore Award Lecture: Pseudo Deterministic Algorithms
		Shafi Goldwasser
9:00	-	Business Meeting.
Monday, October 24
7:30	- 8:25	Continental Breakfast. Foyer.
		Session 5A.	Session 5B.
8:25	- 8:45	On the Power of Adaptivity in Sparse Recovery	The 1D Area Law and the Complexity of Quantum States: A combinatorial approach
		Piotr Indyk, Eric Price, David P. Woodruff	Dorit Aharonov, Itai Arad, Zeph Landau, Umesh Vazirani
8:50	- 9:10	(1+eps)-Approximate Sparse Recovery	On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems
		Eric Price, David P. Woodruff	Dorit Aharonov, Lior Eldar
9:15	- 9:35	Near-Optimal Column-Based Matrix Reconstruction	Quantum query complexity of state conversion
		Christos Boutsidis, Petros Drineas, Malik Magdon-Ismail	Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy
9:40	- 10:00	Near Linear Lower Bound for Dimension Reduction in L1	Optimal bounds for quantum bit commitment
		Alexandr Andoni, Moses S. Charikar, Ofer Neiman, Huy L. Nguyen	André Chailloux, Iordanis Kerenidis
10:00	-10:45	Coffee Break. Foyer.
		Session 6A.	Session 6B.
10:45	- 11:05	Streaming Algorithms via Precision Sampling	The Power of Linear Estimators
		Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak	Gregory Valiant, Paul Valiant
11:10	- 11:30	Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones	An algebraic proof of a robust social choice impossibility theorem
		Michael Elkin, Shay Solomon	Dvir Falik, Ehud Friedgut
11:35	- 11:55	Fully dynamic maximal matching in O(log n) update time	Planar Graphs: Random Walks and Bipartiteness Testing
		Surender Baswana, Manoj Gupta, Sandeep Sen	Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler
12:00	- 12:20	Which Networks Are Least Susceptible to Cascading Failures?	Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
		Lawrence Blume, David Easley, Jon Kleinberg, Robert Kleinberg, Eva Tardos	Madhav Jha, Sofya Raskhodnikova
12:30	- 1:45	Lunch.
		Session 7A.	Session 7B.
2:00	- 2:20	How to Play Unique Games Against a Semi-Random Adversary	Markov Layout
		Alexandra Kolla, Konstantin Makarychev, Yury Makarychev	Flavio Chierichetti, Ravi Kumar, Prabhakar Raghavan
2:25	- 2:45	The Grothendieck constant is strictly smaller than Krivine's bound	Limitations of Randomized Mechanisms for Combinatorial Auctions
		Mark Braverman, Konstantin Makarychev, Yury Makarychev, Assaf Naor	Shaddin Dughmi, Jan Vondrak
2:50	- 3:10	A Parallel Approximation Algorithm for Positive Semidefinite Programming	Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
		Rahul Jain, Penghui Yao	Saeed Alaei
3:15	- 3:35	Rounding Semidefinite Programming Hierarchies via Global Correlation	Extreme-Value Theorems for Optimal Multidimensional Pricing
		Boaz Barak, Prasad Raghavendra, David Steurer	Yang Cai, Constantinos Daskalakis
3:40	- 4:00	Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives	Efficient computation of approximate pure Nash equilibria in congestion games
		Venkatesan Guruswami, Ali Kemal Sinop	Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik
4:00	- 4:30	Coffee Break. Foyer.
		Session 8.
4:30	- 4:50	On Range Searching in the Group Model and Combinatorial Discrepancy
		Kasper Green Larsen
4:55	- 5:15	A Randomized Rounding Approach to the Traveling Salesman Problem
		Shayan Oveis Gharan, Amin Saberi, Mohit Singh
5:20	- 5:40	Approximating Graphic TSP by Matchings
		Tobias Moemke, Ola Svensson
Tuesday, October 25
7:30	- 8:25	Continental Breakfast. Foyer.
		Session 9A.	Session 9B.
8:25	- 8:45	A Unified Continuous Greedy Algorithm for Submodular Maximization	Lexicographic Products and the Power of Non-Linear Network Coding
		Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz	Anna Blasiak, Robert Kleinberg, Eyal Lubetzky
8:50	- 9:10	Enumerative Lattice Algorithms in any Norm via M-ellipsoid Coverings	Quadratic Goldreich-Levin Theorems
		Daniel Dadush, Chris Peikert, Santosh Vempala	Madhur Tulsiani, Julia Wolf
9:15	- 9:35	A nearly-mlogn time solver for SDD linear systems	Optimal testing of multivariate polynomials over small prime fields
		Ioannis Koutis, Gary L. Miller, Richard Peng	Elad Haramaty, Amir Shpilka, Madhu Sudan
9:40	- 10:00	Balls and Bins: Smaller Hash Families and Faster Evaluation	Tight lower bounds for 2-query LCCs over finite fields
		L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder	Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka
10:00	-10:30	Coffee Break. Foyer.
		Session 10A.	Session 10B.
10:30	- 10:50	A Two Prover One Round Game with Strong Soundness	Medium Access Using Queues
		Subhash Khot, Muli Safra	Devavrat Shah, Jinwoo Shin, Prasad Tetali
10:55	- 11:15	The Randomness Complexity of Parallel Repetition	Local Distributed Decision
		Kai-Min Chung, Rafael Pass	Pierre Fraigniaud, Amos Korman, David Peleg
11:20	- 11:40	Privacy Amplification and Non-Malleable Extractors Via Character Sums	The Complexity of Renaming
		Yevgeniy Dodis, Xin Li, Trevor D. Wooley, David Zuckerman	Dan Alistarh, James Aspnes, Seth Gilbert, Rachid Guerraoui
11:45	- 12:05	Stateless Cryptographic Protocols	Mutual Exclusion with O(log^2 log n) Amortized Work
		Vipul Goyal, Hemanta K. Maji	Michael A. Bender, Seth Gilbert
12.10	- 12:30	Storing Secrets on Continually Leaky Devices	Algorithms for the Generalized Sorting Problem
		Yevgeniy Dodis, Allison Lewko, Brent Waters, Daniel Wichs	Zhiyi Huang, Sampath Kannan, Sanjeev Khanna
12:30	- 1:45	Lunch.
		Session 11A.	Session 11B.
2:00	- 2:20	Information Equals Amortized Communication	Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
		Mark Braverman, Anup Rao	Jian Li, Amol Deshpande
2:25	- 2:45	Delays and the Capacity of Continuous-time Channels	Approximation Algorithms for Submodular Multiway Partition
		Sanjeev Khanna, Madhu Sudan	Chandra Chekuri, Alina Ene
2:50	- 3:10	Efficient and Explicit Coding for Interactive Communication	An FPTAS for #Knapsack and Related Counting Problems
		Ran Gelles, Ankur Moitra, Amit Sahai	Parikshit Gopalan, Adam Klivans, Raghu Meka, Daniel Stefankovic, Santosh Vempala, Eric Vigoda
3:15	- 3:35	Efficient Reconstruction of Random Multilinear Formulas	Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
		Ankit Gupta, Neeraj Kayal, Satya Lokam	Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi
3:40	- 4:00	New extension of the Weil bound for character sums with applications to coding	Evolution with Recombination
		Tali Kaufman, Shachar Lovett	Varun Kanade