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