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