| 1993 | Counting Rational Points on Curves over Finite Fields (Extended Abstract) | Ming-Deh A. Huang, Doug Ierardi |
| 1993 | Efficient Computation of Euclidean Shortest Paths in the Plane | John Hershberger, Subhash Suri |
| 1993 | Top-Down Lower Bounds for Depth 3 Circuits | Johan Hstad, Stasys Jukna, Pavel Pudlk |
| 1993 | The shrinkage exponent is 2 | Johan Hstad |
| 1993 | Optimal Bi-Weighted Binary Trees and the Complexity of Maintaining Partial Sums | Haripriyan Hampapuram, Michael L. Fredman |
| 1993 | Near-Quadratic Bounds for the Motion Planning Problem for a Polygon in a Polygonal Environment | Dan Halperin, Micha Sharir |
| 1993 | Directed vs. Undirected Monotone Contact Networks for Threshold Functions | Magns M. Halldrsson, Jaikumar Radhakrishnan, K. V. Subrahmanyam |
| 1993 | Gages Accept Concurrent Behavior | Vineet Gupta, Vaughan R. Pratt |
| 1993 | NP Trees and Carnap's Modal Logic | Georg Gottlob |
| 1993 | External-Memory Computational Geometry (Preliminary Version) | Michael T. Goodrich, Jyh-Jong Tsay, Darren Erik Vengroff, Jeffrey Scott Vitter |
| 1993 | A Chernoff bound for random walks on expander graphs | David Gillman |
| 1993 | Solving Systems of Set Constraints with Negated Subset Relationships | Rmi Gilleron, Sophie Tison, Marc Tommasi |
| 1993 | Testing Equalities of Multiplicative Representations in Polynomial Time (Extended Abstract) | Guoqiang Ge |
| 1993 | A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract) | Juan A. Garay, Shay Kutten, David Peleg |
| 1993 | A Framework for Cost-scaling Algorithms for Submodular Flow Problems | Harold N. Gabow |
| 1993 | Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems | Matthew K. Franklin, Zvi Galil, Moti Yung |
| 1993 | Dynamic Word Problems | Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum |
| 1993 | A Randomized Time-Space Tradeoff of \tildeO(m\tildeR) for USTCON | Uriel Feige |
| 1993 | Signal Propagation, with Application to a Lower Bound on the Depth of Noisy Formulas | William S. Evans, Leonard J. Schulman |
| 1993 | Better Lower Bounds on Detecting Affine and Spherical Degeneracies | Jeff Erickson, Raimund Seidel |
| 1993 | The Complexity of the Theory of p-adic Numbers | Lavinia Egidi |
| 1993 | Logical Reducibility and Monadic NP | Stavros S. Cosmadakis |
| 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 | Fast algorithms for constructing t-spanners and paths with stretch t | Edith Cohen |
| 1993 | Parallel computable higher type functionals (Extended Abstract) | Peter Clote, Aleksandar Ignjatovic, Bruce M. Kapron |