FOCS 2002
The 43rd Annual IEEE Symposium on Foundations of Computer
Science
Vancouver, Canada
November 16-19, 2002
SATURDAY NOVEMBER 16
9:30am - 10:00am - Coffee Break
TUTORIAL 1: 10:00am - 12:00 pm, Chair: Venkatesan
Guruswami
Oded Goldreich: Zero-Knowledge
Lunch (on your own)
TUTORIAL 2: 1:45pm - 3:45 pm, Chair:
Yuval Rabani
Eva Tardos: Approximation Algorithms
3:45pm - 4:15pm - Coffee Break
TUTORIAL 3: 4:15pm-6:15pm,
Chair: Omer Reingold
Salil Vadhan: Randomness Extractors
19:00-21:00 Welcome Reception
Workshop
on Algorithms and Models for the Web-Graph
SUNDAY NOVEMBER 17
8:30-10:10
SESSION 1A
CHAIR Venkatesan Guruswami
8:55 Locally Testable Codes and PCPs of Almost-Linear Length,
by Oded Goldreich and Madhu Sudan
9:20 Hardness Results for Coloring 3-Colorable 3-Uniform Hypergraphs,
by Subhash Khot
9:45 The Hardness of 3-Uniform Hypergraph Coloring,
by Irit Dinur, Oded Regev, and Clifford Smyth
SESSION 1B
CHAIR Yuval Rabani
8:30 Minimizing Congestion in General Networks,
by Harald R\"acke
8:55 Small Induced Universal Graphs and Compact Implicit Graph
Representations,
by Stephen Alstrup and Theis Rauhe
9:20 Deterministic Broadcasting Time in Radio Networks of Unknown
Topology,
by Dariusz Kowalski and Andrzej Pelc
9:45 Explicit Unique-Neighbor Expanders,
by Noga Alon and Michael Capalbo
10:10-10:30 BREAK
10:30-12:10
SESSION 2A
CHAIR Ronitt Rubinfeld
10:30 Abstract Combinatorial Programs and Efficient Property Testers,
by Artur Czumaj and Christian Sohler
10:55 A Linear Lower Bound on the Query Complexity of Property Testing,
by Andrej Bogdanov, Kenji Obata, and Luca Trevisan
11:20 Testing Juntas,
by Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky
11:45 A Spectral Algorithm for Learning Mixtures of Distributions,
by Santosh Vempala and Grant Wang
SESSION 2B
CHAIR Bernard Chazelle
10:30 Equivalence between Priority Queues and Sorting,
by Mikkel Thorup
10:55 Integer Sorting in O(n\sqrt{\log\log n}) Expected Time and Linear
Space,
by Yijie Han and Mikkel Thorup
11:20 Implicit B-trees: New Results for the Dictionary Problem,
by G. Franceschini, R. Grossi, J.I. Munro, and L. Pagli
11:45 An Inverse-Ackermann Style Lower Bound for MST Verification Queries,
by Seth Pettie
12:10-2:00 LUNCH
2:00-3:40
SESSION 3A
CHAIR Ronitt Rubinfeld
2:00 PAC = PAExact and Other Equivalent Models in Learning,
by Nader Bshouty and Dmitry Gavinsky
2:25 Learning Intersections and Thresholds of Halfspaces,
by Adam Klivans, Ryan O'Donnell, and Rocco Servedio
2:50 On-line Transductive Confidence Machines are Well-Calibrated,
by Vladimir Vovk
3:15 Learning a Hidden Matching,
by Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov
SESSION 3B
CHAIR Piotr Indyk
2:00 An Information Statistics Approach to Data Stream and Communication
Complexity,
by Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, and D. Sivakumar
2:25 Static Optimality Theorem for External Memory String Access,
by V. Ciriani, P. Ferragina, F. Luccio, and S. Muthukrishnan
2:50 A Simple Algorithmic Characterization of Uniform Solvability
by Eli Gafni
3:15 Correlation Clustering,
by Nikhil Bansal, Avrim Blum, and Shuchi Chawla
3:40-4:15 BREAK
4:15-5:30
SESSION 4A
CHAIR Dan Spielman
4:15 Decoding Turbo-Like Codes in Polynomial Time with Provably
Good
Error-Correcting Performance via Linear Programming,
by Jon Feldman and David R. Karger
4:40 Breaking the O(n^{1/(2k-1)}) Barrier for Information-Theoretic
Private Information Retrieval,
by Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Jean-Francois Raymond
5:05 LT Codes,
by Michael Luby
SESSION 4B
CHAIR Edith Cohen
4:15 Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic
Numbers,
by Uriel Feige, Michael Langberg, and Gideon Schechtman
4:40 Scheduling over a Time-Varying User-Dependent Channel with
Applications to High Speed Wireless Data,
by Matthew Andrews and Lisa Zhang
5:05 On-line End-to-End Congestion Control,
by Naveen Garg and Neal E. Young
8:30 Business Meeting
MONDAY NOVEMBER 18
8:30-10:10
SESSION 1A
CHAIR David Shmoys
8:55 Proving Integrality Gaps without Knowing the Linear Program,
by Sanjeev Arora, Bela Bollobas, Laszlo Lovasz
9:20 Dependent Rounding in Bipartite Graphs
by Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan
9:45 A Constant-Factor Approximation Algorithm for the
Multicommodity Rent-or-Buy Problem,
by Amit Kumar, Anupam Gupta, and Tim Roughgarden
SESSION 1B
CHAIR Tal Rabin
8:30 Constant-Round Coin-Tossing With a Man in the Middle or
Realizing
the Shared Random String Model,
by Boaz Barak
8:55 Generalized Compact Knapsacks, Cyclic Lattices, and Efficient
One-Way Functions from Worst-Case Complexity Assumptions,
by Daniele Micciancio
9:20 Concurrent Zero Knowledge with Logarithmic Round Complexity,
by Manoj M. Prabhakaran, Alon Rosen, and Amit Sahai
9:45 On the (non)Universality of the One-Time Pad,
by Yevgeniy Dodis and Joel Spencer
10:10-10:30 BREAK
10:30-12:10
SESSION 2A
CHAIR Yuval Rabani
10:30 Market Equilibrium via a Primal-Dual-Type Algorithm,
by Nikhil Devanur, Christos H. Papadimitriou, Amin Saberi, and Vijay Vazirani
10:55 Optimal Auctions are Hard,
by Amir Ronen and Amin Saberi
11:20 Auctions with Severely Bounded Communication,
by Liad Blumrosen and Noam Nisan
11:45 Nash Equilibria in Competitive societies, with Applications
to Facility Location, Traffic Routing and Auctions,
by Adrian Vetta
SESSION 2B
CHAIR Omer Reingold
10:30 Privacy and Interaction in Quantum Communication Complexity
and a Theorem about the Relative Entropy of Quantum States,
by Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen
10:55 Linear Diophantine Equations over Polynomials and
Soft Decoding of Reed-Solomon Code,
by Michael Alekhnovich
11:20 Authentication of Quantum States,
by Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, and Alain
Tapp
11:45 Limits on the Power of Quantum Statistical Zero-Knowledge,
by John Watrous
12:10-2:00 LUNCH
2:00-3:40
SESSION 3A
CHAIR David Shmoys
2:00 Protocols and Impossibility Results for Gossip-Based Communication
Mechanisms,
by David Kempe and Jon Kleinberg
2:25 Covering Problems with Hard Capacities,
by Julia Chuzhoy and Joseph (Seffi) Naor
2:50 Packing 2-Dimensional Bins in Harmony,
by Alberto Caprara
3:15 Fast Approximation Algorithms for Fractional Steiner Forest
and Related Problems,
by Naveen Garg and Rohit Khandekar
SESSION 3B
CHAIR Dorit Aharonov
2:00 Quantum Lower Bounds for the Collision and the Element Distinctness
Problems,
by Yaoyun Shi
2:25 Quantum Computation and Lattice Problems,
by Oded Regev
2:50 On the Decidability of Self-Assembly of Infinite Ribbons,
by Leonard Adleman, Jarkko Kari, Lila Kari, and Dustin Reishus
3:15 The Parameterized Complexity of Counting Problems,
by Joerg Flum and Martin Grohe
3:40-4:15 BREAK
4:15-5:30
SESSION 4A
CHAIR Bernard Chazelle
4:15 Dimension Reduction in the L1 Norm,
by Moses Charikar and Amit Sahai
4:40 On Approximating the Radii of Point Sets in High Dimensions,
by Kasturi Varadarajan, S. Venkatesh, and Jiawei Zhang
5:05 Low-Dimensional Linear Programming with Violations,
by Timothy M. Chan
SESSION 4B
CHAIR Maria Bonet
4:15 Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles,
by Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi,
Ran Raz, and Ashish Sabharwal
4:40 Satisfiability, Branch-width and Tseitin Tautologies,
by Michael Alekhnovich and Alexander A. Razborov
5:05 A Switching Lemma for Small Restrictions and Lower Bounds
for
for k-DNF Resolution,
by Nathan Segerlind, Sam Buss, Russell Impagliazzo
9:00PM PRIMES is in P,
Special talk by Manindra Agrawal
TUESDAY NOVEMBER 19
8:30-10:10
SESSION 1A
CHAIR Piotr Indyk
8:55 Dynamic Planar Convex Hull,
by Gerth Stolting Brodal and Riko Jacob
9:20 Optimal System of Loops on an Orientable Surface,
by Eric Colin de Verdiere and Francis Lazarus
9:45 The Partition Technique for Overlays of Envelopes,
by Vladlen Koltun and Micha Sharir
SESSION 1B
CHAIR Anna Gal
8:30 A Dichotomy Theorem for Constraints on a Three-Element Set,
by Andrei A. Bulatov
8:55 Lower Bounds on the Bounded Coefficient Complexity of Bilinear
Maps,
by Peter Buergisser and Martin Lotz
9:20 Power from Random Strings,
by Eric Allender, Harry Buhrman, Michal Koucky,
Dieter van Melkebeek, and Detlef Ronneburger
9:45 Improved Dynamic Reachability Algorithms for Directed
Graphs,
by Liam Roditty and Uri Zwick
10:10-10:30 BREAK
10:30-12:10
SESSION 2A
CHAIR Claire Kenyon
10:30 Conflict-Free Colorings of Simple Geometric Regions
with Applications to Frequency Assignment in Cellular Networks
by Guy Even, Zvi Lotker, Dana Ron, and Shakhar Smorodinsky
10:55 Global Information from Local Observation,
by Itai Beniamini and Laszlo Lovasz
11:20 Rapidly Mixing Markov Chains for Sampling Contingency Tables
with a Constant Number of Rows,
by Mary Cryan, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and
Russell Martin
11:45 Spectral Gap and log-Sobolev Constant for Balanced Matroids,
by Mark R. Jerrum and Jung-Bae Son
SESSION 2B
CHAIR Anna Gal
10:30 Random Lattices and a Conjectured 0-1 Law about their Polynomial
Time Computable Properties,
by Miklos Ajtai
10:55 Graph Isomorphism is in SPP,
by V. Arvind and Piyush P Kurur
11:20 Kolmogorov's Structure Functions with an Application to the Foundations
of Model Selection,
by Nikolai K. Vereshchagin and Paul M.B. Vitanyi
11:45 Forbidden Information,
by Leonid A. Levin
12:10-2:00 LUNCH
2:00-3:40
SESSION 3
CHAIR Claire Kenyon
2:00 The 3-XORSAT Threshold (Strong Evidence in Favour of the
Replica
Method of Statistical Physics),
by Olivier Dubois and Jacques Mandler
2:25 The Asymptotic Order of the Random k-SAT Threshold,
by Dimitris Achlioptas and Cristopher Moore
2:50 On Random Symmetric Travelling Salesman Problems,
by Alan M. Frieze
3:15 Load Balancing with Memory,
by Michael Mitzenmacher, Balaji Prabhakar, and Devavrat Shah