31. FOCS 1990: St. Louis, Missouri, USA

• 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
  
• 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
  
• 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
  
• Baruch Awerbuch, David Peleg:
  Sparse Partitions (Extended Abstract). 503-513
  
• Baruch Awerbuch, David Peleg:
  Network Synchronization with Polylogarithmic Overhead. 514-522
  
• 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
  
• 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
  

Last update Fri May 25 08:14:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page