23. FOCS 1982:
Chicago,
Illinois
23rd Annual Symposium on Foundations of Computer Science,
Chicago, Illinois, 3-5 November 1982. IEEE Computer Society
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
Copyright © Sat Dec 19 23:13:51 2009
by Michael Ley (ley@uni-trier.de)
