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