23. STOC 1991: New Orleans, Louisiana, USA

• Richard Beigel, Nick Reingold, Daniel A. Spielman:
  PP Is Closed Under Intersection (Extended Abstract). 1-9
  
• Ker-I Ko:
  Integral Equations, Systems of Quadratic Equations, and Exponential-Time Completeness (Extended Abstract). 10-20
  
• László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy:
  Checking Computations in Polylogarithmic Time. 21-31
  
• Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson:
  Self-Testing/Correcting for Polynomials and for Approximate Functions. 32-42
  
• Greg Barnes, Walter L. Ruzzo:
  Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (Extended Abstract). 43-53
  
• Erich Kaltofen:
  Effective Noether Irreducibility Forms and Applications (Extended Abstract). 54-63
  
• Leonard M. Adleman:
  Factoring Numbers Using Singular Integers. 64-71
  
• Johannes Buchmann, Victor Shoup:
  Constructing Nonresidues in Finite Fields and the Extended Riemann Hypothesis. 72-79
  
• Alfred Menezes, Scott A. Vanstone, Tatsuaki Okamoto:
  Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. 80-89
  
• László Babai, Gene Cooperman, Larry Finkelstein, Eugene M. Luks, Ákos Seress:
  Fast Monte Carlo Algorithms for Permutation Groups. 90-100
  
• Frank Thomson Leighton, Fillia Makedon, Serge A. Plotkin, Clifford Stein, Éva Tardos, Spyros Tragoudas:
  Fast Approximation Algorithms for Multicommodity Flow Problems. 101-111
  
• Harold N. Gabow:
  A Matroid Approach to Finding Edge Connectivity and Packing Arborescences. 112-122
  
• Tomás Feder, Rajeev Motwani:
  Clique Partitions, Graph Compression, and Speeding-Up Algorithms. 123-133
  
• Ajit Agrawal, Philip N. Klein, R. Ravi:
  When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. 134-144
  
• Edith Cohen, Nimrod Megiddo:
  Improved Algorithms for Linear Inequalities with Two Variables per Inequality (Extended Abstract). 145-155
  
• David Applegate, Ravi Kannan:
  Sampling and Integration of Near Log-Concave functions. 156-163
  
• László Babai:
  Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups. 164-174
  
• Graham Brightwell, Peter Winkler:
  Counting Linear Extensions is \#P-Complete. 175-181
  
• Andrei Z. Broder, Alan M. Frieze, Eli Shamir:
  Finding Hidden Hamiltonian Cycles (Extended Abstract). 182-189
  
• Richard M. Karp:
  Probabilistic Recurrence Relations. 190-197
  
• Ehud Y. Shapiro:
  Separating Concurrent Languages with Categories of Language Embeddings (Extended Abstract). 198-208
  
• Serge Abiteboul, Victor Vianu:
  Generic Computation and Its Complexity. 209-219
  
• David Harel:
  Hamiltonian Paths in Infinite Graphs. 220-229
  
• Edward G. Coffman Jr., Costas Courcoubetis, M. R. Garey, David S. Johnson, Lyle A. McGeoch, Peter W. Shor, Richard R. Weber, Mihalis Yannakakis:
  Fundamental Discrepancies between Average-Case Analyses under Discrete and Continuous Distributions: A Bin Packing Case Study. 230-240
  
• Edward G. Coffman Jr., M. R. Garey:
  Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-Processor Scheduling. 241-248
  
• Allan Borodin, Sandy Irani, Prabhakar Raghavan, Baruch Schieber:
  Competitive Paging with Locality of Reference (Preliminary Version). 249-259
  
• Edward F. Grove:
  The Harmonic Online K-Server Algorithm Is Competitive. 260-266
  
• Simon Kahan:
  A Model for Data in Motion. 267-277
  
• Howard J. Karloff, Yuval Rabani, Yiftach Ravid:
  Lower Bounds for Randomized k-Server and Motion Planning Algorithms. 278-288
  
