Abstract is missing.
- Hardness vs. Randomness (Extended Abstract)Noam Nisan, Avi Wigderson. 2-11
- On the Existence of Pseudorandom Generators (Extended Abstract)Oded Goldreich, Hugo Krawczyk, Michael Luby. 12-24
- Zero-knowledge with Log-Space VerifiersJoe Kilian. 25-35
- Homogeneous Measures and Polynomial Time InvariantsLeonid A. Levin. 36-41
- Achieving Oblivious Transfer Using Weakened Security Assumptions (Extended Abstract)Claude Crépeau, Joe Kilian. 42-52
- Lower Bounds for Integer Greatest Common Divisor Computations (Extended Summary)Yishay Mansour, Baruch Schieber, Prasoon Tiwari. 54-63
- A Lower Bound for Matrix MultiplicationNader H. Bshouty. 64-67
- The Influence of Variables on Boolean Functions (Extended Abstract)Jeff Kahn, Gil Kalai, Nathan Linial. 68-80
- Lattices, Möbius Functions and Communication ComplexityLászló Lovász, Michael E. Saks. 81-90
- Near-Optimal Time-Space Tradeoff for Element DistinctnessAndrew Chi-Chih Yao. 91-97
- Predicting {0,1}-Functions on Randomly Drawn Points (Extended Abstract)David Haussler, Nick Littlestone, Manfred K. Warmuth. 100-109
- Learning Probabilistic Prediction Functions (Extended Abstract)Alfredo De Santis, George Markowsky, Mark N. Wegman. 110-119
- Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract)Nathan Linial, Yishay Mansour, Ronald L. Rivest. 120-129
- Learning via QueriesWilliam I. Gasarch, Carl H. Smith. 130-137
- Effect of Connectivity in Associative Memory Models (Preliminary Version)János Komlós, Ramamohan Paturi. 138-147
- Efficient Parallel Algorithms for Chordal GraphsPhilip N. Klein. 150-161
- Removing Randomness in Parallel Computation Without a Processor PenaltyMichael Luby. 162-173
- Sublinear-Time Parallel Algorithms for Matching and Related ProblemsAndrew V. Goldberg, Serge A. Plotkin, Pravin M. Vaidya. 174-185
- Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense GraphsElias Dahlhaus, Péter Hajnal, Marek Karpinski. 186-193
- Parallel Comparison Algorithms for Approximation ProblemsNoga Alon, Yossi Azar. 194-203
- Dynamic Networks Are as Fast as Static Networks (Preliminary Version)Baruch Awerbuch, Michael Sipser. 206-220
- Increasing the Size of a Network by a Constant Factor Can Increase Performance by More Than a Constant FactorRichard A. Koch. 221-230
- On the Effects of Feedback in Dynamic Network Protocols (Preliminary Version)Baruch Awerbuch. 231-245
- Coordinated Traversal: (t + 1)-Round Byzantine Agreement in Polynomial TimeYoram Moses, Orli Waarts. 246-255
- Universal Packet Routing Algorithms (Extended Abstract)Frank Thomson Leighton, Bruce M. Maggs, Satish Rao. 256-269
- Fast Management of Permutation GroupsLászló Babai, Eugene M. Luks, Ákos Seress. 272-282
- New Algorithms for Finding Irreducible Polynomials over Finite FieldsVictor Shoup. 283-290
- A Faster PSPACE Algorithm for Deciding the Existential Theory of the RealsJames Renegar. 291-295
- Computing with Polynomials Given By Black Boxes for Their Evaluation: Greatest Common Divisors, Factorization, Separation of Numerators and DenominatorsErich Kaltofen, Barry M. Trager. 296-305
- On the Complexity of Kinodynamic PlanningJohn F. Canny, Bruce Randall Donald, John H. Reif, Patrick G. Xavier. 306-316
- On the Complexity of omega-AutomataShmuel Safra. 319-327
- The Complexity of Tree Automata and Logics of Programs (Extended Abstract)E. Allen Emerson, Charanjit S. Jutla. 328-337
- Verifying Temporal Properties of Finite-State Probabilistic ProgramsCostas Courcoubetis, Mihalis Yannakakis. 338-345
- The Complexity of the Pigeonhole PrincipleMiklós Ajtai. 346-355
- Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version)Miklós Ajtai, Ronald Fagin. 358-367
- Fully Abstract Models of the Lazy Lambda CalculusC.-H. Luke Ong. 368-376
- Nonexpressibility of Fairness and SignalingDavid A. McAllester, Prakash Panangaden, Vasant Shanbhogue. 377-386
- On a Theory of Computation over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines (Extended Abstract)Lenore Blum, Mike Shub, Steve Smale. 387-397
- Constructive Results from Graph Minors: Linkless EmbeddingsRajeev Motwani, Arvind Raghunathan, Huzur Saran. 398-409
- Polytopes, Permanents and Graphs with Large FactorsPaul Dagum, Michael Luby, Milena Mihail, Umesh V. Vazirani. 412-421
- An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation AlgorithmsFrank Thomson Leighton, Satish Rao. 422-431
- Combinatorial Algorithms for the Generalized Circulation ProblemAndrew V. Goldberg, Serge A. Plotkin, Éva Tardos. 432-443
- Polynomial Algorithm for the k-Cut ProblemOlivier Goldschmidt, Dorit S. Hochbaum. 444-451
- A Las Vegas Algorithm for Linear Programming When the Dimension Is SmallKenneth L. Clarkson. 452-456
- Genus g Graphs have Pagenumber O(sqrt(g))Seth M. Malitz. 458-468
- Take a Walk, Grow a Tree (Preliminary Version)Sandeep N. Bhatt, Jin-yi Cai. 469-478
- Bounds on the Cover Time (Preliminary Version)Andrei Z. Broder, Anna R. Karlin. 479-487
- Speeding up Dynamic ProgrammingDavid Eppstein, Zvi Galil, Raffaele Giancarlo. 488-496
- Notes on Searching in Multidimensional Monotone Arrays (Preliminary Version)Alok Aggarwal, James K. Park. 497-512
- Three StacksMichael L. Fredman, Deborah L. Goldsmith. 514-523
- Dynamic Perfect Hashing: Upper and Lower BoundsMartin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, Robert Endre Tarjan. 524-531
- On Pointers versus Addresses (Extended Abstract)Amir M. Ben-Amram, Zvi Galil. 532-538
- A Deterministic View of Random Sampling and its Use in GeometryBernard Chazelle, Joel Friedman. 539-549
- New upper bounds in Klee s measure problem (extended abstract)Mark H. Overmars, Chee-Keng Yap. 550-556
- Fully Dynamic Techniques for Point Location and Transitive Closure in Planar Structures (Extended Abstract)Franco P. Preparata, Roberto Tamassia. 558-567
- Combinatorial Complexity Bounds for Arrangements of Curves and SurfacesKenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Emo Welzl. 568-579
- A Fast Planar Partition Algorithm, I (Extended Abstract)Ketan Mulmuley. 580-589
- An Optimal Algorithm for Intersecting Line Segments in the PlaneBernard Chazelle, Herbert Edelsbrunner. 590-600
- Covering Polygons Is Hard (Preliminary Abstract)Joseph C. Culberson, Robert A. Reckhow. 601-611