29. FOCS 1988: White Plains, New York, USA

• 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
  

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