24. FOCS 1983:
Tucson,
Arizona
24th Annual Symposium on Foundations of Computer Science,
Tucson, Arizona, 7-9 November 1983. IEEE Computer Society
- J. C. Lagarias, Andrew M. Odlyzko:
Solving Low-Density Subset Sum Problems.
1-10
- Michael Luby, Silvio Micali, Charles Rackoff:
How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin.
11-21
- Umesh V. Vazirani, Vijay V. Vazirani:
Trapdoor Pseudo-random Number Generators, with Applications to Protocol Design.
23-30
- Jeff Kahn, Michael E. Saks, Dean Sturtevant:
A Topological Approach to Evasiveness.
31-33
- Shimon Even, Oded Goldreich:
On the Security of Multi-Party Ping-Pong Protocols.
34-39
- Harry G. Mairson:
The Program Complexity of Searching a Table.
40-47
- Janet Incerpi, Robert Sedgewick:
Improved Upper Bounds on Shellsort.
48-55
- Richard M. Karp, Michael Luby:
Monte-Carlo Algorithms for Enumeration and Reliability Problems.
56-64
- Jeffrey Scott Vitter:
Optimum Algorithms for Two Random Sampling Problems (Extended Abstract).
65-75
- Philippe Flajolet, G. Nigel Martin:
Probabilistic Counting.
76-82
- Herbert Edelsbrunner, Joseph O'Rourke, Raimund Seidel:
Constructing Arrangements of Lines and Hyperplanes with Applications.
83-91
- Mikhail J. Atallah:
Dynamic Computational Geometry (Preliminary Version).
92-99
- Leonidas J. Guibas, Lyle Ramshaw, Jorge Stolfi:
A Kinetic Framework for Computational Geometry.
100-111
- Richard Cole, Chee-Keng Yap:
Geometric Retrieval Problems.
112-121
- Bernard Chazelle:
Filtering Search: A New Approach to Query-Answering.
122-132
- John H. Reif:
Logarithmic Depth Circuits for Algebraic Functions.
138-145
- Uzi Vishkin, Avi Wigderson:
Trade-Offs between Depth and Width in Parallel Computation (Preliminary Version).
146-153
- Pierre McKenzie, Stephen A. Cook:
The Parallel Complexity of the Abelian Permutation Group Membership Problem.
154-161
- László Babai, William M. Kantor, Eugene M. Luks:
Computational Complexity and the Classification of Finite Simple Groups.
162-171
- Jerzy Tiuryn, Pawel Urzyczyn:
Some Relationships between Logics of Programs and Complexity Theory (Extended Abstract).
180-184
- Pierre Wolper, Moshe Y. Vardi, A. Prasad Sistla:
Reasoning about Infinite Computation Paths (Extended Abstract).
185-194
- Rohit Parikh:
Propositional Game Logic.
195-200
- Sarit Kraus, Daniel J. Lehmann:
Decision Procedures for Time and Chance (Extended Abstract).
202-209
- Yuri Gurevich:
Algebras of Feasible Functions.
210-214
- Joffroy Beauquier, Françoise Gire:
On Context-Free Generators.
215
- Bernard Chazelle, Leonidas J. Guibas, D. T. Lee:
The Power of Geometric Duality.
217-225
- Kenneth L. Clarkson:
Fast Algorithms for the All Nearest Neighbors Problem.
226-232
- Tetsuo Asano, Takao Asano:
Minimum Partition of Polygonal Regions into Trapezoids.
233-241
- Greg N. Frederickson:
Shortest Path Problems in Planar Graphs (Preliminary Version).
242-247
- Harold N. Gabow:
Scaling Algorithms for Network Problems.
248-257
- Donald B. Johnson, Shankar M. Venkatesan:
Partition of Planar Flow Networks (Preliminary Version).
259-263
- Brenda S. Baker:
Approximation Algorithms for NP-Complete Problems on Planar Graphs (Preliminary Version).
265-273
- Mihalis Yannakakis:
A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees (Extended Abstract).
274-281
- Philippe Flajolet, Claude Puech:
Tree Structures for Partial Match Retrieval.
282-288
- George S. Lueker:
Bin Packing with Items Uniformly Distributed over Intervals [a,b].
289-297
- Miklós Ajtai, Michael L. Fredman, János Komlós:
Hash Functions for Priority Queues.
299-303
- Piotr Berman, Janos Simon:
Lower Bounds on Graph Threading by Probabilistic Machines (Preliminary Version).
304-311
- Joseph JáJá:
On the Computational Complexity of the Permanent (Extended Abstract).
312-319
- Helmut Alt:
Multiplication Is the Easiest Nontrivial Arithmetic Function.
320-322
- Georg Schnitger:
On Depth-Reduction and Grates.
323-328
- Christopher B. Wilson:
Relativized Circuit Complexity.
329-334
- Robert E. Wilber:
Randomness and the Density of Hard Problems.
335-342
- Ramamohan Paturi, Janos Simon:
Lower Bounds on the Time of Probabilistic On-Line Simulations (Preliminary Version).
343-350
- Peter H. Hochschild, Ernst W. Mayr, Alan R. Siegel:
Techniques for Solving Graph Problems in Parallel Environments.
351-359
- Brenda S. Baker, Ron Y. Pinter:
An Algorithm for the Optimal Placement and Routing of a Circuit within a Ring of Pads (Extended Abstract).
360-370
- Alok Aggarwal:
Period-Time Tradeoffs for VLSI Models with Delay (Preliminary Version).
372-382
- Albert G. Greenberg, Richard E. Ladner:
Estimating the Multiplicities of Conflicts in Multiple Access Channels (Preliminary Report).
383-392
- Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer:
On the Minimal Synchronism Needed for Distributed Consensus.
393-402
- Michael O. Rabin:
Randomized Byzantine Generals.
403-409
- Maria M. Klawe:
A Tight Bound for Black and White Pebbles on the Pyramid.
410-419
- Andrew Chi-Chih Yao:
Lower Bounds by Probabilistic Arguments (Extended Abstract).
420-428
- Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter:
On Determinism versus Non-Determinism and Related Problems (Preliminary Version).
429-438
- Juris Hartmanis:
Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report).
439-445
- Christos H. Papadimitriou:
Games Against Nature (Extended Abstract).
446-450
- Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani:
Global Wire Routing in Two-Dimensional Arrays (Extended Abstract).
453-459
- Daniel Leivant:
Reasoning about Functional Programs and Complexity Classes Associated with Type Disciplines.
460-469
- Nathan Linial:
Legal Coloring of Graphs.
470-472
- Nathan Linial, Michael E. Saks:
Information Bounds Are Good for Search Problems on Ordered Data Structures.
473-475
Copyright © Fri Mar 12 17:11:24 2010
by Michael Ley (ley@uni-trier.de)
