35. FOCS 1994: Santa Fe, New Mexico, USA

• David R. Karger, Rajeev Motwani, Madhu Sudan:
  Approximate Graph Coloring by Semidefinite Programming. 2-13
  
• Naveen Garg, Huzur Saran, Vijay V. Vazirani:
  Finding separator cuts in planar graphs within twice the optimal. 14-23
  
• Noga Alon, Alan M. Frieze, Dominic Welsh:
  Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs. 24-35
  
• Mario Szegedy:
  A note on the Theta number of Lovász and the generalized Delsarte bound. 36-39
  
• Jeffrey C. Jackson:
  An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution. 42-53
  
• Nader H. Bshouty, Zhixiang Chen, Steven Homer:
  On Learning Discretized Geometric Concepts (Extended Abstract). 54-63
  
• Aditi Dhagat, Lisa Hellerstein:
  PAC Learning with Irrelevant Attributes. 64-74
  
• Michael A. Bender, Donna K. Slonim:
  The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs. 75-85
  
• Leonard M. Adleman:
  Algorithmic Number Theory-The Complexity Contribution. 88-113
  
• Daniel R. Simon:
  On the Power of Quantum Cryptography. 116-123
  
• Peter W. Shor:
  Algorithms for Quantum Computation: Discrete Logarithms and Factoring. 124-134
  
• Jin-yi Cai, Richard J. Lipton, Yechezkel Zalcstein:
  The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices. 135-142
  
• Jin-yi Cai, Wolfgang H. J. Fuchs, Dexter Kozen, Zicheng Liu:
  Efficient Average-Case Algorithms for the Modular Group. 143-152
  
• David Eppstein:
  Finding the k Shortest Paths. 154-165
  
• S. Rao Kosaraju, James K. Park, Clifford Stein:
  Long Tours and Short Superstrings (Preliminary Version). 166-177
  
• Karsten Weihe:
  Maximum (s, t)-Flows in Planar Networks in O(|V| log |V|) Time. 178-189
  
• Edith Cohen:
  Estimating the Size of the Transitive Closure in Linear Time. 190-200
  
• R. Ravi:
  Rapid Rumor Ramification: Approximating the minimum broadcast time (Extended Abstract). 202-213
  
• Moni Naor, Avishai Wool:
  The Load, Capacity and Availability of Quorum Systems. 214-225
  
• Gene Itkis, Leonid A. Levin:
  Fast and Lean Self-Stabilizing Asynchronous Protocols. 226-239
  
• Baruch Awerbuch, Yossi Azar:
  Local Optimization of Global Objectives: Competitive Distributed Deadlock Resolution and Resource Allocation. 240-249
  
• David R. Karger, Daphne Koller:
  (De)randomized Construction of Small Sample Spaces in \calNC. 252-263
  
• Aravind Srinivasan, David Zuckerman:
  Computing with Very Weak Random Sources. 264-275
  
• Mihir Bellare, John Rompel:
  Randomness-Efficient Oblivious Sampling. 276-287
  
• Ronitt Rubinfeld:
  On the robustness of functional equations. 288-299
  
• Andrew Chi-Chih Yao:
  A Lower Bound for the Monotone Depth of Connectivity. 302-308
  
• Rakesh K. Sinha, Jayram S. Thathachar:
  Efficient Oblivious Branching Programs for Threshold Functions. 309-317
  
• Noam Nisan, Steven Rudich, Michael E. Saks:
  Products and Help Bits in Decision Trees. 318-329
  
• Daniel J. Kleitman, Frank Thomson Leighton, Yuan Ma:
  On the Design of Reliable Boolean Circuits that Contain Partially Unreliable Gates. 332-346
  
• Abhiram G. Ranade, Saul Schleimer, Daniel Shawcross Wilkerson:
  Nearly Tight Bounds for Wormhole Routing. 347-355
  
• Robert D. Blumofe:
  Scheduling Multithreaded Computations by Work Stealing. 356-368
  
• Miroslaw Kutylowski, Krzysztof Lorys, Brigitte Oesterdiekhoff, Rolf Wanka:
  Fast and Feasible Periodic Sorting Networks of Constant Depth. 369-380
  
• Manuel Blum, Hal Wasserman:
  Program Result-Checking: A Theory of Testing Meets a Test of Theory. 382-392
  
• Elias Koutsoupias, Christos H. Papadimitriou:
  Beyond Competitive Analysis. 394-400
  
• Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts:
  A Theory of Competitive Analysis for Distributed Algorithms. 401-411
  
