32. FOCS 1991:
San Juan,
Puerto Rico
32nd Annual Symposium on Foundations of Computer Science,
San Juan, Puerto Rico, 1-4 October 1991. IEEE Computer Society
- Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:
Approximating Clique is Almost NP-Complete (Preliminary Version).
2-12 BibTeX
- Dror Lapidot, Adi Shamir:
Fully Parallelized Multi Prover Protocols for NEXP-Time (Extended Abstract).
13-18 BibTeX
- Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser:
Languages that Are Easier than their Proofs.
19-28 BibTeX
- Bernard Chazelle:
An Optimal Convex Hull Algorithm and New Results on Cuttings (Extended Abstract).
29-38 BibTeX
- Frank Hoffmann, Michael Kaufmann, Klaus Kriegel:
The Art Gallery Theorem for Polygons With Holes.
39-48 BibTeX
- Jirí Matousek, Nathaly Miller, János Pach, Micha Sharir, Shmuel Sifrony, Emo Welzl:
Fat Triangles Determine Linearly Many Holes.
49-58 BibTeX
- Oded Goldreich, Erez Petrank:
Quantifying Knowledge Complexity.
59-68 BibTeX
- Joan Boyar, Gilles Brassard, René Peralta:
Subquadratic Zero-Knowledge.
69-78 BibTeX
- David Zuckerman:
Simulating BPP Using a General Weak Random Source.
79-89 BibTeX
- Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, Moni Naor:
Checking the Correctness of Memories.
90-99 BibTeX
- Sanjoy K. Baruah, Gilad Koren, Bhubaneswar Mishra, Arvind Raghunathan, Louis E. Rosier, Dennis Shasha:
On-line Scheduling in the Presence of Overload.
100-110 BibTeX
- Anja Feldmann, Jiri Sgall, Shang-Hua Teng:
Dynamic Scheduling on Parallel Machines.
111-120 BibTeX
- Jeffrey Scott Vitter, P. Krishnan:
Optimal Prefetching via Data Compression (Extended Abstract).
121-130 BibTeX
- David B. Shmoys, Joel Wein, David P. Williamson:
Scheduling Parallel Machines On-Line.
131-140 BibTeX
- Manfred Kunde:
Concentrated Regular Data Streams on Grids: Sorting and Routing Near to the Bisection Bound.
141-150 BibTeX
- I-Chen Wu, H. T. Kung:
Communication Complexity for Parallel Divide-and-Conquer.
151-162 BibTeX
- Christos H. Papadimitriou:
On Selecting a Satisfying Truth Assignment (Extended Abstract).
163-169 BibTeX
- Howard Aizenstein, Leonard Pitt:
Exact Learning of Read-Twice DNF Formulas (Extended Abstract).
170-179 BibTeX
- Otfried Schwarzkopf:
Dynamic Maintenance of Geometric Structures Made Easy.
197-206 BibTeX
- Jirí Matousek:
Reporting Points in Halfspaces.
207-215 BibTeX
- Alon Orlitsky:
Interactive Communication: Balanced Distributions, Correlated Files, and Average-Case Complexity.
228-238 BibTeX
- Tomás Feder, Eyal Kushilevitz, Moni Naor:
Amortized Communication Complexity (Preliminary Version).
239-248 BibTeX
- Jeff Edmonds, Steven Rudich, Russell Impagliazzo, Jiri Sgall:
Communication Complexity Towards Lower Bounds on Circuit Depth.
249-257 BibTeX
- Baruch Awerbuch, George Varghese:
Distributed Program Checking: a Paradigm for Building Self-stabilizing Distributed Protocols (Extended Abstract).
258-267 BibTeX
- Baruch Awerbuch, Boaz Patt-Shamir, George Varghese:
Self-Stabilization By Local Checking and Correction (Extended Abstract).
268-277 BibTeX
- Weiguo Wang:
An Asynchronous Two-Dimensional Self-Correcting Cellular Automaton.
278-285 BibTeX
- Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, Sundar Vishwanathan:
Competitive Algorithms for Layered Graph Traversal.
288-297 BibTeX
- Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou:
How to Learn an Unknown Environment (Extended Abstract).
298-303 BibTeX
- Rolf Klein:
Walking an Unknown Street with Bounded Detour.
304-313 BibTeX
- Jaikumar Radhakrishnan:
Better Bounds for Threshold Formulas.
314-323 BibTeX
- Mike Paterson, Uri Zwick:
Shrinkage of de~Morgan formulae under restriction.
324-333 BibTeX
- Nader H. Bshouty, Richard Cleve, Wayne Eberly:
Size-Depth Tradeoffs for Algebraic Formulae.
334-341 BibTeX
- Bruce M. Kapron, Stephen A. Cook:
A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract).
342-347 BibTeX
- Rakesh M. Verma:
A Theory of Using History for Equational Systems with Applications (Extended Abstract).
348-357 BibTeX
- Nils Klarlund:
Progress Measures for Complementation of omega-Automata with Applications to Temporal Logic.
358-367 BibTeX
- E. Allen Emerson, Charanjit S. Jutla:
Tree Automata, Mu-Calculus and Determinacy (Extended Abstract).
368-377 BibTeX
- Victor Shoup, Roman Smolensky:
Lower Bounds for Polynomial Evaluation and Interpolation Problems.
378-383 BibTeX
- Joachim von zur Gathen:
Efficient Exponentiation in Finite Fields (Extended Abstract).
384-391 BibTeX
- Moshe Morgenstern:
Explicit Construction of Natural Bounded Concentrators.
392-397 BibTeX
- Nabil Kahale:
Better Expansion for Ramanujan Graphs.
398-404 BibTeX
- Ioannis Z. Emiris, John F. Canny:
A General Approach to Removing Degeneracies.
405-413 BibTeX
- Herbert Edelsbrunner, Tiow Seng Tan:
A Quadratic Time Algorithm for The MinMax Length Triangulation (Extended Abstract).
414-423 BibTeX
- Jirí Matousek, Emo Welzl, Lorenz Wernisch:
Discrepancy and epsilon-approximations for bounded VC-dimension.
424-430 BibTeX
- Ding-Zhu Du, Yanjun Zhang, Qing Feng:
On Better Heuristic for Euclidean Steiner Minimum Trees (Extended Abstract).
431-439 BibTeX
- Yonatan Aumann, Michael Ben-Or:
Asymptotically Optimal PRAM Emulation on Faulty Hypercubes (Extended Abstract).
440-446 BibTeX
- Oded Goldreich, Shafi Goldwasser, Nathan Linial:
Fault-tolerant Computation in the Full Information Model (Extended Abstract).
447-457 BibTeX
- Frank Thomson Leighton, Yuan Ma, C. Greg Plaxton:
Highly Fault-Tolerant Sorting Circuits.
458-469 BibTeX
- Frank Thomson Leighton, Eric J. Schwabe:
Efficient Algorithms for Dynamic Allocation of Distributed Memory.
470-479 BibTeX
- Ilan Adler, Peter A. Beling:
Polynomial Algorithms for LP over a Subring of the Algebraic Integers with Applications to LP with Circulant Matrices.
480-487 BibTeX
- David Eppstein:
Dynamic Three-Dimensional Linear Programming.
488-494 BibTeX
- Serge A. Plotkin, David B. Shmoys, Éva Tardos:
Fast Approximation Algorithms for Fractional Packing and Covering Problems.
495-504 BibTeX
- Baruch Awerbuch, Leonard J. Schulman:
The Maintenance of Common Data in a Distributed System.
505-514 BibTeX
- Moni Naor, Ron M. Roth:
Optimal File Sharing in Distributed Networks (Preliminary Version).
515-525 BibTeX
- Maurice Herlihy, Nir Shavit, Orli Waarts:
Low Contention Linearizable Counting.
526-535 BibTeX
- Gary L. Miller, Shang-Hua Teng, Stephen A. Vavasis:
A Unified Geometric Approach to Graph Separators.
538-547 BibTeX
- Tsan-sheng Hsu, Vijaya Ramachandran:
A Linear Time Algorithm for Triconnectivity Augmentation (Extended Abstract).
548-559 BibTeX
- David R. Karger, Daphne Koller, Steven J. Phillips:
Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths.
560-568 BibTeX
- Noga Alon, Zvi Galil, Oded Margalit:
On the Exponent of the All Pairs Shortest Path Problem.
569-575 BibTeX
- László Lovász, Moni Naor, Ilan Newman, Avi Wigderson:
Search Problems in the Decision Tree Model (Preliminary Version).
576-585 BibTeX
- Noga Alon:
A parallel algorithmic version of the Local Lemma.
586-593 BibTeX
- Anna Gál:
Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates.
594-601 BibTeX
- Rüdiger Reischuk, Bernd Schmeltz:
Reliable Computation with Noisy Circuits and Decision Trees-A General n log n Lower Bound.
602-611 BibTeX
- Rajamani Sundar:
A Lower Bound for the Dictionary Problem under a Hashing Model.
612-621 BibTeX
- Amir M. Ben-Amram, Zvi Galil:
Lower Bounds for Data Structure Problems on RAMs (Extended Abstract).
622-631 BibTeX
- Greg N. Frederickson:
Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees.
632-641 BibTeX
- Arne Andersson, Thomas Ottmann:
Faster Uniquely Represented Dictionaries.
642-649 BibTeX
- Bruce Randall Donald, Davied Renpan Chang:
On the Complexity of Computing the Homology Type of a Triangulation.
650-661 BibTeX
- Dima Grigoriev, Marek Karpinski:
An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q].
662-669 BibTeX
- Johannes Blömer:
Computing Sums of Radicals in Polynomial Time.
670-677 BibTeX
- Ming-Deh A. Huang, Doug Ierardi:
Efficient Algorithms for the Riemann-Roch Problem and for Addition in the Jacobian of a Curve (Extended Abstract).
678-687 BibTeX
- Donald B. Johnson, Panagiotis Takis Metaxas:
Connected Components in O(\lg^3/2 |V|) Parallel Time for the CREW PRAM.
688-697 BibTeX
- Joseph Gil, Yossi Matias, Uzi Vishkin:
Towards a Theory of Nearly Constant Time Parallel Algorithms.
698-710 BibTeX
- Michael T. Goodrich:
Using Approximation Algorithms to Design Parallel Algorithms that May Ignore Processor Allocation (Preliminary Version).
711-722 BibTeX
- Hillel Gazit:
A Deterministic Parallel Algorithm for Planar Graphs Isomorphism.
723-732 BibTeX
- László Babai, Katalin Friedl:
Approximate Representation Theory of Finite Groups.
733-742 BibTeX
- Huzur Saran, Vijay V. Vazirani:
Finding k-cuts within Twice the Optimal.
743-751 BibTeX
- Peter W. Shor:
How to Pack Better than Best Fit: Tight Bounds for Average-Case On-Line Bin Packing.
752-759 BibTeX
- Amihood Amir, Martin Farach:
Adaptive Dictionary Matching.
760-766 BibTeX
- Wolfgang Maass, Georg Schnitger, Eduardo D. Sontag:
On the Computational Power of Sigmoid versus Boolean Threshold Circuits.
767-776 BibTeX
- Matthias Krause, Stephan Waack:
Variation Ranks of Communication Matrices and Lower Bounds for Depth Two Circuits Having Symmetric Gates with Unbounded Fan-In.
777-782 BibTeX
- Richard Beigel, Jun Tarui:
On ACC.
783-792 BibTeX
- Arkady Kanevsky, Roberto Tamassia, Giuseppe Di Battista, Jianer Chen:
On-Line Maintenance of the Four-Connected Components of a Graph (Extended Abstract).
793-801 BibTeX
- Arvind Gupta, Russell Impagliazzo:
Computing Planar Intertwines.
802-811 BibTeX
- Harold N. Gabow:
Applications of a Poset Representation to Edge Connectivity and Graph Rigidity.
812-821 BibTeX
Copyright © Sat May 16 23:12:26 2009
by Michael Ley (ley@uni-trier.de)