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