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