31. FOCS 1990:
St. Louis,
Missouri
31st Annual Symposium on Foundations of Computer Science,
St. Louis, Missouri, 22-24 October 1990. IEEE Computer Society
- Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan:
Algebraic Methods for Interactive Proof Systems.
2-10
- Adi Shamir:
IP=PSPACE.
11-15
- László Babai, Lance Fortnow, Carsten Lund:
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols.
16-25
- László Babai, Lance Fortnow:
A Characterization of \sharp P Arithmetic Straight Line Programs.
26-34
- Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung:
Perfectly Secure Message Transmission.
36-45
- Noga Alon, Moni Naor:
Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract).
46-54
- Hagit Attiya, Nancy A. Lynch, Nir Shavit:
Are Wait-Free Algorithms Fast? (Extended Abstract).
55-64
- Baruch Awerbuch, Michael E. Saks:
A Dining Philosophers Algorithm with Polynomial Response Time.
65-74
- Ding-Zhu Du, Frank K. Hwang:
An Approach for Proving Lower Bounds: Solution of Gilbert-Pollak's Conjecture on Steiner Ratio.
76-85
- Michael Formann, Torben Hagerup, James Haralambides, Michael Kaufmann, Frank Thomson Leighton, Antonios Symvonis, Emo Welzl, Gerhard J. Woeginger:
Drawing Graphs in the Plane with High Resolution.
86-95
- Siu-Wing Cheng, Ravi Janardan:
New Results on Dynamic Planar Point Location.
96-105
- John H. Reif, J. D. Tygar, Akitoshi Yoshida:
The Computability and Complexity of Optical Beam Tracing.
106-114
- William I. Chang, Eugene L. Lawler:
Approximate String Matching in Sublinear Expected Time.
116-124
- Ming Li:
Towards a DNA Sequencing Theory (Learning a String) (Preliminary Version).
125-134
- Livio Colussi, Zvi Galil, Raffaele Giancarlo:
On the Exact Complexity of String Matching (Extended Abstract).
135-144
- Moshe Dubiner, Zvi Galil, Edith Magen:
Faster Tree Pattern Matching.
145-150
- C. Andrew Neff:
Specified Precision Polynomial Root Isolation is in NC.
152-162
- S. Rao Kosaraju, Arthur L. Delcher:
A Tree-Partitioning Technique with Applications to Expression Evaluation and Term Matching (Extended Abstract).
163-172
- Jens Lagergren:
Efficient Parallel Algorithms for Tree-Decomposition and Related Problems.
173-182
- Dana Angluin, Michael Frazier, Leonard Pitt:
Learning Conjunctions of Horn Clauses (Extended Abstract).
186-192
- Sally A. Goldman, Michael J. Kearns, Robert E. Schapire:
Exact Identification of Circuits Using Fixed Points of Amplification Functions (Extended Abstract).
193-202
- Wolfgang Maass, György Turán:
On the Complexity of Learning from Counterexamples and Membership Queries.
203-210
- Bernard Chazelle:
Triangulating a Simple Polygon in Linear Time.
220-230
- Marshall W. Bern, David Eppstein, John R. Gilbert:
Provably Good Mesh Generation.
231-241
- Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink:
Counting and Cutting Cycles of Lines and Rods in Space.
242-251
- Mark de Berg, Mark H. Overmars:
Hidden Surface Removal for Axis-Parallel Polyhedra (Extended Abstract).
252-261
- Frank Thomson Leighton, C. Greg Plaxton:
A (fairly) Simple Circuit that (usually) Sorts.
264-274
- Shay Assaf, Eli Upfal:
Fault Tolerant Sorting Network.
275-284
- Christos Kaklamanis, Anna R. Karlin, Frank Thomson Leighton, Victor Milenkovic, Prabhakar Raghavan, Satish Rao, Clark D. Thomborson, A. Tsantilas:
Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract).
285-296
- Paul Bay, Gianfranco Bilardi:
Deterministic On-Line Routing on Area-Universal Networks (Extended Abstract).
297-306
- Uriel Feige, Dror Lapidot, Adi Shamir:
Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract).
308-317
- Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman:
Security Preserving Amplification of Hardness.
318-326
- Carl Sturtivant, Zhi-Li Zhang:
Efficiently Inverting Bijections Given by Straight Line Programs.
327-334
- Benny Chor, Mihály Geréb-Graus, Eyal Kushilevitz:
Private Computations Over the Integers (Extended Abstract).
335-344
- László Lovász, Miklós Simonovits:
The Mixing Rate of Markov Chains, an Isoperimetric Inequality, and Computing the Volume.
346-354
- Xiaotie Deng, Christos H. Papadimitriou:
Exploring an Unknown Graph (Extended Abstract).
355-361
- Sampath Kannan, Tandy Warnow:
Inferring Evolutionary History from DNA Sequences (Extended Abstract).
362-371
- Faith E. Fich, J. Ian Munro, Patricio V. Poblete:
Permuting.
372-379
- Michael J. Kearns, Robert E. Schapire:
Efficient Distribution-free Learning of Probabilistic Concepts (Extended Abstract).
382-391
- David Aldous, Umesh V. Vazirani:
A Markovian Extension of Valiant's Learning Model (Extended Abstract).
392-396
- Ramamohan Paturi, Michael E. Saks:
On Threshold Circuits for Parity.
397-404
- Mark A. Fulk:
Robust Separations in Inductive Inference.
405-410
- Karl R. Abrahamson:
A Time-Space Tradeoff for Boolean Matrix Multiplication.
412-419
- Paul Beame, Martin Tompa, Peiyuan Yan:
Communication-Space Tradeoffs for Unrestricted Protocols.
420-428
- Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa:
Time-Space Tradeoffs for Undirected Graph Traversal.
429-438
- Sorin Istrail:
Constructing Generalized Universal Traversing Sequences of Polynomial Size for Graphs with Small Diameter (Extended Abstract).
439-448
- Amos Fiat, Yuval Rabani, Yiftach Ravid:
Competitive k-Server Algorithms (Extended Abstract).
454-463
- Sundar Vishwanathan:
Randomized Online Graph Coloring (Preliminary Version).
464-469
- Sandy Irani:
Coloring Inductive Graphs On-Line.
470-479
- Richard Cole, Arvind Raghunathan:
Online Algorithms for Finger Searching (Extended Abstract).
480-489
- Baruch Awerbuch, Israel Cidon, Shay Kutten:
Communication-Optimal Maintenance of Replicated Information.
492-502
- David Zuckerman:
General Weak Random Sources.
534-543
- Noga Alon, Oded Goldreich, Johan Håstad, René Peralta:
Simple Constructions of Almost k-Wise Independent Random Variables.
544-553
- Mihir Bellare, Oded Goldreich, Shafi Goldwasser:
Randomness in Interactive Proofs.
563-572
- Noga Alon, Nimrod Megiddo:
Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time.
574-582
- Pravin M. Vaidya:
Reducing the Parallel Complexity of Certain Linear Programming Problems (Extended Abstract).
583-589
- Charles U. Martel, Ramesh Subramonian, Arvin Park:
Asynchronous PRAMs Are (Almost) as Good as Synchronous PRAMs.
590-599
- Bowen Alpern, Larry Carter, Ephraim Feig:
Uniform Memory Hierarchies.
600-608
- Johan Håstad, Mikael Goldmann:
On the Power of Small-Depth Threshold Circuits.
610-618
- Andrew Chi-Chih Yao:
On ACC and Threshold Circuits.
619-627
- Roman Smolensky:
On Interpolation by Analytic Functions with Special Properties and Some Weak Lower Bounds on the Size of Circuits with Symmetric Gates.
628-631
- Jehoshua Bruck, Roman Smolensky:
Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract).
632-641
- Mike Paterson, Nicholas Pippenger, Uri Zwick:
Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions.
642-650
- David Harel, Danny Raz:
Deciding Properties of Nonregular Programs (Preliminary Version).
652-661
- Patrick Lincoln, John C. Mitchell, Andre Scedrov, Natarajan Shankar:
Decision Problems for Propositional Linear Logic.
662-671
- Oded Maler, Amir Pnueli:
Tight Bounds on the Complexity of Cascaded Decomposition of Automata.
672-682
- Michael Kaminski, Nissim Francez:
Finite-Memory Automata (Extended Abstract).
683-688
- James F. Lynch:
Probabilities of Sentences about Very Sparse Random Graphs.
689-696
- Dalit Naor, Dan Gusfield, Charles U. Martel:
A Fast Algorithm for Optimally Increasing the Edge-Connectivity.
698-707
- András Frank:
Augmenting Graphs to Meet Edge-Connectivity Requirements.
708-718
- Michael L. Fredman, Dan E. Willard:
Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths.
719-725
- Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao:
Approximation through Multicommodity Flow.
726-737
- Shimon Even, Ami Litman, Peter Winkler:
Computing with Snakes in Directed Networks of Automata (Extended Abstract).
740-745
- Amir Pnueli, Roni Rosner:
Distributed Reactive Systems Are Hard to Synthesize.
746-757
- Zhi-Quan Luo, John N. Tsitsiklis:
Communication Complexity of Algebraic Computation (Extended Abstract).
758-765
- Ran Canetti, Oded Goldreich:
Bounds on Tradeoffs between Randomness and Communication Complexity.
766-775
- Seinosuke Toda:
The Complexity of Finding Medians.
778-787
- Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis:
On the Predictability of Coupled Automata: An Allegory about Chaos.
788-793
- Christos H. Papadimitriou:
On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract).
794-801
- Yuri Gurevich:
Matrix Decomposition Problem Is Complete for the Average Case.
802-811
- Russell Impagliazzo, Leonid A. Levin:
No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random.
812-821
- Antoni Koscielski, Leszek Pacholski:
Complexity of Unification in Free Groups and Free Semi-groups.
824-829
- Brigitte Vallée, Philippe Flajolet:
The Lattice Reduction Algorithm of Gauss: An Average Case Analysis.
830-839
- Dima Grigoriev, Marek Karpinski, Michael F. Singer:
Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents.
840-846
- Gwoboa Horng, Ming-Deh A. Huang:
Simplifying Nested Radicals and Solving Polynomials by Radicals in Minimum Depth.
847-856
- László Babai, Gábor Hetyei, William M. Kantor, Alexander Lubotzky, Ákos Seress:
On the Diameter of Finite Groups.
857-865
- Omer Berkman, Joseph JáJá, Sridhar Krishnamurthy, Ramakrishna Thurimella, Uzi Vishkin:
Some Triply-Logarithmic Parallel Algorithms (Extended Abstract).
871-881
Copyright © Thu Nov 26 19:26:05 2009
by Michael Ley (ley@uni-trier.de)
