Conferences in DBLP
Andrew Chi-Chih Yao Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:1-10 [Conf ] Miklós Ajtai , Avi Wigderson Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:11-19 [Conf ] Ravi B. Boppana Amplification of Probabilistic Boolean Formulas [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:20-29 [Conf ] Nicholas Pippenger On Networks of Noisy Gates [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:30-38 [Conf ] David S. Johnson , Christos H. Papadimitriou , Mihalis Yannakakis How Easy Is Local Search? (Extended Abstract) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:39-42 [Conf ] Joseph JáJá Identification Is Easier Than Decoding [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:43-50 [Conf ] Klaus Ambos-Spies Three Theorems on Polynomial Degrees of NP-Sets [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:51-55 [Conf ] Ming Li Simulating Two Pushdown Stores by One Tape in O(n^1.5 sqrt(log n)) Time [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:56-64 [Conf ] Friedhelm Meyer auf der Heide Nondeterministic versus Probabilistic Linear Search Algorithms [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:65-73 [Conf ] Christos H. Papadimitriou , David Wolfe The Complexity of Facets Resolved [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:74-78 [Conf ] Dorit S. Hochbaum , David B. Shmoys Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:79-89 [Conf ] Harold N. Gabow A Scaling Algorithm for Weighted Matching on General Graphs [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:90-100 [Conf ] Alistair Moffat , Tadao Takaoka An All Pairs Shortest Path Algorithm with Expected Running Time O(n^2 log n) [Citation Graph (1, 0)][DBLP ] FOCS, 1985, pp:101-105 [Conf ] Csaba P. Gabor , Wen-Lian Hsu , Kenneth J. Supowit Recognizing Circle Graphs in Polynomial Time [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:106-116 [Conf ] Marshall W. Bern , Eugene L. Lawler , A. L. Wong Why Certain Subgraph Computations Require Only Linear Time [Citation Graph (1, 0)][DBLP ] FOCS, 1985, pp:117-125 [Conf ] Gad M. Landau , Uzi Vishkin Efficient String Matching in the Presence of Errors [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:126-136 [Conf ] Daniel S. Hirschberg , Lawrence L. Larmore The Least Weight Subsequence Problem (Extended Abstract) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:137-143 [Conf ] John H. Reif , Micha Sharir Motion Planning in the Presence of Moving Obstacles [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:144-154 [Conf ] Takao Asano , Tetsuo Asano , Leonidas J. Guibas , John Hershberger , Hiroshi Imai Visibility-Polygon Search and Euclidean Shortest Paths [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:155-164 [Conf ] Bernard Chazelle Slimming Down Search Structures: A Functional Approach to Algorithm Design [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:165-174 [Conf ] Lefteris M. Kirousis , Christos H. Papadimitriou The Complexity of Recognizing Polyhedral Scenes (Extended Abstract) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:175-185 [Conf ] Alok Aggarwal , Maria M. Klawe , David Lichtenstein , Nathan Linial , Avi Wigderson Multi-Layer Grid Embeddings [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:186-196 [Conf ] Paul M. B. Vitányi Area Penalty for Sublinear Signal Propagation Delay on Chip (Preliminary Version) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:197-207 [Conf ] Richard Cole , Alan Siegel On Information Flow and Sorting: New Upper and Lower Bounds for VLSI Circuits (Extended Abstract) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:208-221 [Conf ] Mikhail J. Atallah , Susanne E. Hambrusch Solving Tree Problems on a Mesh-Connected Processor Array (Preliminary Version) [Citation Graph (1, 0)][DBLP ] FOCS, 1985, pp:222-231 [Conf ] Ming-Deh A. Huang Solving Some Graph Problems with Optimal or Near-Optimal Speedup on Mesh-of-Trees Networks [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:232-240 [Conf ] Ronald I. Greenberg , Charles E. Leiserson Randomized Routing on Fat-Trees (Preliminary Version) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:241-249 [Conf ] Baruch Awerbuch , Robert G. Gallager Distributed BFS Algorithms [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:250-256 [Conf ] Francis Y. L. Chin , H. F. Ting An Almost Linear Time and O(n log n + e) Messages Distributed Algorithm for Minimum-Weight Spanning Trees [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:257-266 [Conf ] Paul Feldman , Silvio Micali Byzantine Agreement in Constant Expected Time (and Trusting No One) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:267-276 [Conf ] Noga Alon , Peter Frankl , Vojtech Rödl Geometrical Realization of Set Systems and Probabilistic Communication Complexity [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:277-280 [Conf ] Pedro Celis , Per-Åke Larson , J. Ian Munro Robin Hood Hashing (Preliminary Report) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:281-288 [Conf ] Michael J. Fischer , Mike Paterson Dynamic Monotone Priorities on Planar Sets (Extended Abstract) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:289-292 [Conf ] Jeffrey Scott Vitter Design and Analysis of Dynamic Huffman Coding (Extended Abstract) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:293-302 [Conf ] Harry G. Mairson Average Case Lower Bounds on the Construction and Searching of Partial Orders [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:303-311 [Conf ] Micha Sharir , Ron Livne On Minima of Functions, Intersection Patterns of Curves, and Davenport-Schinzel Sequences [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:312-320 [Conf ] Steven Rudich Inferring the Structure of a Markov Chain from its Output [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:321-326 [Conf ] Moshe Y. Vardi Automatic Verification of Probabilistic Concurrent Finite-State Programs [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:327-338 [Conf ] Hans-Juergen Boehm Partial Polymorphic Type Inference Is Undecidable [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:339-345 [Conf ] Yuri Gurevich , Saharon Shelah Fixed-Point Extensions of First-Order Logic [Citation Graph (11, 0)][DBLP ] FOCS, 1985, pp:346-353 [Conf ] Bruno Courcelle Equivalences and Transformations of Recursive Definitions [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:354-359 [Conf ] Zvi Galil , Stuart Haber , Moti Yung A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems (Extended Abstract) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:360-371 [Conf ] Josh D. Cohen , Michael J. Fischer A Robust and Verifiable Cryptographically Secure Election Scheme (Extended Abstract) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:372-382 [Conf ] Benny Chor , Shafi Goldwasser , Silvio Micali , Baruch Awerbuch Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:383-395 [Conf ] Benny Chor , Oded Goldreich , Johan Håstad , Joel Friedman , Steven Rudich , Roman Smolensky The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:396-407 [Conf ] Michael Ben-Or , Nathan Linial Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:408-416 [Conf ] Umesh V. Vazirani , Vijay V. Vazirani Random Polynomial Time Is Equal to Slightly-random Polynomial Time [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:417-428 [Conf ] Benny Chor , Oded Goldreich Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract) [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:429-442 [Conf ] Eric Bach , Jeffrey Shallit Factoring with Cyclotomic Polynomials [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:443-450 [Conf ] Erich Kaltofen Computing with Polynomials Given by Straight-Line Programs II: Sparse Factorization [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:451-458 [Conf ] András Frank , Éva Tardos An Application of Simultaneous Approximation in Combinatorial Optimization [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:459-463 [Conf ] László Lovász Computing ears and branchings in parallel [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:464-467 [Conf ] Alok Aggarwal , Bernard Chazelle , Leonidas J. Guibas , Colm Ó'Dúnlaing , Chee-Keng Yap Parallel Computational Geometry (Extended Abstract) [Citation Graph (1, 0)][DBLP ] FOCS, 1985, pp:468-477 [Conf ] Gary L. Miller , John H. Reif Parallel Tree Contraction and Its Application [Citation Graph (1, 0)][DBLP ] FOCS, 1985, pp:478-489 [Conf ] Zvi Galil , Victor Y. Pan Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:490-495 [Conf ] John H. Reif An Optimal Parallel Algorithm for Integer Sorting [Citation Graph (1, 0)][DBLP ] FOCS, 1985, pp:496-504 [Conf ] Eugene M. Luks , Pierre McKenzie Fast Parallel Computation with Permutation Groups [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:505-514 [Conf ] Dexter Kozen , Chee-Keng Yap Algebraic Cell Decomposition in NC (Preliminary Version) [Citation Graph (5, 0)][DBLP ] FOCS, 1985, pp:515-521 [Conf ] Victor Y. Pan Fast and Efficient Algorithms for Sequential and Parallel Evaluation of Polynomial Zeros and of Matrix Polynomials [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:522-531 [Conf ] Friedhelm Meyer auf der Heide , Avi Wigderson The Complexity of Parallel Sorting [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:532-540 [Conf ] Richard M. Karp , Eli Upfal , Avi Wigderson The Complexity of Parallel Computation on Matroids [Citation Graph (0, 0)][DBLP ] FOCS, 1985, pp:541-550 [Conf ]