Saturday October 11th 2003

Tutorials Day at Radcliffe Institute for Advanced Study

Tutorial 1:  9:30am - 11:30 pm, Chair: Paul Beame

Avrim Blum: Machine Learning: my favorite results, directions, and open problems. Abstract

Lunch (on your own)

Tutorial 2:   1:20pm - 3:20 pm, Chair: Michael Mitzenmacher

Dana Randall: Mixing. Abstract

Tutorial 3: 3:50pm-5:50pm,  Chair: Avi Wigderson

Eli Upfal: Performance Analysis of Dynamic Network Processes. Abstract

Welcome Reception  at the University Park Hotel at MIT: 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

• 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 Kalai
  

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
• Proving Hardcore Predicates Using List Decoding, Adi Akavia and Shafi Goldwasser and Muli Safra

• 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
• 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

• 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

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

• 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
• Rank Bounds and Integrality Gaps for Cutting Planes Procedures, Josh Buresh-Oppenheim and Nicola Galesi and Shlomo Hoory and Avner Magen and Toniann Pitassi

Afternoon

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

• 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

• 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
• Symmetric Polynomials over Z_m and Simultaneous Communication Protocols, 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

• Average Case and Smoothed Competitive 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

• 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

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

• A Non-Markovian Coupling for Randomly Sampling Colorings, Thomas P. Hayes and Eric Vigoda
• 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