| 1993 | Size-depth trade-offs for threshold circuits. | Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks |
| 1993 | Multiple matching of rectangular patterns. | Ramana M. Idury, Alejandro A. Schffer |
| 1993 | Matrix searching with the shortest path metric. | John Hershberger, Subhash Suri |
| 1993 | The asynchronous computability theorem for t-resilient tasks. | Maurice Herlihy, Nir Shavit |
| 1993 | Simulating threshold circuits by majority circuits. | Mikael Goldmann, Marek Karpinski |
| 1993 | Polynomial space polynomial delay algorithms for listing families of graphs. | Leslie Ann Goldberg |
| 1993 | Counting curves and their projections. | Joachim von zur Gathen, Marek Karpinski, Igor E. Shparlinski |
| 1993 | Approximate max-flow min-(multi)cut theorems and their applications. | Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis |
| 1993 | Fully polynomial Byzantine agreement in t+1 rounds. | Juan A. Garay, Yoram Moses |
| 1993 | Efficient learning of typical finite automata from random walks. | Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie |
| 1993 | Decision trees: old and new results. | Rudolf Fleischer |
| 1993 | Maximum k-chains in planar point sets: combinatorial structure and algorithms. | Stefan Felsner, Lorenz Wernisch |
| 1993 | Optimal online scheduling of parallel jobs with dependencies. | Anja Feldmann, Ming-Yang Kao, Jir Sgall, Shang-Hua Teng |
| 1993 | Monotone monadic SNP and constraint satisfaction. | Toms Feder, Moshe Y. Vardi |
| 1993 | A robust model for finding optimal evolutionary trees. | Martin Farach, Sampath Kannan, Tandy J. Warnow |
| 1993 | Separator based sparsification for dynamic planar graph algorithms. | David Eppstein, Zvi Galil, Giuseppe F. Italiano, Thomas H. Spencer |
| 1993 | Time-space trade-offs for undirected st-connectivity on a JAG. | Jeff Edmonds |
| 1993 | Contention in shared memory algorithms. | Cynthia Dwork, Maurice Herlihy, Orli Waarts |
| 1993 | Fast perfection-information leader-election protocol with linear immunity. | Jason Cooper, Nathan Linial |
| 1993 | Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions. | Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor |
| 1993 | Multi-scale self-simulation: a technique for reconfiguring arrays with faults. | Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman |
| 1993 | Reinventing the wheel: an optimal data structure for connectivity queries. | Robert F. Cohen, Giuseppe Di Battista, Arkady Kanevsky, Roberto Tamassia |
| 1993 | Markov chains, computer proofs, and average-case analysis of best fit bin packing. | Edward G. Coffman Jr., David S. Johnson, Peter W. Shor, Richard R. Weber |
| 1993 | Some complexity issues on the simply connected regions of the two-dimensional plane. | Arthur W. Chou, Ker-I Ko |
| 1993 | Improved bounds on weak epsilon-nets for convex sets. | Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, Micha Sharir, Emo Welzl |