24. STOC 1992: Victoria, British Columbia, Canada

• Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, Steven Phillips:
  Biased Random Walks. 1-9
  
• Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic:
  Approximations of General Independent Distributions. 10-16
  
• Leonard J. Schulman:
  Sample Spaces Uniform on Neighborhoods. 17-25
  
• Tomás Feder, Milena Mihail:
  Balanced Matroids. 26-38
  
• Yair Bartal, Amos Fiat, Yuval Rabani:
  Competitive Algorithms for Distributed Data Management (Extended Abstract). 39-50
  
• Yair Bartal, Amos Fiat, Howard J. Karloff, Rakesh Vohra:
  New Algorithms for an Ancient Scheduling Problem. 51-58
  
• Amihood Amir, Gary Benson, Martin Farach:
  Alphabet Independent Two Dimensional Matching. 59-68
  
• Zvi Galil:
  A Constant-Time Optimal Parallel String-Matching Algorithm. 69-76
  
• Frank Thomson Leighton:
  Methods for Message Routing in Parallel Machines. 77-96
  
• Joachim von zur Gathen, Victor Shoup:
  Computing Frobenius Maps and Factoring Polynomials (Extended Abstract). 97-105
  
• Jin-yi Cai:
  Parallel Computation Over Hyperbolic Groups. 106-115
  
• Robert Beals, Ákos Seress:
  Structure Forest and Composition Factors for Small Base Groups in Nearly Linear Time. 116-125
  
• Alexander I. Barvinok:
  Feasibility Testing for Systems of Real Quadratic Equations. 126-132
  
• Geng Lin:
  Fault Tolerant Planar Communication Networks. 133-139
  
• Andrei Z. Broder, Alan M. Frieze, Eli Upfal:
  Existence and Construction of Edge Disjoint Paths on Expander Graphs. 140-149
  
• Bruce M. Maggs, Ramesh K. Sitaraman:
  Simple Algorithms for Routing on Butterfly Networks with Bounded Queues (Extended Abstract). 150-161
  
• Yonatan Aumann, Michael Ben-Or:
  Computing with Faulty Arrays. 162-169
  
• Anders Björner, László Lovász, Andrew Chi-Chih Yao:
  Linear Decision Trees: Volume Estimates and Topological Bounds. 170-177
  
• Jeff Kahn, Jeong Han Kim:
  Entropy and Sorting. 178-187
  
• Paul Beame, Joan Lawry:
  Randomized versus Nondeterministic Communication Complexity. 188-199
  
• Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák, Alan R. Woods:
  Exponential Lower Bounds for the Pigeonhole Principle. 200-220
  
• Bruce A. Reed:
  Finding Approximate Separators and Computing Tree Width Quickly. 221-228
  
• Satish Rao:
  Faster Algorithms for Finding Small Edge Cuts in Planar Graphs (Extended Abstract). 229-240
  
• Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis:
  The Complexity of Multiway Cuts (Extended Abstract). 241-251
  
• Dorit Dor, Michael Tarsi:
  Graph Decomposition Is NPC-A Complete Proof of Holyer's Conjecture. 252-263
  
• David Lee, Mihalis Yannakakis:
  Online Minimization of Transition Systems (Extended Abstract). 264-274
  
• Shmuel Safra:
  Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (Extended Abstract). 275-282
  
• Stephen Bellantoni, Stephen A. Cook:
  A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract). 283-293
  
• Adam J. Grove, Joseph Y. Halpern, Daphne Koller:
  Asymptotic Conditional Probabilities for First-Order Logic. 294-305
  
• Zvi M. Kedem, Krishna V. Palem, Michael O. Rabin, A. Raghunathan:
  Efficient Program Transformations for Resilient Parallel Computation via Randomization (Preliminary Version). 306-317
  
• Richard M. Karp, Michael Luby, Friedhelm Meyer auf der Heide:
  Efficient PRAM Simulation on a Distributed Memory Machine. 318-326
  
• Miklós Ajtai, Nimrod Megiddo:
  A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension. 327-338
  
• Pierre Kelsen:
  On the Parallel Complexity of Computing a Maximal Independent Set in a Hypergraph. 339-350
  
• Dana Angluin:
  Computational Learning Theory: Survey and Selected Bibliography. 351-369
  
• Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein:
  Learning Arithmetic Read-Once Formulas. 370-381
  
• Avrim Blum, Steven Rudich:
  Fast Learning of k-Term DNF Formulas with Queries. 382-389
  
• Shai Ben-David:
  Can Finite Samples Detect Singularities of Real-Valued Functions? 390-399
  
• Steven Lindell:
  A Logspace Algorithm for Tree Canonization (Extended Abstract). 400-404
  
