(Message inbox:13) Return-Path: Received: from RI.CMU.EDU by missing.link.cs.cmu.edu id aa21822; 7 Aug 96 2:59 EDT Received: from hearnnt.nic.surfnet.nl by RI.CMU.EDU id aa19997; 7 Aug 96 2:58:56 EDT Received: from hearnnt (192.87.5.133) by hearnnt.nic.surfnet.nl (LSMTP for Windows NT v1.0a) with SMTP id 7C8FD3A0 ; Wed, 7 Aug 1996 8:57:39 +0200 Received: from NIC.SURFNET.NL by NIC.SURFNET.NL (LISTSERV release 1.8b) with NJE id 5823 for DMA-LIST@NIC.SURFNET.NL; Wed, 7 Aug 1996 08:59:11 +0200 Received: from HEARN (NJE origin SMTP@HEARN) by HEARN.NIC.SURFNET.NL (LMail V1.2a/1.8a) with BSMTP id 1558; Wed, 7 Aug 1996 08:59:11 +0200 Received: from utmfu0.math.utwente.nl by HEARN.nic.SURFnet.nl (IBM VM SMTP V2R2) with TCP; Wed, 07 Aug 96 08:59:08 +0200 Received: by utmfu0.math.utwente.nl ($Revision: 1.36.108.11 $/16.2) id AA297221111; Wed, 7 Aug 1996 08:58:31 +0200 Full-Name: DMANET Mailer: Elm [revision: 66.36.1.1] Approved-By: DMANET Message-ID: <199608070658.AA297221111@utmfu0.math.utwente.nl> Date: Wed, 7 Aug 1996 08:58:30 METDST Reply-To: tompa@cs.washington.edu Sender: DMANET From: DMANET Subject: FOCS 96 schedule of talks To: Multiple recipients of list DMA-LIST FOCS 96 Information URL http://www.umiacs.umd.edu/events/FOCS96/ The Thirty-seventh Annual Symposium on Foundations of Computer Science (FOCS), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held in Burlington, Vermont on October 14-16, 1996. ----------------------------------------------------------------------- Monday, October 14, 9:00 - 10:35 Session 1A Chair: Rajeev Motwani Polynomial Time Approximation Scheme for Euclidean TSP and Other Geometric Problems by Sanjeev Arora The Regularity Lemma and Approximation Schemes for Dense Problems by Alan Frieze and Ravi Kannan A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems by Sanjeev Arora, Alan Frieze, and Haim Kaplan A Fully Polynomial Time Approximation Scheme for Strip Packing by Claire Kenyon and Eric Remila Session 1B Chair: Russell Impagliazzo Quantum Circuits With Mixed States by D. Aharonov and N. Nisan A Decision Procedure for Unitary Linear Quantum Cellular Automata by Christoph Durr and Miklos Santha Polynomial Simulations Of Decohered Quantum Computers by D. Aharonov and M. Ben-Or Fault-Tolerant Quantum Computation by Peter W. Shor Monday, 11:15 - 12:50 Session 2A Chair: David Karger Single-Source Unsplittable Flow by Jon Kleinberg The Optimal Path-Matching Problem by William H. Cunningham and James F. Geelen Short Paths in Expander Graphs by Jon Kleinberg and Ronitt Rubinfeld Spectral Partitioning Works: Planar Graphs and Finite Element Meshes by Daniel Spielman and Shang-Hua Teng Session 2B Chair: Chee Yap Computing Permanents Over Fields of Characteristic 3 by Grigory Kogan Solving System of Polynomial Congruences Modulo a Large Prime by Ming-Deh Huang and Yiu-Chung Wong Median Selection Requires $(2 + \epsilon)n$ Comparisons by Dorit Dor and Uri Zwick Faster Deterministic Sorting and Searching in Linear Space by Arne Andersson Monday, 2:15 - 3:50 Session 3A Chair: Baruch Schieber An Efficient Algorithm for Constructing Minimal Trellises for Codes over Abelian Groups by Vijay V. Vazirani, Huzur Saran, and B. Sundar Rajan Highly Fault-Tolerant Parallel Computation by Daniel A. Spielman Maximum Likelihood Decoding of Reed Solomon Codes by Madhu Sudan New Coding Techniques for Improved Bandwidth Utilization by Micah Adler Session 3B Chair: Sandy Irani Probabilistic Approximations of Metric Spaces and its Algorithmic Applications by Yair Bartal Factoring Graphs to Bound Mixing Rates by Neal Madras and Dana Randall Sampling According to the Multivariate Normal Density by Ravi Kannan and Guangxing Li Load Balancing and Density Dependent Jump Markov Processes by Michael Mitzenmacher Monday, 4:30 - 5:45 Session 4A Chair: Tandy Warnow Tree Data Structures for N-body Simulation by Richard Anderson Efficient Information Gathering on the Internet by Oren Etzioni, Steve Hanks, Tao Jiang, Richard M. Karp, Omid Madani, and Orli Waarts Approximate Option Pricing by Prasad Chalasani, Somesh Jha, and Isaac Saias Session 4B Chair: Dexter Kozen Temporal Logic and Semidirect Products: An Effective Characterization of the Until Hierarchy by Denis Therien and Thomas Wilke Equivalence in Finite-Variable Logics is Complete for Polynomial Time by Martin Grohe Simplified and Improved Resolution Lower Bounds by Paul Beame and Toniann Pitassi Tuesday, October 15, 9:00 - 10:00 Session 5 Chair: Martin Tompa Computationally Hard Algebraic Problems by Michael Rabin Tuesday, 10:30 - 12:05 Session 6A Chair: Tandy Warnow Approximating Unweighted k-Connectivity via Matching by Joseph Cheriyan and Ramakrishna Thurimella A 3-Approximation for the Minimum Tree Spanning k Vertices by Naveen Garg An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem by Guy Even, Seffi Naor, and Leonid Zosin Efficient Approximate and Dynamic Matching of Patterns Using a Labeling Paradigm by Suleyman Cenk Sahinalp and Uzi Vishkin Session 6B Chair: Yishay Mansour A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions by Avrim Blum, Alan Frieze, Ravi Kannan, and Santosh Vempala Property Testing and its Connection to Learning and Approximation by Oded Goldreich, Shafi Goldwasser, and Dana Ron On the Applications of Multiplicity Automata in Learning by Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, and Stefano Varricchio Learning Linear Transformations by Alan Frieze, Mark Jerrum, and Ravi Kannan Tuesday, 1:30 - 3:05 Session 7A Chair: S. Rao Kosaraju Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols by Friedhelm Meyer auf der Heide and Christian Scheideler Universal Stability Results in Adversarial Queueing Theory by Baruch Awerbuch, Antonio Fernandez, Jon Kleinberg, Tom Leighton, and Zhiyong Liu A General Approach to Dynamic Packet Routing with Bounded Buffers by Andrei Z. Broder, Alan M. Frieze, and Eli Upfal Path Coloring on the Mesh by Yuval Rabani Session 7B Chair: Anne Condon Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles by Roy Armoni, Michael Saks, Avi Wigderson, and Shiyu Zhou The Boolean Isomorphism Problem by Manindra Agrawal and Thomas Thierauf Potential of the Approximation Method by Kazuyuki Amano and Akira Maruoka Static Dictionaries on AC^0 RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient by Arne Andersson, Peter Bro Miltersen. Soren Riis, and Mikkel Thorup Tuesday, 3:45 - 5:20 Session 8A Chair: Chee Yap All Pairs Almost Shortest Paths by Dorit Dor, Shay Halperin, and Uri Zwick Computing Vertex Connectivity: New Bounds from Old Techniques by Monika Rauch Henzinger, Satish Rao, and Hal N. Gabow Better Lower Bounds for Halfspace Emptiness by Jeff Erickson Binary Search Partitions for Fat Rectangles by Pankaj K. Agarwal, Edward F. Grove, T. M. Murali, and Jeffrey Scott Vitter Session 8B Chair: Carsten Lund On the Knowledge Complexity of NP by Erez Petrank and Gabor Tardos Incoercible Multiparty Computation by Ran Canetti and Rosario Gennaro Pseudorandom Functions Revisited: The Cascade Construction by Mihir Bellare, Ran Canetti, and Hugo Krawczyk The Geometry of Coin-Weighing Problems by Noga Alon, Dmitry N. Kozlov, and Van H. Vu Wednesday, October 16, 9:00 - 10:00 Session 9 Chair: Rajeev Motwani Universal Data Compression and Portfolio Selection by Tom Cover Wednesday, 10:30 - 12:30 Session 10A Chair: Sandy Irani Near-Optimal Parallel Prefetching and Caching by Tracy Kimbrel and Anna Karlin New Algorithms for the Disk Scheduling Problem by Matthew Andrews, Michael A. Bender, and Lisa Zhang Optimal Interval Management in External Memory by Lars Arge and Jeffrey Scott Vitter Fast Fault-Tolerant Concurrent Access to Shared Objects by C. G. Plaxton and R. Rajaraman Fault Tolerant Data Structures by Yonatan Aumann and Michael Bender Session 10B Chair: Michael Luby Approximate Checking of Polynomials and Functional Equations by Funda Ergun, S. Ravi Kumar, and Ronitt Rubinfeld Efficient Self-Testing/Self-Correction of Linear Recurrences by S. Ravi Kumar and D. Sivakumar Verifying Identities by Sridhar Rajagopalan and Leonard J. Schulman Gadgets, Approximation, and Linear Programming by Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson Clique is Hard to Approximate Within $n^{1-\epsilon}$ by Johan Hastad -- ****************************************************** Contributions to be spread via DMANET are submitted to DMANET@math.utwente.nl Replies to a message carried on DMANET should NOT be addressed to DMANET but to the original sender. The original sender, however, is invited to prepare an update of the replies received and to communicate it via DMANET. DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)