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