• C. Greg Plaxton:
  A Hypercubic Sorting Network with Nearly Logarithmic Depth. 405-416
  
• Michael Klugerman, C. Greg Plaxton:
  Small-Depth Counting Networks. 417-428
  
• Mike Paterson, Uri Zwick:
  Shallow Multiplication Circuits and Wise Financial Investments. 429-437
  
• László Babai, Robert Beals, Pál Takácsi-Nagy:
  Symmetry and Complexity. 438-449
  
• Richard Beigel:
  When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One. 450-454
  
• David A. Mix Barrington, Richard Beigel, Steven Rudich:
  Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract). 455-461
  
• Noam Nisan, Mario Szegedy:
  On the Degree of Boolean Functions as Real Polynomials. 462-467
  
• Ramamohan Paturi:
  On the Degree of Polynomials that Approximate Symmetric Boolean Functions (Preliminary Version). 468-474
  
• Gil Kalai:
  A Subexponential Randomized Simplex Algorithm (Extended Abstract). 475-482
  
• Ilan Adler, Peter A. Beling:
  Polynomial Algorithms for Linear Programming over the Algebraic Numbers. 483-494
  
• Zvi Galil, Giuseppe F. Italiano, Neil Sarnak:
  Fully Dynamic Planarity Testing (Extended Abstract). 495-506
  
• Michael T. Goodrich:
  Planar Separators and Parallel Polygon Triangulation (Preliminary Version). 507-516
  
• Pankaj K. Agarwal, Jirí Matousek:
  Ray Shooting and Parametric Search. 517-526
  
• Seth M. Malitz, Achilleas Papakostas:
  On the Angular Resolution of Planar Graphs. 527-538
  
• Chi-Yuan Lo, Jirí Matousek, William L. Steiger:
  Ham-Sandwich Cuts in R^d. 539-545
  
• Paul B. Callahan, S. Rao Kosaraju:
  A Decomposition of Multi-Dimensional Point-Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields (Preliminary Version). 546-556
  
• Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Michael E. Saks:
  Adapting to Asynchronous Dynamic Networks (Extended Abstract). 557-570
  
• Baruch Awerbuch, Shay Kutten, David Peleg:
  Competitive Distributed Job Scheduling (Extended Abstract). 571-580
  
• Alessandro Panconesi, Aravind Srinivasan:
  Improved Distributed Algorithms for Coloring and Network Decomposition Problems. 581-592
  
• Manhoi Choy, Ambuj K. Singh:
  Efficient Fault Tolerant Algorithms for Resource Allocation in Distributed Systems. 593-602
  
• Michael Sipser:
  The History and Status of the P versus NP Question. 603-618
  
• Noam Nisan:
  RL ⊆ SC. 619-623
  
• Janos Simon, Mario Szegedy:
  On the Complexity of RAM with Various Operation Sets. 624-631
  
• Ramarathnam Venkatesan, Sivaramakrishnan Rajagopalan:
  Average Case Intractability of Matrix and Diophantine Problems (Extended Abstract). 632-642
  
• Uriel Feige, Carsten Lund:
  On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract). 643-654
  
• Cynthia Dwork, Orli Waarts:
  Simple and Efficient Bounded Concurrent Timestamping or Bounded Concurrent Timestamp Systems are Comprehensible! 655-666
  
• Alain J. Mayer, Yoram Ofek, Rafail Ostrovsky, Moti Yung:
  Self-Stabilizing Symmetry Breaking in Constant-Space (Extended Abstract). 667-678
  
• Hagit Attiya, Roy Friedman:
  A Correctness Condition for High-Performance Multiprocessors (Extended Abstract). 679-690
  
• Graham Brightwell, Teunis J. Ott, Peter Winkler:
  Target Shooting with Programmed Random Variables. 691-698
  
• Matthew K. Franklin, Moti Yung:
  Communication Complexity of Secure Computation (Extended Abstract). 699-710
  
• Mihir Bellare, Erez Petrank:
  Making Zero-Knowledge Provers Efficient. 711-722
  
• Joe Kilian:
  A Note on Efficient Zero-Knowledge Proofs and Arguments (Extended Abstract). 723-732
  
• Uriel Feige, László Lovász:
  Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract). 733-744
  
• Raimund Seidel:
  On the All-Pairs-Shortest-Path Problem. 745-749
  
• Philip N. Klein, Sairam Sairam:
  A Parallel Randomized Approximation Scheme for Shortest Paths. 750-758
  
• Samir Khuller, Uzi Vishkin:
  Biconnectivity Approximations and Graph Carvings. 759-770
  
• Jyh-Han Lin, Jeffrey Scott Vitter:
  epsilon-Approximations with Minimum Packing Constraint Violation (Extended Abstract). 771-782
  

Last update Fri May 25 08:42:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page