| 1990 | 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I |
| 1990 | 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II |
| 1990 | A (fairly) Simple Circuit that (usually) Sorts Frank Thomson Leighton, C. Greg Plaxton |
| 1990 | A Characterization of \sharp P Arithmetic Straight Line Programs László Babai, Lance Fortnow |
| 1990 | A Dining Philosophers Algorithm with Polynomial Response Time Baruch Awerbuch, Michael E. Saks |
| 1990 | A Fast Algorithm for Optimally Increasing the Edge-Connectivity Dalit Naor, Dan Gusfield, Charles U. Martel |
| 1990 | A Markovian Extension of Valiant's Learning Model (Extended Abstract) David J. Aldous, Umesh V. Vazirani |
| 1990 | A Time-Space Tradeoff for Boolean Matrix Multiplication Karl R. Abrahamson |
| 1990 | A Tree-Partitioning Technique with Applications to Expression Evaluation and Term Matching (Extended Abstract) S. Rao Kosaraju, Arthur L. Delcher |
| 1990 | Algebraic Methods for Interactive Proof Systems Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan |
| 1990 | An Approach for Proving Lower Bounds: Solution of Gilbert-Pollak's Conjecture on Steiner Ratio Ding-Zhu Du, Frank K. Hwang |
| 1990 | Approximate String Matching in Sublinear Expected Time William I. Chang, Eugene L. Lawler |
| 1990 | Approximation through Multicommodity Flow Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao |
| 1990 | Are Wait-Free Algorithms Fast? (Extended Abstract) Hagit Attiya, Nancy A. Lynch, Nir Shavit |
| 1990 | Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract) Christos Kaklamanis, Anna R. Karlin, Frank Thomson Leighton, Victor Milenkovic, Prabhakar Raghavan, Satish Rao, Clark D. Thomborson, A. Tsantilas |
| 1990 | Asynchronous PRAMs Are (Almost) as Good as Synchronous PRAMs Charles U. Martel, Ramesh Subramonian, Arvin Park |
| 1990 | Augmenting Graphs to Meet Edge-Connectivity Requirements András Frank |
| 1990 | Bounds on Tradeoffs between Randomness and Communication Complexity Ran Canetti, Oded Goldreich |
| 1990 | Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract) Noga Alon, Moni Naor |
| 1990 | Coloring Inductive Graphs On-Line Sandy Irani |
| 1990 | Communication Complexity of Algebraic Computation (Extended Abstract) Zhi-Quan Luo, John N. Tsitsiklis |
| 1990 | Communication-Optimal Maintenance of Replicated Information Baruch Awerbuch, Israel Cidon, Shay Kutten |
| 1990 | Communication-Space Tradeoffs for Unrestricted Protocols Paul Beame, Martin Tompa, Peiyuan Yan |
| 1990 | Competitive k-Server Algorithms (Extended Abstract) Amos Fiat, Yuval Rabani, Yiftach Ravid |
| 1990 | Complexity of Unification in Free Groups and Free Semi-groups Antoni Koscielski, Leszek Pacholski |
| 1990 | Computing with Snakes in Directed Networks of Automata (Extended Abstract) Shimon Even, Ami Litman, Peter Winkler |
| 1990 | Constructing Generalized Universal Traversing Sequences of Polynomial Size for Graphs with Small Diameter (Extended Abstract) Sorin Istrail |
| 1990 | Counting and Cutting Cycles of Lines and Rods in Space Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink |
| 1990 | Deciding Properties of Nonregular Programs (Preliminary Version) David Harel, Danny Raz |
| 1990 | Decision Problems for Propositional Linear Logic Patrick Lincoln, John C. Mitchell, Andre Scedrov, Natarajan Shankar |
| 1990 | Deterministic On-Line Routing on Area-Universal Networks (Extended Abstract) Paul Bay, Gianfranco Bilardi |
| 1990 | Distributed Reactive Systems Are Hard to Synthesize Amir Pnueli, Roni Rosner |
| 1990 | Drawing Graphs in the Plane with High Resolution Michael Formann, Torben Hagerup, James Haralambides, Michael Kaufmann, Frank Thomson Leighton, Antonios Symvonis, Emo Welzl, Gerhard J. Woeginger |
| 1990 | Efficient Distribution-free Learning of Probabilistic Concepts (Extended Abstract) Michael J. Kearns, Robert E. Schapire |
| 1990 | Efficient Parallel Algorithms for Tree-Decomposition and Related Problems Jens Lagergren |
| 1990 | Efficiently Inverting Bijections Given by Straight Line Programs Carl Sturtivant, Zhi-Li Zhang |
| 1990 | Exact Identification of Circuits Using Fixed Points of Amplification Functions (Extended Abstract) Sally A. Goldman, Michael J. Kearns, Robert E. Schapire |
| 1990 | Exploring an Unknown Graph (Extended Abstract) Xiaotie Deng, Christos H. Papadimitriou |
| 1990 | Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions Mike Paterson, Nicholas Pippenger, Uri Zwick |
| 1990 | Faster Tree Pattern Matching Moshe Dubiner, Zvi Galil, Edith Magen |
| 1990 | Fault Tolerant Sorting Network Shay Assaf, Eli Upfal |
| 1990 | Finite-Memory Automata (Extended Abstract) Michael Kaminski, Nissim Francez |
| 1990 | General Weak Random Sources David Zuckerman |
| 1990 | Hidden Surface Removal for Axis-Parallel Polyhedra (Extended Abstract) Mark de Berg, Mark H. Overmars |
| 1990 | IP=PSPACE Adi Shamir |
| 1990 | Inferring Evolutionary History from DNA Sequences (Extended Abstract) Sampath Kannan, Tandy J. Warnow |
| 1990 | Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents Dima Grigoriev, Marek Karpinski, Michael F. Singer |
| 1990 | Learning Conjunctions of Horn Clauses (Extended Abstract) Dana Angluin, Michael Frazier, Leonard Pitt |
| 1990 | Matrix Decomposition Problem Is Complete for the Average Case Yuri Gurevich |
| 1990 | Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract) Uriel Feige, Dror Lapidot, Adi Shamir |
| 1990 | Network Synchronization with Polylogarithmic Overhead Baruch Awerbuch, David Peleg |
| 1990 | New Results on Dynamic Planar Point Location Siu-Wing Cheng, Ravi Janardan |
| 1990 | No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random Russell Impagliazzo, Leonid A. Levin |
| 1990 | Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols László Babai, Lance Fortnow, Carsten Lund |
| 1990 | On ACC and Threshold Circuits Andrew Chi-Chih Yao |
| 1990 | On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract) Christos H. Papadimitriou |
| 1990 | On Interpolation by Analytic Functions with Special Properties and Some Weak Lower Bounds on the Size of Circuits with Symmetric Gates Roman Smolensky |
| 1990 | On Threshold Circuits for Parity Ramamohan Paturi, Michael E. Saks |
| 1990 | On the Complexity of Learning from Counterexamples and Membership Queries Wolfgang Maass, György Turán |
| 1990 | On the Diameter of Finite Groups László Babai, Gábor Hetyei, William M. Kantor, Alexander Lubotzky, Ákos Seress |
| 1990 | On the Exact Complexity of String Matching (Extended Abstract) Livio Colussi, Zvi Galil, Raffaele Giancarlo |
| 1990 | On the Power of Small-Depth Threshold Circuits Johan Håstad, Mikael Goldmann |
| 1990 | On the Predictability of Coupled Automata: An Allegory about Chaos Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis |
| 1990 | Online Algorithms for Finger Searching (Extended Abstract) Richard Cole, Arvind Raghunathan |
| 1990 | Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time Noga Alon, Nimrod Megiddo |
| 1990 | Perfectly Secure Message Transmission Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung |
| 1990 | Permuting Faith E. Fich, J. Ian Munro, Patricio V. Poblete |
| 1990 | Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract) Jehoshua Bruck, Roman Smolensky |
| 1990 | Private Computations Over the Integers (Extended Abstract) Benny Chor, Mihály Geréb-Graus, Eyal Kushilevitz |
| 1990 | Probabilities of Sentences about Very Sparse Random Graphs James F. Lynch |
| 1990 | Provably Good Mesh Generation Marshall W. Bern, David Eppstein, John R. Gilbert |
| 1990 | Randomized Online Graph Coloring (Preliminary Version) Sundar Vishwanathan |
| 1990 | Randomness in Interactive Proofs Mihir Bellare, Oded Goldreich, Shafi Goldwasser |
| 1990 | Reducing the Parallel Complexity of Certain Linear Programming Problems (Extended Abstract) Pravin M. Vaidya |
| 1990 | Robust Separations in Inductive Inference Mark A. Fulk |
| 1990 | Security Preserving Amplification of Hardness Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman |
| 1990 | Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain Avrim Blum |
| 1990 | Simple Constructions of Almost k-Wise Independent Random Variables Noga Alon, Oded Goldreich, Johan Håstad, René Peralta |
| 1990 | Simplifying Nested Radicals and Solving Polynomials by Radicals in Minimum Depth Gwoboa Horng, Ming-Deh A. Huang |
| 1990 | Some Tools for Approximate 3-Coloring (Extended Abstract) Avrim Blum |
| 1990 | Some Triply-Logarithmic Parallel Algorithms (Extended Abstract) Omer Berkman, Joseph F. JáJá, Sridhar Krishnamurthy, Ramakrishna Thurimella, Uzi Vishkin |
| 1990 | Sparse Partitions (Extended Abstract) Baruch Awerbuch, David Peleg |
| 1990 | Specified Precision Polynomial Root Isolation is in NC C. Andrew Neff |
| 1990 | The Complexity of Finding Medians Seinosuke Toda |
| 1990 | The Computability and Complexity of Optical Beam Tracing John H. Reif, J. D. Tygar, Akitoshi Yoshida |
| 1990 | The Lattice Reduction Algorithm of Gauss: An Average Case Analysis Brigitte Vallée, Philippe Flajolet |
| 1990 | The Mixing Rate of Markov Chains, an Isoperimetric Inequality, and Computing the Volume László Lovász, Miklós Simonovits |
| 1990 | Tight Bounds on the Complexity of Cascaded Decomposition of Automata Oded Maler, Amir Pnueli |
| 1990 | Time-Space Tradeoffs for Undirected Graph Traversal Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa |
| 1990 | Towards a DNA Sequencing Theory (Learning a String) (Preliminary Version) Ming Li |
| 1990 | Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths Michael L. Fredman, Dan E. Willard |
| 1990 | Triangulating a Simple Polygon in Linear Time Bernard Chazelle |
| 1990 | Uniform Memory Hierarchies Bowen Alpern, Larry Carter, Ephraim Feig |