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