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