| 1993 | Improved bounds on the max-flow min-cut ratio for multicommodity flows. | Serge A. Plotkin, va Tardos |
| 1993 | Self-routing superconcentrators. | Nicholas Pippenger |
| 1993 | Online load balancing and network flow. | Steven J. Phillips, Jeffery R. Westbrook |
| 1993 | The network inhibition problem. | Cynthia A. Phillips |
| 1993 | Finding minimum-quotient cuts in planar graphs. | James K. Park, Cynthia A. Phillips |
| 1993 | Linear programming without the matrix. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1993 | More deterministic simulation in logspace. | Noam Nisan, David Zuckerman |
| 1993 | What can be computed locally? | Moni Naor, Larry J. Stockmeyer |
| 1993 | A deterministic algorithm for the three-dimensional diameter problem. | Jir Matousek, Otfried Schwarzkopf |
| 1993 | Finiteness results for sigmoidal "neural" networks. | Angus Macintyre, Eduardo D. Sontag |
| 1993 | Bounds for the computational power and learning complexity of analog neural nets. | Wolfgang Maass |
| 1993 | On the hardness of approximating minimization problems. | Carsten Lund, Mihalis Yannakakis |
| 1993 | A parallel approximation algorithm for positive linear programming. | Michael Luby, Noam Nisan |
| 1993 | Efficient construction of a small hitting set for combinatorial rectangles in high dimension. | Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman |
| 1993 | Lower bounds for randomized mutual exclusion. | Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman |
| 1993 | Constructing small sample spaces satisfying given constraints. | Daphne Koller, Nimrod Megiddo |
| 1993 | Excluded minors, network decomposition, and multicommodity flow. | Philip N. Klein, Serge A. Plotkin, Satish Rao |
| 1993 | Cryptographic hardness of distribution-specific learning. | Michael Kharitonov |
| 1993 | Matchings in lattice graphs. | Claire Kenyon, Dana Randall, Alistair Sinclair |
| 1993 | Efficient noise-tolerant learning from statistical queries. | Michael J. Kearns |
| 1993 | Mapping the genome: some combinatorial problems arising in molecular biology. | Richard M. Karp |
| 1993 | An O~(n | David R. Karger, Clifford Stein |
| 1993 | Characterizing non-deterministic circuit size. | Mauricio Karchmer, Avi Wigderson |
| 1993 | Constant time factors do matter. | Neil D. Jones |
| 1993 | k one-way heads cannot do string-matching. | Tao Jiang, Ming Li |