23. STOC 1991
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA. ACM 1991
- 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
Copyright © Tue Feb 9 19:37:47 2010
by Michael Ley (ley@uni-trier.de)
