Posted to comp.theory February 5, 1996:
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.