default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID24th FOCS 1983: Tucson, Arizona, USA
- 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983. IEEE Computer Society 1983, ISBN 0-8186-0508-1
Session 1
- 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
Session 2
- 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 - Joachim von zur Gathen:
Representations of Rational Functions. 133-137 - 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 - Joachim von zur Gathen:
Factoring Sparse Multivariate Polynomials. 172-179
Session 3
- 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 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
Session 4
- 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
Session 5
- Piotr Berman, Janos Simon:
Lower Bounds on Graph Threading by Probabilistic Machines (Preliminary Version). 304-311 - Joseph F. 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
Session 6
- 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
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-09 00:11 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:
