34. FOCS 1993: Palo Alto, California, USA

• 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, Boris Spieker:
  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
  
• C. K. 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 Tradefoff 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, Marc Tommasi:
  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
  

Last update Fri May 25 08:14:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page