• Xiaotie Deng, Sanjeev Mahajan:
  Infinite Games, Randomization, Computability, and Applications to Online Problems (Preliminary Version). 289-298
  
• Torben Hagerup:
  Constant-Time Parallel Integer Sorting (Extended Abstract). 299-306
  
• Yossi Matias, Uzi Vishkin:
  Converting High Probability into Nearly-Constant Time-with Applications to Parallel Hashing (Extended Abstract). 307-316
  
• Zvi Galil, Giuseppe F. Italiano:
  Fully Dynamic Algorithms for Edge-Connectivity Problems (Extended Abstract). 317-327
  
• Avrim Blum, Tao Jiang, Ming Li, John Tromp, Mihalis Yannakakis:
  Linear Approximation of Shortest Superstrings. 328-336
  
• Hristo Djidjev, John H. Reif:
  An Efficient Algorithm for the Genus Problem with Explicit Construction of Forbidden Subgraphs. 337-347
  
• James Aspnes, Maurice Herlihy, Nir Shavit:
  Counting Networks and Multi-Processor Coordination. 348-358
  
• Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer:
  Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty. 359-369
  
• Richard J. Anderson, Heather Woll:
  Wait-free Parallel Algorithms for the Union-Find Problem. 370-380
  
• Zvi M. Kedem, Krishna V. Palem, A. Raghunathan, Paul G. Spirakis:
  Combining Tentative and Definite Executions for Very Fast Dependable Parallel Computing (Extended Abstract). 381-390
  
• Joseph Cheriyan, Ramakrishna Thurimella:
  Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates (Extended Abstract). 391-401
  
• James Aspnes, Richard Beigel, Merrick L. Furst, Steven Rudich:
  The Expressive Power of Voting Polynomials. 402-409
  
• Noam Nisan:
  Lower Bounds for Non-Commutative Computation (Extended Abstract). 410-418
  
• Noam Nisan, Avi Wigderson:
  Rounds in Communication Complexity Revisited. 419-429
  
• Michael Luby, Boban Velickovic:
  On Deterministic Approximation of DNF. 430-438
  
• Dany Breslauer, Zvi Galil:
  A Lower Bound for Parallel String Matching. 439-443
  
• Dana Angluin, Michael Kharitonov:
  When Won't Membership Queries Help? (Extended Abstract). 444-454
  
• Eyal Kushilevitz, Yishay Mansour:
  Learning Decision Trees Using the Fourier Sprectrum (Extended Abstract). 455-464
  
• Nick Littlestone, Philip M. Long, Manfred K. Warmuth:
  On-Line Learning of Linear Functions. 465-475
  
• Mihalis Yannakakis, David Lee:
  Testing Finite State Machines (Extended Abstract). 476-485
  
• Javed A. Aslam, Aditi Dhagat:
  Searching in the Presence of Linearly Bounded Errors (Extended Abstract). 486-493
  
• Avrim Blum, Prabhakar Raghavan, Baruch Schieber:
  Navigating in Unfamiliar Geometric Terrain (Preliminary Version). 494-504
  
• Jirí Matousek:
  Approximations and Optimal Geometric Divide-And-Conquer. 505-511
  
• Ketan Mulmuley:
  Hidden Surface Removal with Respect to a Moving View Point. 512-522
  
• Michael T. Goodrich, Roberto Tamassia:
  Dynamic Trees and Dynamic Point Location (Preliminary Version). 523-533
  
• Amos Fiat, Moni Naor:
  Rigorous Time/Space Tradeoffs for Inverting Functions. 534-541
  
• Danny Dolev, Cynthia Dwork, Moni Naor:
  Non-Malleable Cryptography (Extended Abstract). 542-552
  
• Joe Kilian:
  A General Completeness Theorem for Two-Party Games. 553-560
  
• Ueli M. Maurer:
  Perfect Cryptographic Security from Partially Independent Channels. 561-571
  

Last update Tue May 21 18:06:24 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page