27. FOCS 1986: Toronto, Canada

• 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
  

Last update Wed May 23 00:46:55 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page