Article: 1986 of cmu.cs.theory Newsgroups: cmu.cs.theory Path: cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!glmiller@ABACUS.THEORY.CS.CMU.EDU From: glmiller@ABACUS.THEORY.CS.CMU.EDU ( Gary Miller) Subject: STOC96 Program Status: RO Message-ID: <199601191400.GAA07574@pollux.usc.edu> X-Mozilla-Status: 0001 Sender: news+@cs.cmu.edu Original-To: Local Distribution Reply-To: Theory-A - TheoryNet World-Wide Events , Gary Miller Approved-By: Theory-A - TheoryNet World-Wide Events Organization: School of Computer Science, Carnegie Mellon Original-Sender: TheoryNet List Date: Sat, 3 Feb 1996 04:23:23 GMT Approved: bboard-news_gateway Comments: To: Multiple recipients of list THEORY-A Lines: 559 Below is the STOC96 program. Please report any correction to Gary Miller at glmiller@cs.cmu,edu Conference Title: 28th Annual ACM Symposium on Theory of Computing (STOC) Conference Committees General Chair: David S. Johnson, AT&T Bell Laboratories Program Chair: Gary L. Miller, Carnegie-Mellon University Tutorials Chair: (none) Publicity and Publications Chair: (none) Finance Chair: Alok Aggarwal, IBM Research Advisory Committee: (none) Program Committee: Sanjeev Arora (Princeton) Jin-Yi Cai (SUNY Buffalo) Alan Frieze (CMU) Michel Goemans (MIT) Monika R. Henzinger (Cornell) Maurice Herlihy (Brown) Erich Kaltofen (NCSU) Joe Kilian (NECI) Thomas Lengauer (GMD) Gary L. Miller (CMU) Noam Nisan (Hebrew) Serge Plotkin (Stanford) Pavel Pudlak (Prague) Abhiram Ranade (Berkeley/IIT Bombay) Ronitt Rubinfeld (Cornell/MIT) Alistair Sinclair (Berkeley) ShangHua Teng (UMN) Les Valiant (Harvard) Vijay Vazirani (Georgia Tech) Sessions schedule. Session 1A: Wednesday, May 22, 1996 9:20am-10:55am Session Chair: Jin-Yi Cai (SUNY Buffalo) 9:20am The Linear-Array Conjecture of Communication Complexity is False Eyal Kushilevitz, Technion, Nathan Linial, Hebrew Institute, Rafail Ostrovsky, Bellcore 9:45am Testing of the long code and hardness for clique Johan Hastad, Royal Institute of Technology 10:10am The space complexity of approximating the frequency moments Noga Alon, Yossi Matias, Mario Szegedy AT/&T Bell Labs 10:35am Deterministic Restrictions in Circuit Complexity Shiva Chaudhuri, Max-Planck Institut f\'{u}r Informatik, Jaikumar Radhakrishnan, Tata Institute of Fundamental Research Session 1B: Wednesday, May 22, 1996 9:20am-10:55am Session Chair: Monika R. Henzinger (Cornell) 9:20am Fast Algorithms for k-Node Connectivity Augmentation and Related Problems Joseph Cheriyan, Waterloo, Ramakrishna Thurimella, Univ of Denver 9:45am Approximating s-t minimum cuts in O(n^2) time Andras A. Benczur, David R. Karger, MIT 10:10am Minimum Cuts in Near-Linear Time David R. Karger, MIT 10:35am Deterministic \tilde{O}(nm) Time Edge-Splitting in Undirected Graphs Hiroshi Nagamochi, Toshihide Ibaraki, Kyoto coffee break: 10:55am - 11:30am session number: 2 session title: (Talk by Knuth Prize Winner) time: 11:30am - 12:30pm Lunch: 12:30pm - 2:00pm Session 3A: Wednesday, May 22, 1996 2:00pm - 3:35pm Session Chair: Ronitt Rubinfeld (Cornell/MIT) 2:00pm Learning Sat-k-DNF formulas from membership queries F. Bergadano, Universit\`{a} di Torino D. Catalano, Universit\`{a} di Catania S. Varricchio, Universit\`{a} di L' Aquila 2:25pm The Monotone Theory for the PAC-Model Nader H. Bshouty, Calgary 2:55pm Noise-tolerant Learning Near the Information-theoretic Bound N. Cesa-Bianchi, Universit\`{a} di Milano E. Dichterman, Technion P. Fischer, Universit\"{a}t Dortmund H.U. Simon Hans Ulrich Simon, Univerisi\"{a}t Dortmund 3:20pm Noise-tolerant Distribution-Free Learning of General Geometric Concepts Nader Bshouty, Calgary Sally Goldman, David Mathias, Subhash Suri, Washington University Hisao Tamaki, IBM Tokyo Session 3B: Wednesday, May 22, 1996 2:00pm - 3:35pm Session Chair: Erich Kaltofen (NCSU) 2:00pm The complexity of matrix rank and feasible systems of linear equations E. Allender, Rutgers R. Beals, DIMACS, Rutgers M. Ogihara, Rochester 2:25pm Computing Roadmaps of Semi-algebraic Sets Saugata Basu, Richard Pollack, Courant Marie-Fran\c{c}oise Roy, IRMAR, Universit\'{e} de Rennes 2:55pm Using the Groebner basis algorithm to find proofs of unsatisfiability Matthew Clegg, UASD Jeffery Edmonds, York Russell Impagliazzo, UCSD 3:20pm Sparsity Considerations in Dixon Resultants Deepak Kapur, Tushar Saxena, SUNY Albany Coffee Break: 3:35pm - 4:05pm Session 4A: Wednesday, May 22, 1996 4:05pm - 5:40pm Session Chair: Monika R. Henzinger (Cornell) 4:05pm Efficient 3-d Range Searching in External Memory Darren Erick Vengroff, Brown, Duke Jeffery Scott Vitter, Duke 4:30pm Purely Functional Representations of Catenable Sorted Lists Haim Kaplan, Robert E. Tarjan, Princeton 4:55pm A fast quantum mechanical algorithm for database search Lov K. Grover, AT\&T Bell Labs Session 4B: Wednesday, May 22, 1996 4:05pm - 5:40pm Session Chair: Ronitt Rubinfeld (Cornell/MIT) 4:05pm Constructing Evolutionary Trees in the Presence of Polymorphic Characters Maria Bonet, U of Penn Cynthia Phillips, Sandia Tandy J. Warnow, Shibu Yooseph, U of Penn 4:30pm Efficient Algorithms for Inverting Evolution Martin Farach, Rutgers Sampath Kannan, U of Penn ------------------------ Session 5A: Thursday, May 23, 1996 9:20am - 10:55am Session Chair: Maurice Herlihy (Brown) 9:20am Modular Competitiveness for Distributed Algorithms James Aspnes, Yale Orli Waarts, UC Berkeley 9:45am Communication-Efficient Parallel Sorting Michael T. Goodrich, John Hopkins 10:10am Automatic Methods for Hiding Latency in High Bandwidth Networks Matthew Andrews, Tom Leighton, MIT P. Takis Metaxas, Wellesley Lisa Zhang, MIT, 10:35am An $O(n \log n)$-Size Fault-Tolerant Sorting Network Yuan Ma, Stanford Session 5B: Thursday, May 23, 1996 9:210am - 10:55am Session Chair: Alistair Sinclair (UC Berkeley) 9:20am On Extracting Randomness From Weak Random Sources Amnon Ta-Shma, Hebrew 9:45am Randomness-Optimal Sampling, Extractors, and Constructive Leader Election David Zuckermann, Austin 10:10am Generating Random Spanning Trees More Quickly than the Cover Time David Bruce Wilson, MIT 10:35am Towards an analysis of local optimization algorithms Tassos Dimitriou, Russell Impagliazzo, UCSD Coffee break: 10:55am - 11:25am Session 6A: Thursday, May 23, 1996 11:25am - 12:35pm Session Chair: Jin-Yi Cai (SUNY Buffalo) 11:25am Evaluation may be easier than generation Moni Naor, Weizmann 11:50am The PL Hierarchy Collapses Mitsunori Ogihara, Rochester 12:15pm Convergence Complexity of Optimistic Rate Based Flow Control Algorithms Yehuda Afek, Yishay Mansour, Zvi Ostfeld, Tel-Aviv Session 6B: Thursday, May 23, 1996 11:25 - 12:35pm Session Chair: ShangHua Teng (UMN) 11:25am Generating Hard Instances of Lattice Problems M. Ajtai, IBM Almaden 11:50am Translational Polygon Containment and Minimal Enclosure Using Linear Programming Based Restriction Victor J. Milenkovic, U of Miami 12:15pm Pushing disks together--the continuous-motion case Marshall Bern, Xerox Amit Sahai, UC Berkeley Lunch: 12:35pm - 2:00pm Session 7A: Thursday, May 23, 1996 2:00pm - 3:35pm Session Chair: Michel Goemans (MIT) 2:00pm A Threshold of ln n for approximating set cover Uriel Feige, Weizmann 2:25pm Fast Algorithms for parametric scheduling come from extensions to parametric Maximum Flow S. Thomas McCormick, UBC 2:50pm Towards a syntactic characterization of ptas Sanjeev Khanna, Rajeev Motwani, Stanford 3:15pm Efficient Approximation Algorithms for MAX~CUT and COLORING Philip Klein, Hsueh-I Lu, Brown Session 7B: Thursday, May 23, 1996 2:00pm - 3:35pm Session Chair: Abhiram Ranade (Berkeley/IIT Bombay) 2:00pm Dynamic Deflection Routing on Arrays Andrei Border, Digital Systems Research Eli Upfal, IBM Almaden 2:25pm Universal Algorithms for Store-and-Forward and Wormhole Routing Robert Cypher, Johns Hopkins Friedhelm Meyer auf der Heide, Christian Scheideler, Berthold Vo\'{c}king, Paderborn 2:50pm Distributed Packet Switching in Arbitrary Networks Yuval Rabini, Eva Tardos Cornell 3:15pm Adversarial Queueing Theory Allan Borodin, Toronto Jon Kleinberg, MIT Prabhakar Raghavan, IBM Almaden Madhu Sudan, David P. Williamson, IBM T.J.Watson Coffee break: 3:35pm - 4:05pm Session 8A: Thursday, May 23, 1996 4:05pm - 5:40pm Session Chair: Gary L. Miller (CMU) 4:05pm Computing Betti numbers via combinatorial Laplacians Joel Friedman, UBC 4:30pm Embedding graphs in an arbitrary surface in linear time Bojan Mohar, University of Ljubljana 4:55pm Algorithms for Manifolds and Simplicial Complexes in Euclidean 3-Space Tamal K. Dey, IIT India Sumanta Guha, University of Wisconsin 5:20pm On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-algebraic Sets Saugata Basu, Courant Session 8B: Thursday, May 23, 1996 4:05pm - 5:40pm Session Chair: Vijay Vazirani (Georgia Tech) 4:05pm Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Maching Hans Kellerer, Universit\"{a}t Graz Thomas Tautenhahn, Universit\"{a}t Magdeburg Gerhard J. Woeginger, Eindhoven 4:30pm How Good is the Goemans-Williamson MAX CUT Algorithm? Howard J. Karloff, Georgia Tech 4:55pm A Tight Analysis of the Greedy Algorithm for Set Cover Petr Slavik, SUNY Buffalo 5:20pm A constant-factor approximation algorithm for the k-MST problem Avrim Blum, R. Ravi, Santosh Vempala, CMU Friday, May 24, 1996 Session 9A: Friday, May 24, 1996 9:20am - 10:30am Session Chair: Thomas Lengauer (GMD) 9:20am Reconstructing a Three-Dimensional Model with Arbitrary Errors Bonnie Berger, Jon Kleinberg, Tom Leighton, MIT 9:45am On the Boosting Ability of Top-Down Decision Tree Learning Algorithms Michael Kearns, AT/&T Bell Lab. Yishay Mansour, Tel-Aviv 10:10am Robot Navigation with Range Queries Dana Angluin, Jeffery Westbrook, Wenhong Zhu, Yale Session 9B: Friday, May 24, 1996 9:20am - 10:30am Session Chair: Joe Kilian (NECI) 9:20am Correlated Pseudorandomness and the Complexity of Private Computations Donald Beaver, Transarc Corp. 9:45am Digital Signets for Protection of Digital Information Cynthia Dwork, Jeffery Lotspiech, IBM Almaden Moni Naor, Weizmann 10:10am Witness-Based Cryptographic Program Checking and Robust Function Sharing Yair Frankel, Peter Gemmell, Sandia National Labs, Moti Yung, IBM T.J. Watson Coffee break: 10:30am - 11:00am Session 10A: Friday, May 24, 1996 11:00am - 12:20pm Session Chair: Serge Plotkin (Stanford) 11:00am Non-Expansive Hashing Nathan Linial, Ori Sasson, Hebrew 11:25am Making Commitments in the Face of Uncertainty: How to Pick a Winner Almost Every Time Baruch Awerbuch, Johns Hopkins, Yossi Azar, Amos Fiat, Tel Aviv, Tom Leighton, MIT 11:50am Lower Bounds for On-line Graph Problems with Application to On-Line Circuit and Optical Routing Yair Bartal, Berkeley, Amos Fiat, Tel Aviv Univ. Stefano Leonardi, Universit\`{a} di Roma Session 10B: Friday, May 24, 1996 11:00am - 12:10pm Session Chair: Noam Nisan (Hebrew) 11:00am Characterizing Linear Size Circuits in Terms of Privacy Eyal Kushilevitz, Technion, Rafail Ostrovsky, Bellcore, Adi Rosen, Tel-Aviv 11:25am Nondeterministic communication with a limited number of advice bits Juraj Hromkovic, Universit\`{a}t zu Kiel, Georg Schnitger, Johann Wolfgang Goethe-Universit\`{a}t 11:50am Public vs. Private Coin Flips in One Round Communication Games Ilan Newman, Haifa Mario Szegedy, AT/&T Bell Labs Lunch: 12:10pm - 2:00pm Session 11A: Friday, May 24, 1996 2:00pm - 3:35pm Session Chair: Alan Frieze (CMU) 2:00pm Efficiently four-coloring planar graphs Neil Robertson, Daniel P. Sanders, Ohio State Paul Seymour, Bellcore Robin Thomas, Georgia Tech 2:25pm The Angle-TSP Problem and the Weighted Linear Matroid Parity Problem A. Aggarwal, D. Coppersmith, T.J. Watson, S. Khanna, R. Motwani, Stanford B. Schieber, T.J. Watson 2:50pm Faster Isomorphism Testing of Strongly Regular Graphs Daniel A. Spielman, UC Berkeley 3:15pm Node-Disjoint Paths on the Mesh and a New Trade-off in VLSI Layout Alok Aggarwal, IBM Research Jon M. Kleinberg, MIT David P. Williamson, IBM Research Session 11B: Friday, May 24, 1996 2:00pm - 3:35pm Session Chair: Alistair Sinclair (Berkeley) 2:00pm Modular 2 Counting Formulas Are Hard for Cutting Planes Proofs Xudong Fu, Toronto 2:25pm Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs Laszlo Babai, Univ. of Chicago, Anna Gal, Institute for Advanced Study, Janos Kollar, Univ. of Utah, Lajos Ronyai, Hungarian Academy Tibor Szabo, Ohio State Avi Wigderson, Hebrew 2:50pm A Lower Bound for Randomized Algebraic Decision Trees Dima Grigoriev, Penn State Marek Karpinski, Bonn Friedhelm Meyer auf der Heide, Paderborn Roman Smolensky, Bonn 3:15pm Lower Bounds for Noisy Boolean Decision Trees William Evans, Nicholas Pippenger, UBC Coffee break: 3:35pm - 4:05pm Session 12A: Friday, May 24, 1996 4:05pm - 5:40pm Session Chair: Sanjeev Arora (Princeton) 4:05pm Adaptive Zero Knowledge and Computational Equivocation Donald Beaver, Transarc Corp. 4:30pm Adaptively Secure Multiparty Computation Ran Canetti, MIT, Uri Feige, Oded Goldreich, Moni Naor, Weizmann 4:55pm On Relationships between Statistical Zero-Knowledge Proofs Tatsuaki Okamoto, NTT Labs.