31. FOCS 1990: St. Louis, Missouri, USA
31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I. IEEE Computer Society 1990- 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
- 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
- John H. Reif, J. D. Tygar, Akitoshi Yoshida: The Computability and Complexity of Optical Beam Tracing. 106-114
- 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
- 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
- Avrim Blum: Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain. 211-218
- Bernard Chazelle: Triangulating a Simple Polygon in Linear Time. 220-230
- 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
- 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
- Sampath Kannan, Tandy Warnow: Inferring Evolutionary History from DNA Sequences (Extended Abstract). 362-371
- 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
- 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
- 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II. IEEE Computer Society 1990
- 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
- Avrim Blum: Some Tools for Approximate 3-Coloring (Extended Abstract). 554-562
- 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
- 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
- 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
- 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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team