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 updated on Sat May 25 04:59:31 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page