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