------------------------------------------------------------------------ Advance Program for STOC 1993. SUNDAY Session A: 9:20 - 10:30 am Session Chair: Pravin Vaidya, Univ. of Illinois at Urbana-Champaign Time: 9:20 am Title: Some Complexity Issues on the Simply Connected Regions of the Two-Dimensional Plane Authors: A. Chou, Clark University, K. Ko, SUNY at Stony Brook Time: 9:45 am Title: Quantum Complexity Theory Authors: E. Bernstein, University of California at Berkeley, U. Vazirani, University of California at Berkeley Time: 10:10 am Title: Thermodynamics of Computation and Information Distance Authors: Charles H. Bennett (IBM Watson Research Center), Peter Gacs (Boston University), Ming Li (University of Waterloo), Paul Vitanyi (CWI and University of Amsterdam), Wojciek Zurek (Los Alamos National Lab. and Santa Fe Institute) Time: 10:30 am Coffee Break Session B: 9:20 - 10:30 am Session Chair: David Peleg, Weizmann Institute, Israel Time: 9:20 am Title: Fully Polynomial Byzantine Agreement in t+1 Rounds Authors: J. Garay, IBM Watson Research Center, Y. Moses, Weizmann Institute Time: 9:45 am Title: Fast Asynchronous Byzantine Agreement with Optimal Resilience Authors: R. Canetti, Technion, T. Rabin, Hebrew University Time: 10:10 am Title: Asynchronous Secure Computation Authors: M. Ben-Or, Hebrew University, R. Canetti, Technion, O. Goldreich, Technion Time: 10:30 am Coffee Break Session A: 11:00 - 12:10 am Session Chair: Pravin Vaidya, Univ. of Illinois at Urbana-Champaign Time: 11:00 am Title: $k$ One-Way Heads Cannot Do String-Matching Authors: T. Jiang, McMaster University, M. Li, University of Waterloo Time: 11:25 am Title: A Theory of Parameterized Pattern Matching: Algorithms and Applications Author: B. Baker, AT & T Bell Labs. Time: 11:50 am Title: Multiple Matching of Rectangular Patterns Authors: R. Idury and A. Schaffer, Rice University Time: 12:10 pm Lunch Break Session B: 11:00 am - 12:10 pm Session Chair: David Peleg, Weizmann Institute, Israel Time: 11:00 am Title: Generalized FLP Impossibility Result for $t$-Resilient Asynchronous Computations Authors: E. Borowsky and E. Gafni, University of California at Los Angeles Time: 11:25 am Title: Wait-Free $k$-set Agreement is Impossible: The Topology of Public Knowledge Authors: M. Saks, Rutgers Univ. and Univ. of California at San Diego, F. Zaharoglou, Univ. of California at San Diego Time: 11:50 am Title: The Asynchronous Computability Theorem for $t$-Resilient Tasks Authors: M. Herlihy, DEC Cambridge Research Lab., N. Shavit, Tel-Aviv University Time: 12:10 pm Lunch Break Session A: 2:00 - 3:35 pm Session Chair: Michael Goodrich, The Johns Hopkins University Time: 2:00 pm Title: Linear Programming Without the Matrix Authors: C. Papadimitriou, Univ. of California at San Diego, M. Yannakakis, AT & T Bell Labs. Time: 2:25 pm Title: Comparison-Based Search in the Presence of Errors Authors: R. Borgstrom, The Johns Hopkins University, S. Kosaraju, The Johns Hopkins University Time: 2:50 pm Title: A Robust Model for Finding Optimal Evolutionary Trees Authors: M. Farach, DIMACS, S. Kannan, University of Arizona, T. Warnow, Sandia National Labs. Time: 3:15 pm Title: Maximum $k$-Chains in Planar Point Sets: Combinatorial Structure and Algorithms Authors: S. Felsner and L. Wernisch, Technische Universitaet Berlin Time: 3:35 pm Coffee Break Session B: 2:00 - 3:35 pm Session Chair: Anna Karlin, DEC Systems Research Center Time: 2:00 pm Title: Lower Bounds for Randomized Mutual Exclusion Authors: E. Kushilevitz, Harvard University, Y. Mansour, Tel-Aviv University and IBM Watson Research Center, M. Rabin, Harvard University, D. Zuckerman, MIT Time: 2:25 pm Title: Competitive Distributed File Allocation Authors: B. Awerbuch, MIT, Y. Bartal and A. Fiat, Tel-Aviv University Time: 2:50 pm Title: Contention in Shared Memory Algorithms Authors: C. Dwork, IBM Almaden Research Center M. Herlihy, DEC Cambridge Research Lab., O. Waarts, IBM Almaden Research Center Time: 3:15 pm Title: What Can be Computed Locally? Authors: M. Naor, IBM Almaden Research Center L. Stockmeyer, IBM Almaden Research Center Time: 3:35 pm Coffee Break Session A: 4:00 - 6:00 pm Session Chair: Michael Goodrich, The Johns Hopkins University Time: 4:00 pm Title: Reinventing the Wheel: An Optimal Data Structure for Connectivity Queries Authors: R. Cohen, US Coast Guard Academy, G. Di Battista, University di Roma, A. Kanevsky, Texas A & M University Time: 4:25 pm Title: Locality Based Graph Coloring Authors: M. Szegedy, AT & T Bell Labs., S. Vishwanathan, University of Chicago Time: 4:50 pm Title: Separator Based Sparsification for Dynamic Planar Graph Algorithms Authors: D. Eppstein, University of California at Irvine, Z. Galil, Columbia University and Tel-Aviv University, G. Italiano, IBM Watson Research Center, T. Spencer, University of Nebraska at Omaha Time: 5:15 pm Title: Polynomial Space Polynomial Delay Algorithms for Listing Families of Graphs Authors: L. Goldberg, Sandia National Labs. Time: 5:40 pm Title: A Linear Time Algorithm for Finding Tree-Decompositions of Small Treewidth Authors: H. Bodlaender, Utrecht University Session B: 4:00 pm - 6:00 pm Session Chair: Andrew C.-C. Yao, Princeton University Time: 4:00 pm Title: More Deterministic Simulation in Logspace Authors: N. Nisan, Hebrew University, D. Zuckerman, MIT Time: 4:25 pm Title: Expanders that Beat the Eigenvalue Bound: Explicit Construction and Applications Authors: A. Wigderson, Hebrew University, D. Zuckerman, MIT Time: 4:50 pm Title: The Biased Coin Problem Authors: R. Boppana and B. Narayanan, New York University Time: 5:15 pm Title: Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension Authors: N. Linial, Hebrew University, M. Luby, ICSI and University of California at Berkeley, M. Saks, Rutgers University and Univ. of California at San Diego, D. Zuckerman, MIT Time: 5:40 pm Title: Constructing Small Sample Spaces Satisfying Given Constraints Authors: D. Koller, Stanford University and IBM Almaden Research Center, N. Megiddo, IBM Almaden Research Center and Tel-Aviv Univ. END OF SESSION (B) MONDAY Session A: 9:20 - 10:20 am Session Chair: Richard Beigel, Yale University Time: 9:20 am Title: On the Hardness of Approximating Minimization Problems Authors: C. Lund and M. Yannakakis, AT & T Bell Labs. Time: 9:45 am Title: Efficient Probabilistically Checkable Proofs: Applications to Approximation Authors: M. Bellare, IBM Watson Research Center, S. Goldwasser, MIT, C. Lund, AT & T Bell Labs., A. Russell, MIT Time: 10:10 am Title: Probabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions Authors: A. Condon, University of Wisconsin at Madison, J. Feigenbaum, C. Lund, and P. Shor, AT & T Bell Labs. Time: 10:30 am Coffee Break Session B: 9:20 - 10:30 am Session Chair: Avrim Blum, Carnegie Mellon University Time: 9:20 am Title: Efficient Learning of Typical Finite Automata from Random Walks Authors: Y. Freund, Univ. of California at Santa Cruz, M. Kearns, AT & T Bell Labs., D. Ron, Hebrew University, R. Rubinfeld, Cornell University, R. Schapire, AT & T Bell Labs., L. Sellie, University of Chicago Time: 9:45 am Title: Finiteness Results for Sigmoidal "Neural" Networks Authors: A. Macintyre, University of Oxford, E. Sontag, Rutgers University Time: 10:10 am Title: Bounds for the Computational Power and Learning Complexity of Analog Neural Nets Authors: W. Maass, Technische Universitaet Graz Time: 10:30 am Coffee Break Session A: 11:00 am - 12:10 pm Session Chair: Michael Paterson, University of Warwick Time: 11:00 am Title: Proportionate Progress: A Notion of Fairness in Resource Allocation Authors: S. Baruah, N. Cohen, C. Plaxton, D. Varvel, Univ. of Texas at Austin Time: 11:25 am Title: Self-Routing Superconcentrators Authors: N. Pippenger, University of British Columbia Time: 11:50 am Title: Space-Efficient Scheduling of Multithreaded Computations Authors: R. Blumofe and C. Leiserson, MIT Lunch Break Session B: 11:00 am - 12:10 pm Session Chair: Avrim Blum, Carnegie Mellon University Time: 11:00 am Title: Cryptographic Hardness of Distribution-Specific Learning Authors: M. Kharitonov, Stanford University Time: 11:25 am Title: How to Use Expert Advice Authors: N. Cesa-Bianchi, Univ. di Milano Y. Freund, U. of California, Santa Cruz, D. Haussler, Univ. of California, Santa Cruz, D. Helmbold, Univ. of California, Santa Cruz, R. Schapire, AT & T Bell Labs., M. Warmuth, Univ. of California, Santa Cruz Time: 11:50 am Title: Efficient Noise-Tolerant Learning from Statistical Queries Author: M. Kearns, AT & T Bell Labs. Time: 12:10 pm Lunch Break Session A: 2:00 - 3:35 pm Session Chair: Chee Yap, New York University Time: 2:00 pm Title: Online Load Balancing and Network Flow Authors: S. Phillips, Stanford University, J. Westbrook, Yale University Time: 2:25 pm Title: Markov Chains, Computer Proofs, and Average-Case Analysis of Best Fit Bin Packing Authors: E. Coffman, D. Johnson and P. Shor, AT & T Bell Labs., R. Weber, Cambridge University Time: 2:50 pm Title: On-Line Algorithms for Cache Sharing Authors: M. Bern and D. Greene, Xerox PARC, A. Raghaunathan, Univ. of California at Davis Time: 3:15 pm Title: Angles of Planar Triangular Graphs Authors: G. DiBattista and L. Vismara, Univ. Di Roma, "La Sapienza" Time: 3:35 pm Coffee Break Session B: 2:00 - 3:35 pm Session Chair: Joe Kilian, NEC Research Institute Time: 2:00 pm Title: Many Birds with One Stone: Multi-Objective Approximation Algorithms Authors: R. Ravi, Brown University, M. Marathe, S. Ravi, D. Rosenkrantz, and H. Hunt, SUNY at Albany Time: 2:25 pm Title: A Parallel Approximation Algorithm for Positive Linear Programming Authors: M. Luby, ICSI and Univ. of California at Berkeley, N. Nisan, Hebrew University Time: 2:50 pm Title: Randomness-Optimal Unique Element Isolation, with Applications to Perfect Matching and Related Problems Authors: S. Chari, Cornell University, P. Rohatgi, Cornell University, A. Srinivasan, Cornell University Time: 3:15 pm Title: Decision Trees: Old and New Results Author: R. Fleischer, Max-Planck Institute Time: 3:35 pm Coffee Break Session A: 4:00 pm - 5:35 pm Session Chair: Alok Aggarwal, IBM Research Division Time: 4:00 pm Title: A Deterministic Algorithm for the Three-Dimensional Diameter Problem Authors: J. Matousek, Universita Karlova and Freie University, Berlin O. Schwarzkopf, Universiteit Utrecht Time: 4:25 pm Title: Matrix Searching with the Shortest Path Metric Authors: J. Hershberger, DEC Systems Research Center, S. Suri, Bell Communications Research Time: 4:50 pm Title: Improved Bounds on Weak Epsilon-Nets for Convex Sets Authors: B. Chazelle, Princeton University, H. Edelsbrunner, University of Illinois at Urbana-Champaign, M. Grigni, Princeton University, L. Guibas, DEC Systems Research Center and Stanford University, M. Sharir, Tel-Aviv University, E. Welzl, Freie University, Berlin Time: 5:15 pm Title: Piecewise Linear Paths Among Convex Obstacles Authors: M. de Berg, Universiteit Utrecht, J. Matousek, Universita Karlova and Freie University, Berlin O. Schwarzkopf, Universiteit Utrecht Session B: 4:00 pm - 6:00 pm Session Chair: Andrew C.-C. Yao, Princeton University Time: 4:00 pm Title: Depth Reduction for Noncommutative Arithmetic Circuits Authors: E. Allender, Princeton University, J. Jiao, Rutgers University Time: 4:25 pm Title: Modified Ranks of Tensors and the Size of Circuits Authors: P.Pudlak, Universitaet Dortmund, V. Rodl, Emory University Time: 4:50 pm Title: Characterizing Non-Deterministic Circuit Size Authors: M. Karchmer, MIT, A. Wigderson, Hebrew University Time: 5:15 pm Title: Size-Depth Trade-Offs for Threshold Circuits Authors: R. Impagliazzo, R. Paturi, University of California at San Diego, M. Saks, Rutgers University and University of California at San Diego Time: 5:40 pm Title: Simulating Threshold Circuits by Majority Circuits Authors: M. Goldmann, Royal Institute of Technology, M. Karpinski, University of Bonn END OF SESSION (B) TUESDAY Session A: 9:20 - 10:30 am Session Chair: Michael Paterson, University of Warwick Time: 9:20 am Title: Multi-Scale Emulation: A Technique for Reconfiguring Arrays with Faults Authors: R. Cole, New York University, B. Maggs, NEC Research Institute, R. Sitaraman, Princeton University Time: 9:45 am Title: How Much Can Hardware Help Routing? Authors: A. Borodin, Univ. of Toronto and IBM Center for Advanced Research, P. Raghavan, IBM Watson Research Center, B. Schieber, IBM Watson Research Center, E. Upfal, IBM Almaden Research Center and Weizmann Institute Time: 10:10 am Title: Routing Permutations on Graphs via Matchings Authors: N. Alon, Tel-Aviv University, F. Chung, Bell Communications Research and Harvard University, R. Graham, Bell Communications Research and Rutgers University Time: 10:30 am Coffee Break Session B: 9:20 - 10:30 am Session Chair: Paris Kannelakis, Brown University Time: 9:20 am Title: Parametric Real-Time Reasoning Authors: R. Alur, AT & T Bell Labs., T. Henzinger, Cornell University, M. Vardi, IBM Almaden Research Center Time: 9:45 am Title: Constant Time Factors Do Matter Authors: N. Jones, University of Copenhagen Time: 10:10 am Title: Monotone Monadic SNP and Constraint Satisfaction Authors: T. Feder, IBM Almaden Research Center, M. Vardi, IBM Almaden Research Center Time: 10:30 am Coffee Break Session A: 11:00 am - 12:10 pm Session Chair: Sandeep Bhatt, Bell Communications Research Time: 11:00 am Title: On-Line Load Balancing with Applications to Machine Scheduling and Virtual Circuit Routing Authors: J. Aspnes, IBM Almaden Research Center, Y. Azar, DEC Systems Research Center, A. Fiat, Tel-Aviv University, S. Plotkin, Stanford University O. Waarts, IBM Almaden Research Center Time: 11:25 am Title: Wait-Free Approximate Load Balancing Authors: W. Aiello, Bell Communications Research, B. Awerbuch, MIT, B. Maggs, NEC Research Institute, S. Rao, NEC Research Institute Time: 11:50 am Title: Optimal Online Scheduling of Parallel Jobs with Dependencies Authors: A. Feldmann, Carnegie Mellon University, M. Kao, Duke University, J. Sgall, Carnegie Mellon University, S. Teng, MIT Time: 12:10 pm Lunch Break Session B: 11:00 am - 12:10 pm Session Chair: David Peleg, Weizmann Institute, Israel Time: 11:00 am Title: Time Optimal Self-Stabilizing Synchronization Authors: B. Awerbuch, MIT, S. Kutten, IBM Watson Research Center, Y. Mansour, Tel-Aviv University and IBM Watson Research Center, B. Patt-Shamir, MIT, G. Varghese, DEC Time: 11:25 am Title: Fast Perfect-Information Leader-Election Protocol with Linear Immunity Authors: J. Cooper and N. Linial, Hebrew University Time: 11:50 am Title: Cryptographic Defense Against Traffic Analysis Authors: C. Rackoff, Univ. of Toronto D. Simon, Univ. of Toronto Time: 12:10 pm Lunch Break Session A: 2:00 - 3:35 pm Session Chair: F. Tom Leighton, MIT Time: 2:00 pm Title: Excluded Minors, Network Decomposition, and Multicommodity Flow Authors: P. Klein, Brown University S. Plotkin, Stanford University S. Rao, NEC Research Insititute Time: 2:25 pm Title: Improved Bounds on the Max-Flow Min-Cut Ratio for Multicommodity Flows Authors: S. Plotkin, Stanford University E. Tardos, Cornell University Time: 2:50 pm Title: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications Authors: N. Garg and V. Vazirani, IIT Delhi, M. Yannakakis, AT & T Bell Labs. Time: 3:15 pm Title: A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems Authors: D. Williamson, MIT M. Goemans, MIT, M. Mihail, Bell Communications Research, V. Vazirani, IIT Delhi Time: 3:35 pm Coffee Break Session B: 2:00 - 3:35 pm Session Chair: Martin Tompa, University of Washington, Seattle Time: 2:00 pm Title: Time-Space Trade-Offs for Undirected ST-Connectivity on a JAG Authors: J. Edmonds, Univ. of Toronto Time: 2:25 pm Title: Short Random Walks on Graphs Authors: G. Barnes, Max-Planck Institute, U. Feige, Weizmann Institute Time: 2:50 pm Title: Matchings in Lattice Graphs Authors: C. Kenyon, Ecole Normale Superiere de Lyon, D. Randall, Univ. of California at Berkeley, A. Sinclair, Univ. of Edinburgh at ICSI Time: 3:15 pm Title: Deterministic Coding for Interactive Communication Authors: L. Schulman, Univ. of California, Berkeley Time: 3:35 pm Coffee Break Session A: 4:00 pm - 5:15 pm Session Chair: F. Tom Leighton, MIT Time: 4:00 pm Title: An $O \tilda ( n^2 )$ Algorithm for Minimum Cuts Authors: D. Karger, Stanford University C. Stein, Dartmouth College Time: 4:25 pm Title: Finding Minimum-Quotient Cuts in Planar Graphs Authors: J. Park and C. Phillips, Sandia National Labs. Time: 4:50 pm Title: The Network Inhibition Problem Authors: C. Phillips, Sandia National Labs. End of STOC 1993 -- Session (A) Session B: 4:00 pm - 5:15 pm Session Chair: Joe Kilian, NEC Research Insititute Time: 4:00 pm Title: Checking Approximate Computations Over the Reals Authors: S. Ar, Princeton University, M. Blum, University of California at Berkeley, B. Codenotti, ICSI at Berkeley, P. Gemmell, University of California at Berkeley Time: 4:25 pm Title: On the Generation of Multivariate Polynomials which are Hard to Factor Authors: A. Shamir, The Weizmann Institute Time: 4:50 pm Title: Counting Points on Curves Over Finite Fields Authors: J. von zur Gathen, University of Toronto, M. Karpinski, University of Bonn, I. Shparlinski, Macquarie University End of STOC 1993 -- Session (B)