27. FOCS 1986:
Toronto,
Canada
27th Annual Symposium on Foundations of Computer Science,
Toronto, Canada, 27-29 October 1986. IEEE Computer Society
- Zvi Galil, Éva Tardos:
An O(n^2 (m + n log n) log n) Min-Cost Flow Algorithm.
1-9
- Prabhakar Raghavan:
Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs.
10-18
- Richard M. Karp, Michael E. Saks, Avi Wigderson:
On a Search Problem Related to Branch-and-Bound Procedures.
19-28
- Michael E. Saks, Avi Wigderson:
Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees.
29-38
- Nathan Linial, László Lovász, Avi Wigderson:
A Physical Interpretation of Graph Connectivity, and Its Algorithmic Applications.
39-48
- Volker Strassen:
The Asymptotic Spectrum of Tensors and the Exponent of Matrix Multiplication.
49-54
- Alfred V. Aho, David Lee:
Storing a Dynamic Sparse Table.
55-60
- Robert E. Wilber:
Lower Bounds for Accessing Binary Search Trees With Rotations (Preliminary Version).
61-70
- David Mutchler:
What search algorithm gives optimal average-case performance when search resources are highly limited?
71-76
- Micha Sharir, Richard Cole, Klara Kedem, Daniel Leven, Richard Pollack, Shmuel Sifrony:
Geometric Applications of Davenport-Schinzel Sequences.
77-86
- Bernard Chazelle:
Lower Bounds on the Complexity of Multidimensional Searching (Extended Abstract).
87-96
- Ady Wiernik:
Planar Realizations of Nonlinear Davenport-Schinzel Sequences by Segments.
97-106
- Jiawei Hong:
Proving by Example and Gap Theorems.
107-116
- Pravin M. Vaidya:
An optimal algorithm for the All-Nearest-Neighbors Problem.
117-122
- W. Harry Plantinga, Charles R. Dyer:
An Algorithm for Constructing the Aspect Graph.
123-131
- B. K. Natarajan:
An Algorithmic Approach to the Automated Design of Parts Orienters.
132-142
- Daniel H. Greene, F. Frances Yao:
Finite-Resolution Computational Geometry.
143-152
- Joel Friedman:
On Newton's Method for Polynomials.
153-161
- Andrew Chi-Chih Yao:
How to Generate and Exchange Secrets (Extended Abstract).
162-167
- Gilles Brassard, Claude Crépeau, Jean-Marc Robert:
Information Theoretic Reductions among Disclosure Problems.
168-173
- Oded Goldreich, Silvio Micali, Avi Wigderson:
Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract).
174-187
- Gilles Brassard, Claude Crépeau:
Non-Transitive Transfer of Confidence: A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond.
188-195
- Baruch Awerbuch, Silvio Micali:
Dynamic deadlock resolution protocols (Extended Abstract).
196-207
- Yoram Moses, Mark R. Tuttle:
Programming Simultaneous Actions Using Common Knowledge: Preliminary Version.
208-221
- Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer:
Flipping Persuasively in Constant Expected Time (Preliminary Version).
222-232
- Paul M. B. Vitányi, Baruch Awerbuch:
Atomic Shared Register Access by Asynchronous Hardware (Detailed Abstract).
233-243
- Anna R. Karlin, Mark S. Manasse, Larry Rudolph, Daniel Dominic Sleator:
Competitive Snoopy Caching.
244-254
- Yiming Ma, Sandeep Sen, Isaac D. Scherson:
The Distance Bound for Sorting on Mesh-Connected Processor Arrays Is Tight (Preliminary Report).
255-263
- Quentin F. Stout:
Meshes with Multiple Buses.
264-273
- Sandeep N. Bhatt, Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg:
Optimal Simulations of Tree Machines (Preliminary Version).
274-282
- Bernd Becker, Hans-Ulrich Simon:
How Robust Is the n-Cube? (Extended Abstract).
283-291
- Eugene M. Luks:
Parallel Algorithms for Permutation Groups and Graph Isomorphism.
292-302
- László Babai:
A Las Vegas-NC Algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues.
303-312
- Max H. Garzon, Yechezkel Zalcstein:
The Complexity of Isomorphism Testing.
313-321
- Sally Floyd, Richard M. Karp:
FFD Bin Packing for Item Sizes with Distributions on [0,1/2].
322-330
- Martin E. Dyer, Alan M. Frieze:
Fast Solution of Some Random NP-Hard Problems.
331-336
- László Babai, Peter Frankl, Janos Simon:
Complexity classes in communication complexity theory (preliminary version).
337-347
- H. Venkateswaran, Martin Tompa:
A New Pebble Game that Characterizes Parallel Complexity Classes.
348-360
- Marek Chrobak, Ming Li:
k+1 Heads Are Better than k for PDA's.
361-367
- William Aiello, Shafi Goldwasser, Johan Håstad:
On the Power of Interaction.
368-379
- Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer:
Collapsing Degrees (Extended Abstract).
380-389
- Judy Goldsmith, Deborah Joseph:
Three Results on the Polynomial Isomorphism of Complete Sets.
390-397
- Joachim von zur Gathen:
Permanent and Determinant.
398-401
- Karl R. Abrahamson:
Time-Space Tradeoffs for Branching Programs Contrasted with those for Straight-Line Programs.
402-409
- Noga Alon, Wolfgang Maass:
Meanders, Ramsey Theory and Lower Bounds for Branching Programs.
410-417
- David Peleg, Eli Upfal:
The Token Distribution Problem (Preliminary Version).
418-427
- Greg N. Frederickson, Ravi Janardan:
Separator-Based Strategies for Efficient Message Routing (Preliminary Version).
428-437
- Jeffrey D. Ullman, Allen Van Gelder:
Parallel Complexity of Logical Query Programs.
438-454
- Jik H. Chang, Oscar H. Ibarra, Anastasios Vergis:
On the Power of One-Way Communication.
455-464
- Philip N. Klein, John H. Reif:
An Efficient Parallel Algorithm for Planarity.
465-477
- Richard Cole, Uzi Vishkin:
Approximate and Exact Parallel Scheduling with Applications to List, Tree and Graph Problems.
478-491
- Hillel Gazit:
An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph.
492-501
- Noga Alon, Yossi Azar, Uzi Vishkin:
Tight Complexity Bounds for Parallel Comparison Sorting.
502-510
- Richard Cole:
Parallel Merge Sort.
511-516
Copyright © Tue Dec 1 16:15:03 2009
by Michael Ley (ley@uni-trier.de)
