23. STOC 1991: New Orleans, Louisiana, USA
Cris Koutsougeras, Jeffrey Scott Vitter (Eds.):
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA.
ACM 1991, ISBN 0-89791-397-3
- 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