default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID23rd FOCS 1982: Chicago, Illinois, USA
- 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982. IEEE Computer Society 1982
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 L. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-21 00:02 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
