Path: utzoo!utgpu!utcsri!arvind From: arvind@utcsri.UUCP (Arvind Gupta) Newsgroups: ut.theory Subject: THEORY NET: Preliminary Program STOC '88 Message-ID: <5772@utcsri.UUCP> Date: 6 Jan 88 15:07:25 GMT Article-I.D.: utcsri.5772 Posted: Wed Jan 6 10:07:25 1988 Distribution: ut Organization: CSRI, University of Toronto Lines: 284 *** REPLACE THIS LINE WITH YOUR MESSAGE *** Date: Mon, 28 Dec 87 15:13:28 CST From: Jeff Ullman Subject: Preliminary Program STOC '88 Monday, May 2, 1988. Session 1,9---10:20 am,Andrew Odlyzko. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. Michael Ben-Or, Hebrew University, Shafi Goldwasser, MIT, and Avi Wigderson, Hebrew University. Multiparty Unconditionally Secure Protocols. David Chaum, Centre for Mathematics and Computer Science, Claude Crepeau, MIT, and Ivaa Damgard, Aarhus Universitet. On the Power of Oblivious Transfer. Joe Kilian, MIT. How to Sign Given Any Trapdoor Function. Mihir Bellare and Silvio Micali, MIT. Coffee 10:20---10:50 am. Session 2,10:50 am---12:30 pm,Nancy Lynch. A Tradeoff Between Space and Efficiency for Routing Tables. David Peleg, Stanford University, and Eli Upfal, IBM Almaden. Reasoning About Knowledge and Time in Asynchronous Systems. Joseph Halpern and Moshe Vardi, IBM Almaden. Investigations of Fault-Tolerant Networks of Computers. Piotr Berman, Penn State University, and Janos Simon, University of Chicago. Toward a Non-Atomic Era: 1-Exclusion as a Test Case. Danny Dolev, IBM Almaden and Hebrew University, Eli Gafni, UCLA, and Nir Shavit, Hebrew University. A Time-Randomness Tradeoff for Oblivious Routing. David Peleg, Stanford University, and Eli Upfal, IBM Almaden. Lunch Session 3,2---5:30 pm,TBA. Non-Interactive Zero-Knowledge and its Applications. Manuel Blum, University of California, Berkeley, Paul Feldman and Silvio Micali, MIT. Multi-Prover Interactive Proofs: How to Remove Intractability. Michael Ben-Or, Hebrew University, Shafi Goldwasser, MIT, Joe Killian, MIT, and Avi Widerson, Hebrew University. A Knowledge-Based Analysis of Zero Knowledge. Joseph Halpern, IBM Almaden, Yoram Moses, Weizmann Institute, and Mark Tuttle, MIT. >From Scratch to Byzantine Agreement in Constant Expected Time. Paul Feldman and Silvio Micali, MIT. Coffee 3:20---3:50 pm. Session 4,3:50---5:30 pm,TBA. On Different Modes of Communication. Bernd Halstenberg and Rudiger Reischuk, Technische Hochschule Darmstadt. Virtual Memory Algorithms. Alok Aggarwal and Ashok Chandra, IBM Yorktown Heights. On the Communication Complexity of Graph Properties. Andras Hajnal, University of Illinois at Chicago and Hungarian Academy of Sciences, Wolfgang Maass, University of Illinois at Chicago, and Gyorgy Turan, University of Illinois at Chicago and Hungarian Academy of Sciences. Optimal Simulations by Butterfly Networks. Sandeep Bhatt, Yale University, Fan Chung, BellCore, Jia-Wei Hong, Beijing Computer Institute and Courant Institute of NYU, Tom Leighton, MIT, and Arnold Rosenberg, University of Massachusetts at Amherst. Energy Consumption in VLSI Circuits. Alok Aggarwal, Ashok Chandra, and Prabhakar Raghavan, IBM Yorktown Heights. \day Tuesday, May 3, 1988. Session 5,9---10:20 am,TBA. Random Instances of a Graph Coloring Problem are Hard. Ramarathnam Venkatesan and Leonid Levin, Boston University. Expressing Combinatorial Optimization Problems. Mihalis Yannakakis, AT\&T Bell Labs, Murray Hill. Optimization, Approximation, and Complexity Classes. Christos Papadimitriou, University of California, San Diego, and Mihalis Yannakakis, AT\&T Bell Labs, Murray Hill. Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved. Mark Jerrum and Alistair Sinclair, University of Edinburgh. Coffee 10:20---10:50 am. Session 6,10:50 am---12:30 pm,TBA. Relativized Polynomial Time Hierarchies Having Exactly K Levels. Ker-I Ko, SUNY at Stony Brook. Computing Algebraic Formulas with a Constant Number of Registers. Richard Cleve, University of Toronto. On the Power of White Pebbles. Balasubramanian Kalyanasundaram and George Schnitger, Penn State University. Learning in the Presence of Malicious Errors. M. Kearns and M. Li, Harvard University. Nondeterministic Linear Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space. Yuri Gurevich and Saharon Shelah, University of Michigan. Lunch Session 7,2---3:20 pm,TBA. Efficient String Matching. S. Rao Kosaraju, Johns Hopkins University. A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation. Michael Ben-Or, Hebrew University, and Prasoon Tiwari, IBM Yorktown Heights. Randomized Algorithms and Pseudorandom Numbers. Howard Karloff, University of Chicago, and Prabhakar Raghavan, IBM Yorktown Heights. Competitive Algorithms for On-line Problems. Mark Manasse, DEC SRC, Lyle McGeoch, Amherst College, and Daniel Sleator, Carnegie Mellon University. Coffee 3:20---3:50 pm. Session 8,3:50---5:30 pm,Herbert Edelsbrunner. Implicit Representation of Graphs. Sampath Kannan, Moni Naor, and Steven Rudich, University of California, Berkeley. Storing and Searching a Multikey Table. Amos Fiat and Moni Naor, University of California, Berkeley, Alexandro Sch\"affer, Stanford University, Jeanette Schmidt and Alan Siegel, Courant Institute of NYU. More Analysis of Double Hashing. George Lueker and Mariko Molodowitch, University of California, Irvine. Linearity and Unprovability of Set Union Problem. Martin Loebl and Jaroslav Ne\u set\u ril, Charles University and Universit\"at Bonn. More Perfect Hashing and Storing a Multikey Sparse Table. Amos Fiat and Moni Naor, University of California, Berkeley, Jeanette Schmidt and Alan Siegel, Courant Institute of NYU. \day Wednesday, May 4, 1988. Session 9,9---10:20 am,Greg Frederickson. A Faster Strongly Polynomial Minimum Cost Flow Algorithm. James Orlin, MIT. Finding Minimum-Cost Circulations by Canceling Negative Cycles. Andrew Goldberg, Stanford University. Detecting Cycles in Dynamic Graphs in Polynomial Time. S. Rao Kosaraju and Gregory F. Sullivan, Johns Hopkins University. An Effcient Matroid Partitioning Algorithm and Applications. Harold Gabow and Herbert Westermann, University of Colorado at Boulder. Coffee 10:20---10:50 am. Session 10,10:50 am---12:30 pm,John Reif. Geometry helps in matching. Pravin M. Vaidya, AT\&T Bell Labs, Murray Hill. Small Sets Supporting Fary Embeddings of Planar Graphs. Hubert de Fraysseix, CNRS, Janos Pach, Hungarian Academy of Sciences, and Richard Pollack, Courant Institute of NYU. Optimal Algorithms for Approximate Clustering. Tomas Feder, Stanford University, and Daniel Greene, Xerox PARC. Planning Constrained Motion. Steven Fortune and Gordon Wilfong, AT\&T Bell Labs, Murray Hill. Some Algebraic and Geometric Computations in PSPACE. John Canny, University of California, Berkeley. Lunch Session 11,2---3:20 pm,Jeffrey Ullman. Lower Bounds on the Complexity of Graph Properties. Valerie King, University of California, Berkeley. Decidable Optimization Problems for Database Logic Programs. Stavros Cosmadakis, IBM Yorktown Heights, Haim Gaifman, Hebrew University, Paris Kanellakis, Brown University, and Moshe Vardi, IBM Almaden. Polynomial Universal Traversing Sequences for Cycles Are Constructible. Sorin Istrail, Wesleyan University. Two Infinite Sets of Primes with Fast Primality Tests. Janos Pintz, Hungarian Academy of Sciences, William Steiger, Rutgers University, and Endre Szemer\'edi, Rutgers University and Hungarian Academy of Sciences. Coffee 3:20---3:50 pm. Session 12,3:50---5:30 pm,Richard Cole. Towards an Architecture-Independent Analysis of Parallel Algorithms. Christos Papadimitriou, University of California, San Diego, and Mihalis Yannakakis, AT\&T Bell Labs, Murray Hill. A Randomized Parallel Branch-and-Bound Procedure. Richard Karp and Yanjun Zhang, University of California, Berkeley. Almost-Optimum Speed-ups of Algorithms for Matching and Related Problems. Harold Gabow, University of Colorado at Boulder, and Robert Tarjan, Princeton University and AT\&T Bell Labs, Murray Hill. Using Smoothness to Achieve Parallelism. Leonard M. Adleman and Kireeti Kompella, University of Southern California. Monotone Circuits for Connectivity Require Super-logarithmic Depth. Mauricio Karchmer and Avi Wigderson, Hebrew University.