24. FOCS 1983: Tucson, Arizona, USA

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 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, (Abstract only)
  
• 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 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
  

Last update Fri May 25 08:14:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page