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