• Baruch Awerbuch, Rainer Gawlick, Frank Thomson Leighton, Yuval Rabani:
  On-line Admission Control and Circuit Routing for High Performance Computing and Communication. 412-423
  
• Carsten Lund, Steven Phillips, Nick Reingold:
  IP over connection-oriented networks and distributional paging. 424-434
  
• Silvio Micali:
  CS Proofs (Extended Abstracts). 436-453
  
• Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung:
  On Monotone Formula Closure of SZK. 454-465
  
• Joe Kilian:
  On the complexity of Bounded-Interaction and Noninteractive Zero-Knowledge Proofs. 466-477
  
• Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky:
  Reducibility and Completeness in Multi-Party Private Computations. 478-489
  
• David Aldous, Umesh V. Vazirani:
  ``Go With the Winners'' Algorithms. 492-501
  
• Bernd Gärtner, Günter M. Ziegler:
  Randomized Simplex Algorithms on Klee-Mintny Cubes. 502-510
  
• Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki:
  Motion Planning on a Graph (Extended Abstract). 511-520
  
• Jon M. Kleinberg:
  The Localization Problem for Mobile Robots. 521-531
  
• Michael Ben-Or:
  Algebraic Computation Trees in Characteristi p>0 (Extended Abstract). 534-539
  
• C. Andrew Neff, John H. Reif:
  An O(n^1+epsilon log b) Algorithm for the Complex Roots Problem. 540-547
  
• Dima Grigoriev, Nicolai Vorobjov:
  Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates. 548-552
  
• György Turán, Farrokh Vatan:
  On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-in (Extended Abstract). 553-564
  
• Michael Sipser, Daniel A. Spielman:
  Expander Codes. 566-576
  
• Nathan Linial, Eran London, Yuri Rabinovich:
  The geometry of graphs and some of its algorithmic applications. 577-591
  
• Anil Kamath, Rajeev Motwani, Krishna V. Palem, Paul G. Spirakis:
  Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture. 592-603
  
• Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby, Madhu Sudan:
  Priority Encoding Transmission. 604-612
  
• Thomas Schwentick:
  Graph Connectivity and Monadic NP. 614-622
  
• Yoram Hirshfeld, Mark Jerrum, Faron Moller:
  A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes. 623-631
  
• Saugata Basu, Richard Pollack, Marie-Françoise Roy:
  On the Combinatorial and Algebraic Complexity of Quantifier Elimination. 632-641
  
• Witold Charatonik, Leszek Pacholski:
  Set constraints with projections are in NEXPTIME. 642-653
  
• Ravi Kannan:
  Markov Chains and Polynomial Time Algorithms. 656-671
  
• Bernard Chazelle:
  A Spectral Approach to Lower Bounds. 674-682
  
• Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos:
  Parallel Algorithms for Higher-Dimensional Convex Hulls. 683-694
  
• Kenneth L. Clarkson:
  More Output-Sensitive Geometric Algorithms (Extended Abstract). 695-702
  
• Sunil Arya, David M. Mount, Michiel H. M. Smid:
  Randomized and deterministic algorithms for geometric spanners of small diameter. 703-712
  
• Arne Andersson, Stefan Nilsson:
  A New Efficient Radix Sort. 714-721
  
• Daniel H. Greene, Michal Parnas, F. Frances Yao:
  Multi-Index Hashing for Information Retrieval. 722-731
  
• K. Bruce Erickson, Richard E. Ladner, Anthony LaMarca:
  Optimizing Static Calendar Queues. 732-743
  
• Monika Rauch Henzinger:
  Fully Dynamic Cycle-Equivalence in Graphs. 744-755
  
• Dmitry Keselman, Amihood Amir:
  Maximum Agreement Subtree in a Set of Evolutionary Trees-Metrics and Efficient Algorithms. 758-769
  
• Martin Farach, Mikkel Thorup:
  Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract). 770-779
  
• Haim Kaplan, Ron Shamir, Robert Endre Tarjan:
  Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping. 780-791
  
• Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, Pavel Pudlák:
  Lower Bound on Hilbert's Nullstellensatz and propositional proofs. 794-806
  
• Eric Allender, Martin Strauss:
  Measure on Small Complexity Classes, with Applications for BPP. 807-818
  
• Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
  On Syntactic versus Computational Views of Approximability. 819-830
  
• Noam Nisan, Avi Wigderson:
  On Rank vs. Communication Complexity. 831-836
  

Last update Tue Feb 14 03:56:13 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page