|
|
FOCS 2007
48th Annual IEEE Symposium on Foundations of Computer Science October 20-23, 2007 Providence, RI |
|
 LOCAL
MAP |
| Call for Papers |
| Accepted Papers |
| Program |
| Tutorials |
| Registration |
| Hotel
Reservations |
| Travel info |
| Roommate matching |
| Travel
Support |
| Visa Requests |
| Organizing team |
IEEE CS
| ACM
| SIGACT
| ASQA
| SODA 08
| STOC 08
| SODA 07
| STOC 07
| FOCS 06
Corporate Endowment
Conference Program
The conference venue is the Renaissance Hotel Providence: MAP
Saturday, October 20
9.30 am - 6.00 pm Tutorials at Brown University.
6.30 - 8.30 pm Registration
7:00 - 9:00 pm Welcoming Reception
Sunday, October 21 (20 talks + Knuth Prize Talk)
8.00 am - 4.00 pm Registration
8:30 - 9:50 Session 1 (Chair: Adam Klivans)
Andrej Bogdanov and Emanuele Viola
Pseudorandom bits for polynomials via the Gowers norm
Zeev Dvir, Ariel Gabizon and Avi Wigderson
Extractors and rank extractors for polynomial sources
Louay Bazzi
Polylogarithmic independence can fool DNF formulas
Qi Cheng
Derandomization of sparse cyclotomic integer zero testing
Pseudorandom bits for polynomials via the Gowers norm
Zeev Dvir, Ariel Gabizon and Avi Wigderson
Extractors and rank extractors for polynomial sources
Louay Bazzi
Polylogarithmic independence can fool DNF formulas
Qi Cheng
Derandomization of sparse cyclotomic integer zero testing
10:10 - 11:50 Session 2 (Chair: Kamal Jain)
Constantinos Daskalakis and Christos
Papadimitriou
Computing equilibria in anonymous games
Frank McSherry and Kunal Talwar
Mechanism design via differential privacy
Nicole Immorlica, Anna Karlin, Mohammad Mahdian and Kunal Talwar
Balloon popping with applications to ascending auctions
Kousha Etessami and Mihalis Yannakakis
On the complexity of Nash equilibria and other fixed points
Xi Chen and Shang-Hua Teng
Paths beyond local search: a tight bound for randomized fixed-point computation
Computing equilibria in anonymous games
Frank McSherry and Kunal Talwar
Mechanism design via differential privacy
Nicole Immorlica, Anna Karlin, Mohammad Mahdian and Kunal Talwar
Balloon popping with applications to ascending auctions
Kousha Etessami and Mihalis Yannakakis
On the complexity of Nash equilibria and other fixed points
Xi Chen and Shang-Hua Teng
Paths beyond local search: a tight bound for randomized fixed-point computation
1:30 - 2:50 Session 3 (Chair: TS Jayram)
Philipp Hertel and Toniann Pitassi
Exponential time/space speedups for resolution and the PSPACE-completeness of black-white pebbling
Stefan Dantchev, Barnaby Martin and Stefan Szeider
Parameterized proof complexity
Eyal Lubetzky and Uri Stav
Non-linear index coding outperforming the linear optimum
Dániel Marx
Can you beat treewidth?
Exponential time/space speedups for resolution and the PSPACE-completeness of black-white pebbling
Stefan Dantchev, Barnaby Martin and Stefan Szeider
Parameterized proof complexity
Eyal Lubetzky and Uri Stav
Non-linear index coding outperforming the linear optimum
Dániel Marx
Can you beat treewidth?
3:10 - 4:30 Session 4 (Chair: Bobby Kleinberg)
Daniel Štefankovic, Santosh Vempala and
Eric Vigoda
Adaptive simulated annealing: a near-optimal connection between sampling and counting
Antoine Gerschenfeld and Andrea Montanari
Reconstruction for models on random graphs
Yun Long, Asaf Nachmias and Yuval Peres
Mixing time power laws at criticality
Jeong Han Kim, Ravi Montenegro and Prasad Tetali
A near optimal bound for Pollard's Rho to solve discrete log
Adaptive simulated annealing: a near-optimal connection between sampling and counting
Antoine Gerschenfeld and Andrea Montanari
Reconstruction for models on random graphs
Yun Long, Asaf Nachmias and Yuval Peres
Mixing time power laws at criticality
Jeong Han Kim, Ravi Montenegro and Prasad Tetali
A near optimal bound for Pollard's Rho to solve discrete log
4:50 - 5:50 Session 5 (Chair: Daniele Micciancio)
Stefan Dziembowski and Krzysztof
Pietrzak
Intrusion-resilient secret sharing
Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky and Amit Sahai
Covert multi-party computation
Ran Canetti, Rafael Pass and Abhi Shelat
Cryptography from sunspots: how to use an imperfect reference string
Intrusion-resilient secret sharing
Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky and Amit Sahai
Covert multi-party computation
Ran Canetti, Rafael Pass and Abhi Shelat
Cryptography from sunspots: how to use an imperfect reference string
6:00 - 7:00 Knuth Prize Talk (Chair: Mihalis Yannakakis)
Nancy Lynch
Distributed computing theory: algorithms, impossibility results, models and proofs
Distributed computing theory: algorithms, impossibility results, models and proofs
Monday, October 22 (22 talks + business meeting)
8:30 - 9:50 Session 6 (Chair: Piotr Indyk)
Mihai Patrašcu and Mikkel Thorup
Planning for fast connectivity updates
Guy Blelloch and Daniel Golovin
Strongly history-independent hashing with applications
Vladimir Braverman and Rafail Ostrovsky
Smooth histograms for sliding windows
Anna Gál and Parikshit Gopalan
Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
Planning for fast connectivity updates
Guy Blelloch and Daniel Golovin
Strongly history-independent hashing with applications
Vladimir Braverman and Rafail Ostrovsky
Smooth histograms for sliding windows
Anna Gál and Parikshit Gopalan
Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
10:10 - 11:50 Session 7 (Chair: James Lee)
Per Austrin
Towards sharp inapproximability for any 2-CSP
Subhash Khot and Assaf Naor
Linear equations modulo 2 and the L1 diameter of convex bodies
Christoph Ambühl, Monaldo Mastrolilli and Ola Svensson
Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling
Dániel Marx
On the optimality of planar and geometric approximation schemes
Parikshit Gopalan, Subhash Khot and Rishi Saket
Hardness of reconstructing multivariate polynomials over finite fields
Towards sharp inapproximability for any 2-CSP
Subhash Khot and Assaf Naor
Linear equations modulo 2 and the L1 diameter of convex bodies
Christoph Ambühl, Monaldo Mastrolilli and Ola Svensson
Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling
Dániel Marx
On the optimality of planar and geometric approximation schemes
Parikshit Gopalan, Subhash Khot and Rishi Saket
Hardness of reconstructing multivariate polynomials over finite fields
1:30 - 2:50 Session 8 (Chair: TS Jayram)
Andris Ambainis, Andrew Childs, Ben
Reichardt, Robert Spalek and
Shengyu Zhang
Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer
Dorit Aharonov, Daniel Gottesman, Sandy Irani and Julia Kempe
The power of quantum systems on a line
Oded Regev and Ben Toner
Simulating quantum correlations with finite communication
Andrew Childs, Leonard Schulman and Umesh Vazirani
Quantum algorithms for hidden nonlinear structures
Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer
Dorit Aharonov, Daniel Gottesman, Sandy Irani and Julia Kempe
The power of quantum systems on a line
Oded Regev and Ben Toner
Simulating quantum correlations with finite communication
Andrew Childs, Leonard Schulman and Umesh Vazirani
Quantum algorithms for hidden nonlinear structures
3:10 - 4:50 Session 9 (Chair: Chris Umans)
Uriel Feige
Refuting smoothed 3CNF formulas
Andrej Bogdanov and Muli Safra
Hardness amplification for errorless heuristics
Emanuele Viola and Avi Wigderson
One-way multi-party communication lower bound for pointer jumping with applications
Ran Raz, Amir Shpilka and Amir Yehudayoff
A lower bound for the size of syntactically multilinear arithmetic circuits
Arkadev Chattopadhyay
Discrepancy and the power of bottom fan-in in depth-three circuits
Refuting smoothed 3CNF formulas
Andrej Bogdanov and Muli Safra
Hardness amplification for errorless heuristics
Emanuele Viola and Avi Wigderson
One-way multi-party communication lower bound for pointer jumping with applications
Ran Raz, Amir Shpilka and Amir Yehudayoff
A lower bound for the size of syntactically multilinear arithmetic circuits
Arkadev Chattopadhyay
Discrepancy and the power of bottom fan-in in depth-three circuits
5:10 - 6:30 Session 10 (Chair: Julia Chuzhoy)
Uriel Feige, Vahab Mirrokni and Jan
Vondrák
Maximizing non-monotone submodular functions
Jonathan Kelner and Evdokia Nikolova
On the hardness and smoothed complexity of quasi-concave minimization
Sudipto Guha and Kamesh Munagala
Approximation algorithms for partial-information based stochastic control with Markovian rewards
Christos Koufogiannakis and Neal Young
A fast approximation algorithm for large packing and covering linear programs
Maximizing non-monotone submodular functions
Jonathan Kelner and Evdokia Nikolova
On the hardness and smoothed complexity of quasi-concave minimization
Sudipto Guha and Kamesh Munagala
Approximation algorithms for partial-information based stochastic control with Markovian rewards
Christos Koufogiannakis and Neal Young
A fast approximation algorithm for large packing and covering linear programs
9:00 - 10:00 Business Meeting
Tuesday, October 23 (21 talks)
8:30 - 9:50 Session 11 (Chair: Bobby Kleinberg)
Nikhil Bansal, Niv Buchbinder and Seffi
Naor
A primal-dual randomized algorithm for weighted paging
Noga Alon and Michael Capalbo
Finding disjoint paths in expanders deterministically and online
Esther Ezra and Micha Sharir
Almost tight bound for the union of fat tetrahedra in three dimensions
Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer and Dmitriy Morozov
Inferring local homology from sampled stratified spaces
A primal-dual randomized algorithm for weighted paging
Noga Alon and Michael Capalbo
Finding disjoint paths in expanders deterministically and online
Esther Ezra and Micha Sharir
Almost tight bound for the union of fat tetrahedra in three dimensions
Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer and Dmitriy Morozov
Inferring local homology from sampled stratified spaces
10:10 - 11:50 Session 12 (Chair: Luca Trevisan)
Ilias Diakonikolas, Homin Lee, Kevin
Matulef, Krzysztof Onak, Ronitt
Rubinfeld, Rocco Servedio and Andrew Wan
Testing for concise representations
Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam Smith
Strong lower bounds for approximating distribution support size and the distinct elements problem
Artur Czumaj and Christian Sohler
Testing expansion in bounded-degree graphs
Arie Matsliah, Eldar Fischer and Asaf Shapira
Approximate hypergraph partitioning and applications
Madhu Sudan and Tali Kaufman
Sparse random linear codes are locally decodable and testable
Testing for concise representations
Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam Smith
Strong lower bounds for approximating distribution support size and the distinct elements problem
Artur Czumaj and Christian Sohler
Testing expansion in bounded-degree graphs
Arie Matsliah, Eldar Fischer and Asaf Shapira
Approximate hypergraph partitioning and applications
Madhu Sudan and Tali Kaufman
Sparse random linear codes are locally decodable and testable
1:30 - 2:50 Session 13 (Chair: Julia Chuzhoy)
Naveen Garg and Amit Kumar
Minimizing average flow-time: upper and lower bounds
Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Baruch Schieber and Clifford Stein
Non-preemptive min-sum scheduling with resource augmentation
Moses Charikar, Konstantin Makarychev and Yury Makarychev
On the advantage over random for maximum acyclic subgraph
Spyridon Antonakopoulos, Chandra Chekuri, Bruce Shepherd and Lisa Zhang
Buy-at-bulk network design with protection
Minimizing average flow-time: upper and lower bounds
Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Baruch Schieber and Clifford Stein
Non-preemptive min-sum scheduling with resource augmentation
Moses Charikar, Konstantin Makarychev and Yury Makarychev
On the advantage over random for maximum acyclic subgraph
Spyridon Antonakopoulos, Chandra Chekuri, Bruce Shepherd and Lisa Zhang
Buy-at-bulk network design with protection
3:10 - 4:30 Session 14 (Chair: Anna Lysyanskaya)
Dan Boneh, Craig Gentry and Mike
Hamburg
Space-efficient identity based encryption without pairings
Juan Garay, Jonathan Katz, Chiu-Yuen Koo and Rafail Ostrovsky
Round complexity of authenticated broadcast with a dishonest majority
Iftach Haitner, Jonathan Hoch, Omer Reingold and Gil Segev
Finding collisions in interactive protocols: a tight lower bound on the round complexity of statistically-hiding commitments
Boaz Barak and Mohammad Mahmoody-Ghidary
Lower bounds on signatures from symmetric primitives
Space-efficient identity based encryption without pairings
Juan Garay, Jonathan Katz, Chiu-Yuen Koo and Rafail Ostrovsky
Round complexity of authenticated broadcast with a dishonest majority
Iftach Haitner, Jonathan Hoch, Omer Reingold and Gil Segev
Finding collisions in interactive protocols: a tight lower bound on the round complexity of statistically-hiding commitments
Boaz Barak and Mohammad Mahmoody-Ghidary
Lower bounds on signatures from symmetric primitives
4:50 - 6:10 Session 15 (Chair: Kamal Jain)
Eden Chlamtac
Approximation algorithms using hierarchies of semidefinite programming relaxations
Konstantinos Georgiou, Avner Magen, Toniann Pitassi and Iannis Tourlakis
Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovasz-Schrijver hierarchy
Moses Charikar, Konstantin Makarychev and Yury Makarychev
Tradeoffs between local and global distortions of metric spaces
Alexandr Andoni and Robert Krauthgamer
The computational hardness of estimating edit distance
Approximation algorithms using hierarchies of semidefinite programming relaxations
Konstantinos Georgiou, Avner Magen, Toniann Pitassi and Iannis Tourlakis
Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovasz-Schrijver hierarchy
Moses Charikar, Konstantin Makarychev and Yury Makarychev
Tradeoffs between local and global distortions of metric spaces
Alexandr Andoni and Robert Krauthgamer
The computational hardness of estimating edit distance