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