default search action
34th FOCS 1993: Palo Alto, California, USA
- 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993. IEEE Computer Society 1993, ISBN 0-8186-4370-6
- Avrim Blum, Prasad Chalasani:
An On-Line Algorithm for Improving Performance in Navigation. 2-11 - Sandy Irani, Yuval Rabani
:
On the Value of Information in Coordination Games (preliminary version). 12-21 - Baruch Awerbuch, Yair Bartal, Amos Fiat:
Heat & Dump: Competitive Distributed Paging. 22-31 - Baruch Awerbuch, Yossi Azar, Serge A. Plotkin:
Throughput-Competitive On-Line Routing. 32-40 - Georg Gottlob:
NP Trees and Carnap's Modal Logic. 42-51 - Stavros S. Cosmadakis:
Logical Reducibility and Monadic NP. 52-61 - Vineet Gupta, Vaughan R. Pratt:
Gages Accept Concurrent Behavior. 62-71 - Peter Clote, Aleksandar Ignjatovic, Bruce M. Kapron
Parallel computable higher type functionals (Extended Abstract). 72-81 - David R. Karger:
Random Sampling in Matroids, with Applications to Graph Connectivity and Minimum Spanning Trees. 84-93 - Mark Jerrum, Gregory B. Sorkin:
Simulated Annealing for Graph Bisection. 94-103 - Shenfeng Chen, John H. Reif:
Using Difficulty of Prediction to Decrease Computation: Fast Sort, Priority Queue and Convex Hull on Entropy Bounded Inputs. 104-112 - Johan Håstad:
The shrinkage exponent is 2. 114-123 - Johan Håstad, Stasys Jukna, Pavel Pudlák:
Top-Down Lower Bounds for Depth 3 Circuits. 124-129 - Roman Smolensky:
On Representations by Low-Degree Polynomials. 130-138 - Richa Agarwala, David Fernández-Baca:
A Polynomial-Time Algorithm for the Perfect Phylogeny Problem when the Number of Character States is Fixed. 140-147 - Vineet Bafna, Pavel A. Pevzner:
Genome Rearrangements and Sorting by Reversals. 148-157 - Shang-Hua Teng, F. Frances Yao:
Approximating Shortest Superstrings. 158-165 - Ran Raz
On the "log rank"-Conjecture in Communication Complexity. 168-176 - David W. Juedes, Jack H. Lutz:
The Complexity and Distribution of Hard Problems (Extended Abstract). 177-185 - Shiva Chaudhuri:
Sensitive Functions and Approximate Problems. 186-193 - Yehuda Afek, Gideon Stupp:
Synchronization power depends on the register size (Preliminary Version). 196-205 - Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, Mark R. Tuttle:
A Tight Lower Bound for k-Set Agreement. 206-215 - Chung Keung Poon:
Space Bounds for Graph Connectivity Problems on Node-named JAGs and Node-ordered JAGs. 218-227 - Greg Barnes, Jeff Edmonds:
Time-Space Bounds for Directed s-t Connectivity on JAG Models (Extended Abstract). 228-237 - Uriel Feige:
A Randomized Time-Space Tradeoff of \tildeO(m\tildeR) for USTCON. 238-246 - Richard Cole, Maxime Crochemore, Zvi Galil, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park, Wojciech Rytter:
Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. 248-258 - Philip N. Klein, Sairam Subramanian:
A linear-processor polylog-time algorithm for shortest paths in planar graphs. 259-270 - Yonatan Aumann, Zvi M. Kedem, Krishna V. Palem, Michael O. Rabin:
Highly Efficient Asynchronous Execution of Large-Grained Parallel Programs. 271-280 - Javed A. Aslam, Scott E. Decatur:
General Bounds on Statistical Query Learning and PAC Learning with Noise via Hypothesis Bounding. 282-291 - Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler:
Scale-sensitive Dimensions, Uniform Convergence, and Learnability. 292-301 - Nader H. Bshouty:
Exact Learning via the Monotone Theory (Extended Abstract). 302-311 - Avrim Blum, Ravi Kannan:
Learning an Intersection of k Halfspaces over a Uniform Distribution. 312-320 - Sridhar Rajagopalan, Vijay V. Vazirani:
Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs. 322-331 - Paul B. Callahan:
Optimal Parallel All-Nearest-Neighbors Using the Well-Separated Pair Decomposition (Preliminary Version). 332-340 - Christos Kaklamanis, Danny Krizanc, Satish Rao:
Universal Emulations with Sublogarithmic Slowdown. 341-350 - Andrew Chi-Chih Yao:
Quantum Circuit Complexity. 352-361 - Gilles Brassard, Claude Crépeau, Richard Jozsa, Denis Langlois:
A Quantum Bit Commitment Scheme Provably Unbreakable by both Parties. 362-371 - Rémi Gilleron, Sophie Tison
Solving Systems of Set Constraints with Negated Subset Relationships. 372-380 - Dan Halperin, Micha Sharir:
Near-Quadratic Bounds for the Motion Planning Problem for a Polygon in a Polygonal Environment. 382-391 - Bernard Chazelle:
Geometric Discrepancy Revisited. 392-399 - Hervé Brönnimann, Bernard Chazelle, Jirí Matousek:
Product Range Spaces, Sensitive Sampling, and Derandomization. 400-409 - Lavinia Egidi:
The Complexity of the Theory of p-adic Numbers. 412-421 - Guoqiang Ge:
Testing Equalities of Multiplicative Representations in Polynomial Time (Extended Abstract). 422-426 - Robert Beals, László Babai:
Las Vegas algorithms for matrix groups. 427-436 - Tomasz Radzik:
Faster Algorithms for the Generalized Network Flow Problem. 438-448 - Harold N. Gabow:
A Framework for Cost-scaling Algorithms for Submodular Flow Problems. 449-458 - Baruch Awerbuch, Frank Thomson Leighton:
A Simple Local-Control Approximation Algorithm for Multicommodity Flow. 459-468 - Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum:
Dynamic Word Problems. 470-479 - Haripriyan Hampapuram, Michael L. Fredman:
Optimal Bi-Weighted Binary Trees and the Complexity of Maintaining Partial Sums. 480-485 - Pascal Koiran:
A Weak Version of the Blum, Shub & Smale model. 486-495 - Micha Sharir:
Almost Tight Upper Bounds for Lower Envelopes in Higher Dimensions. 498-507 - John Hershberger, Subhash Suri:
Efficient Computation of Euclidean Shortest Paths in the Plane. 508-517 - Boris Aronov, Micha Sharir:
The Union of Convex Polyhedra in Three Dimensions. 518-527 - Jeff Erickson, Raimund Seidel:
Better Lower Bounds on Detecting Affine and Spherical Degeneracies. 528-536 - Amir M. Ben-Amram, Zvi Galil:
When can we sort in o(n log n) time? 538-546 - Richard Chang, William I. Gasarch:
On Bounded Queries and Approximation. 547-556 - David Shallcross, Victor Y. Pan, Yu Lin-Kriz:
The NC Equivalence of Planar Integer Linear Programming and Euclidean GCD. 557-564 - Alexander I. Barvinok:
A Polynomial Time Algorithm for Counting Integral Points in Polyhedra when the Dimension Is Fixed. 566-572 - Michael McAllister, David G. Kirkpatrick, Jack Snoeyink:
A Compact Piecewise-Linear Voronoi Diagram for Convex Sites in the Plane. 573-582 - Scott A. Mitchell:
Refining a Triangulation of a Planar Straight-Line Graph to Eliminate Large Angles. 583-591 - William S. Evans, Leonard J. Schulman:
Signal Propagation, with Application to a Lower Bound on the Depth of Noisy Formulas. 594-603 - Magnús M. Halldórsson, Jaikumar Radhakrishnan, K. V. Subrahmanyam:
Directed vs. Undirected Monotone Contact Networks for Threshold Functions. 604-613 - Ming-Deh A. Huang, Doug Ierardi:
Counting Rational Points on Curves over Finite Fields (Extended Abstract). 616-625 - John H. Reif:
An O(n log ^3 n) Algorithm for the Real Root Problem. 626-635 - Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg:
Near-Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers. 638-647 - Edith Cohen:
Fast algorithms for constructing t-spanners and paths with stretch t. 648-658 - Juan A. Garay, Shay Kutten, David Peleg:
A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract). 659-668 - Matthew K. Franklin, Zvi Galil, Moti Yung:
Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems. 670-679 - David Gillman:
A Chernoff bound for random walks on expander graphs. 680-691 - Guy Kortsarz, David Peleg:
On Choosing a Dense Subgraph (Extended Abstract). 692-701 - Charles E. Leiserson, Satish Rao, Sivan Toledo:
Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers (Extended Abstract). 704-713 - Michael T. Goodrich, Jyh-Jong Tsay, Darren Erik Vengroff, Jeffrey Scott Vitter:
External-Memory Computational Geometry (Preliminary Version). 714-723 - Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk:
The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations. 724-733 - Frank Thomson Leighton, Yuan Ma:
Breaking the Theta(n log ^2 n) Barrier for Sorting with Faults (Extended Abstract). 734-743
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-12 20:48 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: