23. FOCS 1982: Chicago, Illinois, USA

Session 1

• Ashok K. Chandra, Larry J. Stockmeyer, Uzi Vishkin:
  A Complexity Theory for Unbounded Fan-In Parallelism. 1-13
  
• Christos H. Papadimitriou:
  On the Complexity of Unique Solutions. 14-20
  
• Thiet-Dung Huynh:
  Deciding the Inequivalence of Context-Free Grammars with 1-Letter Terminal Alphabet is Sigma_2^P-Complete. 21-31
  
• J. C. Lagarias:
  The Computational Complexity of Simultaneous Diophantine Approximation Problems. 32-39
  
• Umesh V. Vazirani, Vijay V. Vazirani:
  A Natural Encoding Scheme Proved Probabilistic Polynomial Complete. 40-44
  
• Stefan Reisch, Georg Schnitger:
  Three Applications of Kolmogorov-Complexity. 45-52
  
• Wolfgang J. Paul:
  On-Line Simulation of k+1 Tapes by k Tapes Requires Nonlinear Time. 53-56
  

Session 2

• Erich Kaltofen:
  A Polynomial-Time Reduction from Bivariate to Univariate Integral Polynomial Factorization. 57-64
  
• Allan Borodin, Joachim von zur Gathen, John E. Hopcroft:
  Fast Parallel Matrix and GCD Computations. 65-71
  
• Carl Sturtivant:
  Generalised Symmetries of Polynomials in Algebraic Complexity. 72-79
  
• Andrew Chi-Chih Yao:
  Theory and Applications of Trapdoor Functions (Extended Abstract). 80-91
  
• Benny Chor, Charles E. Leiserson, Ronald L. Rivest:
  An Application of Number Theory to the Organization of Raster-Graphics Memory (Extended Abstract). 92-99
  
• Leonard M. Adleman, Robert McDonnell:
  An Application of Higher Reciprocity to Computational Number Theory (Abstract). 100-106
  
• Narendra Karmarkar:
  Probabilistic Analysis of Some Bin-Packing Problems. 107-111
  
• Manuel Blum, Silvio Micali:
  How to Generate Cryptographically Strong Sequences of Pseudo Random Bits. 112-117
  

Session 3

• Zvi Galil, Christoph M. Hoffmann, Eugene M. Luks, Claus-Peter Schnorr, Andreas Weber:
  An O(n^3 log n) Deterministic and an O(n^3) Probabilistic Isomorphism Test for Trivalent Graphs. 118-125
  
• Mark Jerrum:
  A Compact Representation for Permutation Groups. 126-133
  
• Shafi Goldwasser, Silvio Micali, Po Tong:
  Why and How to Establish a Private Code on a Public Network (Extended Abstract). 134-144
  
• Adi Shamir:
  A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. 145-152
  
• Joan B. Plumstead:
  Inferring a Sequence Generated by a Linear Congruence. 153-159
  
• Andrew Chi-Chih Yao:
  Protocols for Secure Computations (Extended Abstract). 160-164
  
• Michael L. Fredman, János Komlós, Endre Szemerédi:
  Storing a Sparse Table with O(1) Worst Case Access Time. 165-169
  
• Kurt Mehlhorn:
  On the Program Size of Perfect and Universal Hash Functions. 170-175
  

Session 4

• Moshe Y. Vardi:
  On Decomposition of Relational Databases. 176-185
  
• Colm Ó'Dúnlaing, Chee-Keng Yap:
  Generic Transformation of Data Structures. 186-195
  
• Danny Dolev, Rüdiger Reischuk, H. Raymond Strong:
  `Eventual' Is Earlier than `Immediate'. 196-203
  
• Joseph Y. Halpern:
  Deterministic Process Logic Is Elementary. 204-216
  
• Jean-Pierre Queille, Joseph Sifakis:
  A Temporal Logic to Deal with Fairness in Transition Systems. 217-225
  
• Kazuo Iwama:
  On Equations Including String Variables. 226-235
  
• Joffroy Beauquier, Michel Latteux:
  Substitution of Bounded Rational Cone. 236-243
  

Session 5

• Donald B. Johnson, Shankar M. Venkatesan:
  Parallel Algorithms for Minimum Cuts and Maximum Flows in Planar Networks (Preliminary Version). 244-254
  
• Zvi Galil, Silvio Micali, Harold N. Gabow:
  Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs. 255-261
  
• Moon-Jung Chung, Fillia Makedon, Ivan Hal Sudborough, Jonathan S. Turner:
  Polynomial Time Algorithms for the Min Cut Problem on Degree Restricted Trees. 262-271
  
• Quentin F. Stout:
  Using Clerks in Parallel Processing. 272-279
  
• John E. Hopcroft, Deborah Joseph, Sue Whitesides:
  On the Movement of Robot Arms in 2-Dimensional Bounded Regions. 280-289
  
• John H. Reif:
  Parallel Time O(log N) Acceptance of Deterministic CFLs. 290-296
  
• Frank Thomson Leighton, Charles E. Leiserson:
  Wafer-Scale Integration of Systolic Arrays (Extended Abstract). 297-311
  
• Narendra Karmarkar, Richard M. Karp:
  An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem. 312-320
  

Session 6

• Silvio Ursic:
  The Ellipsoid Algorithm for Linear Inequalities in Exact Arithmetic. 321-326
  
• Boris Yamnitsky, Leonid A. Levin:
  An Old Linear Programming Algorithm Runs in Polynomial Time. 327-328
  
• Nimrod Megiddo:
  Linear-Time Algorithms for Linear Programming in R^3 and Related Problems. 329-338
  
• Bernard Chazelle:
  A Theorem on Polygon Cutting with Applications. 339-349
  
• Franco P. Preparata, Witold Lipski Jr.:
  Three Layers Are Enough. 350-357
  
• Thomas Lengauer:
  The Complexity of Compacting Hierarchically Specified Layouts of Integrated Circuits (Preliminary Version). 358-368
  
• Vijaya Ramachandran:
  On Driving Many Long Lines in a VLSI Layout. 369-378
  
• Zvi M. Kedem:
  Optimal Allocation of Computational Resources in VLSI. 379-385
  

Last update Fri May 25 08:14:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page