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 BibTeX
- Christos H. Papadimitriou:
On the Complexity of Unique Solutions.
14-20 BibTeX
- Thiet-Dung Huynh:
Deciding the Inequivalence of Context-Free Grammars with 1-Letter Terminal Alphabet is Sigma_2^P-Complete.
21-31 BibTeX
- J. C. Lagarias:
The Computational Complexity of Simultaneous Diophantine Approximation Problems.
32-39 BibTeX
- Umesh V. Vazirani, Vijay V. Vazirani:
A Natural Encoding Scheme Proved Probabilistic Polynomial Complete.
40-44 BibTeX
- Stefan Reisch, Georg Schnitger:
Three Applications of Kolmogorov-Complexity.
45-52 BibTeX
- Wolfgang J. Paul:
On-Line Simulation of k+1 Tapes by k Tapes Requires Nonlinear Time.
53-56 BibTeX
- Erich Kaltofen:
A Polynomial-Time Reduction from Bivariate to Univariate Integral Polynomial Factorization.
57-64 BibTeX
- Allan Borodin, Joachim von zur Gathen, John E. Hopcroft:
Fast Parallel Matrix and GCD Computations.
65-71 BibTeX
- Carl Sturtivant:
Generalised Symmetries of Polynomials in Algebraic Complexity.
72-79 BibTeX
- Benny Chor, Charles E. Leiserson, Ronald L. Rivest:
An Application of Number Theory to the Organization of Raster-Graphics Memory (Extended Abstract).
92-99 BibTeX
- Leonard M. Adleman, Robert McDonnell:
An Application of Higher Reciprocity to Computational Number Theory (Abstract).
100-106 BibTeX
- Narendra Karmarkar:
Probabilistic Analysis of Some Bin-Packing Problems.
107-111 BibTeX
- Manuel Blum, Silvio Micali:
How to Generate Cryptographically Strong Sequences of Pseudo Random Bits.
112-117 BibTeX
- 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 BibTeX
- Mark Jerrum:
A Compact Representation for Permutation Groups.
126-133 BibTeX
- Shafi Goldwasser, Silvio Micali, Po Tong:
Why and How to Establish a Private Code on a Public Network (Extended Abstract).
134-144 BibTeX
- Adi Shamir:
A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem.
145-152 BibTeX
- Joan B. Plumstead:
Inferring a Sequence Generated by a Linear Congruence.
153-159 BibTeX
- Michael L. Fredman, János Komlós, Endre Szemerédi:
Storing a Sparse Table with O(1) Worst Case Access Time.
165-169 BibTeX
- Kurt Mehlhorn:
On the Program Size of Perfect and Universal Hash Functions.
170-175 BibTeX
- Moshe Y. Vardi:
On Decomposition of Relational Databases.
176-185 BibTeX
- Colm Ó'Dúnlaing, Chee-Keng Yap:
Generic Transformation of Data Structures.
186-195 BibTeX
- Danny Dolev, Rüdiger Reischuk, H. Raymond Strong:
`Eventual' Is Earlier than `Immediate'.
196-203 BibTeX
- Joseph Y. Halpern:
Deterministic Process Logic Is Elementary.
204-216 BibTeX
- Jean-Pierre Queille, Joseph Sifakis:
A Temporal Logic to Deal with Fairness in Transition Systems.
217-225 BibTeX
- Kazuo Iwama:
On Equations Including String Variables.
226-235 BibTeX
- Joffroy Beauquier, Michel Latteux:
Substitution of Bounded Rational Cone.
236-243 BibTeX
- Donald B. Johnson, Shankar M. Venkatesan:
Parallel Algorithms for Minimum Cuts and Maximum Flows in Planar Networks (Preliminary Version).
244-254 BibTeX
- 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 BibTeX
- 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 BibTeX
- Quentin F. Stout:
Using Clerks in Parallel Processing.
272-279 BibTeX
- John E. Hopcroft, Deborah Joseph, Sue Whitesides:
On the Movement of Robot Arms in 2-Dimensional Bounded Regions.
280-289 BibTeX
- John H. Reif:
Parallel Time O(log N) Acceptance of Deterministic CFLs.
290-296 BibTeX
- Frank Thomson Leighton, Charles E. Leiserson:
Wafer-Scale Integration of Systolic Arrays (Extended Abstract).
297-311 BibTeX
- Narendra Karmarkar, Richard M. Karp:
An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem.
312-320 BibTeX
- Silvio Ursic:
The Ellipsoid Algorithm for Linear Inequalities in Exact Arithmetic.
321-326 BibTeX
- Boris Yamnitsky, Leonid A. Levin:
An Old Linear Programming Algorithm Runs in Polynomial Time.
327-328 BibTeX
- Nimrod Megiddo:
Linear-Time Algorithms for Linear Programming in R^3 and Related Problems.
329-338 BibTeX
- Bernard Chazelle:
A Theorem on Polygon Cutting with Applications.
339-349 BibTeX
- Franco P. Preparata, Witold Lipski Jr.:
Three Layers Are Enough.
350-357 BibTeX
- Thomas Lengauer:
The Complexity of Compacting Hierarchically Specified Layouts of Integrated Circuits (Preliminary Version).
358-368 BibTeX
- Vijaya Ramachandran:
On Driving Many Long Lines in a VLSI Layout.
369-378 BibTeX
- Zvi M. Kedem:
Optimal Allocation of Computational Resources in VLSI.
379-385 BibTeX
Copyright © Wed Jun 4 18:35:53 2008
by Michael Ley (ley@uni-trier.de)
