Preliminary Program for FOCS 2003
Saturday October 11th 2003
Tutorials Day at Radcliffe Institute for Advanced Study
TUTORIAL 1: 1:20pm - 3:20 pm, Chair: Paul Beame
Dana Randall: Mixing
Lunch (on your own)
TUTORIAL 2: 9:30am - 11:30 pm, Chair: Michael Mitzenmacher
Avrim Blum: Machine Learning: my favorite results, directions, and open problems
TUTORIAL 3: 3:50pm-5:50pm, Chair: Avi Wigderson
Eli Upfal:
Welcome Reception 7:00 pm - 8:30pm
------------------------------------------------------------------------
Sunday October 12th 2003
Morning
SESSION 1: 8:45 am - 10:25 am, Chair: Chandra Chekuri
* Perfect Graph Recognition, Gerard Cornuejols and Xinming Liu and
Kristina Vuskovic
* On Certain Connectivity Properties of the Internet Topology,
Milena Mihail and Christos Papadimitriou and Amin Saberi
* Paths, Trees and minimum latency tours, Kamalika Chaudhuri and
Brighten Godfrey and Satish Rao and Kunal Talwar
* Approximation Algorithms for Orienteering and Discounted-Reward
TSP, Avrim Blum and Shuchi Chawla and David Karger and Terran Lane
and Adam Meyerson and Maria Minkoff
* A 2/3 Approximation for Maximum Asymmetric TSP by Decomposing
Directed Regular Multigraphs, Haim Kaplan and Moshe Lewenstein and
Nira Shafrir and Maxim Sviridenko
SESSION 2: 10:50am - 12:10pm, Chair: Eyal Kushilevitz
* On the Implementation of Huge Random Objects, Oded Goldreich and
Shafi Goldwasser and Asaf Nussboim
* Zero-Knowledge Sets, Silvio Micali and Michael Rabin and Joe Kilian
* Deterministic Extractors for Bit-Fixing Sources and
Exposure-Resilient Cryptography, Jesse Kamp and David Zuckerman
* On the (In)security of the Fiat-Shamir Paradigm, Shafi Goldwasser
and Yael Tauman
Lunch (Provided)
Afternoon
SESSION 3: 1:40pm - 3:00pm, Chair: Valentine Kabanets
* Locally Testable Cyclic Codes, Laszlo Babai and Amir Shpilka and
Daniel Stefankovic
* List Decoding Using the XOR Lemma, Luca Trevisan
* On $\epsilon$-Biased Generators in NC^0, Elchanan Mossel and Amir
Shpilka and Luca Trevisan
* A Unifying Approach for Proving Hardcore Predicates Using List
Decoding, Adi Akavia and Shafi Goldwasser and Muli Safra
SESSION 4: 3:25pm - 4:45pm, Chair: Michael Mitzenmacher
* Instability of FIFO at Arbitrarily Low Rates in the Adversarial
Queueing Model, Rajat Bhattacharjee and Ashish Goel
* Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the
Finite Random Assignment Problem, Chandra Nair and Balaji
Prabhakar and Mayank Sharma
* Better Turing: asymptotically optimal probability estimation, Alon
Orlitsky and Narayana P. Santhanam and Junan Zhang
* Learning DNF from Random Walks, Nader Bshouty and Elchanan Mossel
and Ryan O'Donnell and Rocco Servedio
SESSION 5: 5:10pm - 6:30pm, Chair: John Watrous
* Quantum Search of Spatial Regions, Scott Aaronson and Andris Ambainis
* A Lattice Problem in Quantum NP, Dorit Aharonov and Oded Regev
* A lower bound for bounded round quantum communication complexity
of set disjointness, Rahul Jain and Jaikumar Radhakrishnan and
Pranab Sen
* Polynomial degree vs. quantum query complexity, Andris Ambainis
Business Meeting 9:00 pm - 10:00 pm
------------------------------------------------------------------------
Monday October 13th 2003
Morning
SESSION 6: 8:45 am - 10:25 am, Chair: Erik Demaine
* An In-Place Sorting with O(n log n) Comparisons and O(n) Moves,
Gianni Franceschini and Viliam Geffert
* Breaking a Time-and-Space Barrier in Constructing Full-Text
Indices, Wing-Kai Hon and Kunihiko Sadakane and Wing-Kin Sung
* I/O-Efficient Strong Connectivity and Depth-First Search for
Directed Planar Graphs, Lars Arge and Norbert Zeh
* The Cost of Cache-Oblivious Searching, Michael A. Bender and Gerth
St\o{}lting Brodal and Rolf Fagerberg and Dongdong Ge and Simai He
and Haodong Hu and John Iacono and Alejandro L\'{o}pez-Ortiz
* Tight Lower Bounds for the Distinct Elements Problem, Piotr Indyk
and David Woodruff
SESSION 7: 10:50am - 12:10pm, Chair: Daniele Micciancio
* Hardness of Approximating the Shortest Vector Problem in High L_p
Norms, Subhash Khot
* More on average case vs approximation complexity, Michael Alekhnovich
* On Worst-Case to Average-Case Reductions for NP Problems, Andrej
Bogdanov and Luca Trevisan
* On the Rank of Cutting Planes Proof-Systems and the Role of
Expansion, Josh Buresh-Oppenheim and Nicola Galesi and Shlomo
Hoory and Avner Magen and Toniann Pitassi
Lunch (Provided)
Afternoonu
SESSION 8: 1:40pm - 3:00pm, Chair: Paul Beame
* The resolution complexity of random constraint satisfaction
problems, Michael Molloy and Mohammad Salavatipour
* Algorithms and Complexity Results for sharpSAT and Bayesian
Inference, Fahiem Bacchus and Shannon Dalmao and Toniann Pitassi
* Linear Upper Bounds for Random Walk on Small Density Random
3-CNFs, Mikhail Alekhnovich and Eli Ben-Sasson
* On the Maximum Satisfiability of Random Formulas, Dimitris
Achlioptas and Assaf Naor and Yuval Peres
SESSION 9: 3:25pm - 4:45pm, Chair: Ran Canetti
* Logics for reasoning about cryptographic constructions, Russell
Impagliazzo and Bruce M. Kapron
* Lower Bounds for Non-Black-Box Zero Knowledge, Boaz Barak, Yehuda
Lindell, Salil Vadhan
* General Composition and Universal Composability in Secure
Multiparty Computation, Yehuda Lindell
* Bounded-Concurrent Secure Two-Party Computation in a Constant
Number of Rounds, Rafael Pass and Alon Rosen
SESSION 10: 5:10pm - 6:30pm, Chair: Avi Wigderson
* Solving Sparse, Symmetric, Diagonally-Dominant, Linear Systems in
Time O(m^1.31), Daniel Spielman and Shang-Hua Teng
* Separating the Power of Monotone Span Programs over Different
Fields, Amos Beimel and Enav Weinreb
* A group-theoretic approach to fast matrix multiplication, Henry
Cohn and Christopher Umans
* Representing Boolean Functions by Symmetric Polynomials, Nayantara
Bhatnagar and Parikshit Gopalan and Richard J. Lipton
------------------------------------------------------------------------
Tuesday October 14th 2003
Morning
SESSION 11: 8:45 am - 10:25 am, Chair: Madhu Sudan
* Smoothening Helps: A Probabilistic Analysis of the Multi-Level
Feedback Algorithm, Luca Becchetti and Stefano Leonardi and
Alberto Marchetti-Spaccamela and Guido Schaefer and Tjark Vredeveld
* Stability and Efficiency of a Random Local Load Balancing
Protocol, Aris Anagnostopoulos and Adam Kirsch and Eli Upfal
* Gossip-Based Computation of Aggregate Information, David Kempe and
Alin Dobra and Johannes Gehrke
* Broadcasting Algorithms in Radio Networks with Unknown Topology,
Artur Czumaj and Wojciech Rytter
* Switch Scheduling via Randomized Edge Coloring, Gagan Aggarwal and
Rajeev Motwani and Devavrat Shah and An Zhu
SESSION 12: 10:50am - 12:10pm, Chair: Dana Ron
* On the Impossibility of Dimension Reduction in $\ell_1$, Bo
Brinkman and Moses Charikar
* Clustering with Qualitative Information, Moses Charikar and
Venkatesan Guruswami and Anthony Wirth
* Bounded geometries, fractals, and low--distortion embeddings,
Anupam Gupta and Robert Krauthgamer and James R. Lee
* On Levels in Arrangements of Curves, II: A Simple Inequality and
Its Consequences, Timothy M. Chan
Lunch (Provided)
Afternoon
SESSION 13: 1:40pm - 2:20pm, Chair: Manindra Agarwal
* The complexity of homomorphism and constraint satisfaction
problems seen from the other side, Martin Grohe
* Towards a dichotomy theorem for the Counting Constraint
Satisfaction Problem, Andrei A. Bulatov and Victor Dalmau
SESSION 14: 2:40pm - 4:00pm, Chair: Monika Henzinger
* Towards a Characterization of Truthful Combinatorial Auctions, Ron
Lavi and Ahuva Mu'alem and Noam Nisan
* Strategy Proof Mechanisms via Primal-Dual Algorithms, Martin Pal
and Eva Tardos
* The Value of Knowing a Demand Curve: Bounds on Regret for On-Line
Posted-Price Auctions, Robert Kleinberg and Tom Leighton
* Approximation Via Cost-Sharing: A Simple Approximation Algorithm
for the Multicommodity Rent-or-Buy Problem, Anupam Gupta and Amit
Kumar and Martin Pal and Tim Roughgarden
SESSION 15: 4:20pm - 5:40pm, Chair: Dana Randall
* The Ising model on trees: Boundary conditions and mixing time,
Fabio Martinelli and Alistair Sinclair and Dror Weitz
* Logconcave Functions: Geometry and Efficient Sampling Algorithms,
Laszlo Lovasz and Santosh Vempala
* Simulated Annealing in Convex Bodies and an O*(n^4) Volume
Algorithm, Laszlo Lovasz and Santosh Vempala
* A Non-Markovian Coupling for Randomly Sampling Colorings, Thomas
P. Hayes and Eric Vigoda