default search action
35th FOCS 1994: Santa Fe, New Mexico, USA
- 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994. IEEE Computer Society 1994, ISBN 0-8186-6580-7
- 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 Computation. 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
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 J. Phillips, Nick Reingold:
IP over connection-oriented networks and distributional paging. 424-434 - Silvio Micali:
CS Proofs (Extended Abstracts). 436-453 - Alfredo De Santis
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 J. 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 N. Vorobjov Jr.:
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
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
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
On Rank vs. Communication Complexity. 831-836
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-11 20:52 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: