| 1993 | A deterministic algorithm for the three-dimensional diameter problem. Jirí Matousek, Otfried Schwarzkopf |
| 1993 | A linear time algorithm for finding tree-decompositions of small treewidth. Hans L. Bodlaender |
| 1993 | A parallel approximation algorithm for positive linear programming. Michael Luby, Noam Nisan |
| 1993 | A primal-dual approximation algorithm for generalized Steiner network problems. David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani |
| 1993 | A robust model for finding optimal evolutionary trees. Martin Farach, Sampath Kannan, Tandy J. Warnow |
| 1993 | A theory of parameterized pattern matching: algorithms and applications. Brenda S. Baker |
| 1993 | An O~(n David R. Karger, Clifford Stein |
| 1993 | Angles of planar triangular graphs. Giuseppe Di Battista, Luca Vismara |
| 1993 | Approximate load balancing on dynamic and asynchronous networks. William Aiello, Baruch Awerbuch, Bruce M. Maggs, Satish Rao |
| 1993 | Approximate max-flow min-(multi)cut theorems and their applications. Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis |
| 1993 | Asynchronous secure computation. Michael Ben-Or, Ran Canetti, Oded Goldreich |
| 1993 | Bounds for the computational power and learning complexity of analog neural nets. Wolfgang Maass |
| 1993 | Characterizing non-deterministic circuit size. Mauricio Karchmer, Avi Wigderson |
| 1993 | Checking approximate computations over the reals. Sigal Ar, Manuel Blum, Bruno Codenotti, Peter Gemmell |
| 1993 | Comparison-based search in the presence of errors. Ryan S. Borgstrom, S. Rao Kosaraju |
| 1993 | Competitive distributed file allocation. Baruch Awerbuch, Yair Bartal, Amos Fiat |
| 1993 | Constant time factors do matter. Neil D. Jones |
| 1993 | Constructing small sample spaces satisfying given constraints. Daphne Koller, Nimrod Megiddo |
| 1993 | Contention in shared memory algorithms. Cynthia Dwork, Maurice Herlihy, Orli Waarts |
| 1993 | Counting curves and their projections. Joachim von zur Gathen, Marek Karpinski, Igor E. Shparlinski |
| 1993 | Cryptographic defense against traffic analysis. Charles Rackoff, Daniel R. Simon |
| 1993 | Cryptographic hardness of distribution-specific learning. Michael Kharitonov |
| 1993 | Decision trees: old and new results. Rudolf Fleischer |
| 1993 | Depth reduction for noncommutative arithmetic circuits. Eric Allender, Jia Jiao |
| 1993 | Deterministic coding for interactive communication. Leonard J. Schulman |
| 1993 | Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman |
| 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 | Efficient noise-tolerant learning from statistical queries. Michael J. Kearns |
| 1993 | Efficient probabilistically checkable proofs and applications to approximations. Mihir Bellare, Shafi Goldwasser, Carsten Lund, Alexander Russell |
| 1993 | Excluded minors, network decomposition, and multicommodity flow. Philip N. Klein, Serge A. Plotkin, Satish Rao |
| 1993 | Expanders that beat the eigenvalue bound: explicit construction and applications. Avi Wigderson, David Zuckerman |
| 1993 | Fast asynchronous Byzantine agreement with optimal resilience. Ran Canetti, Tal Rabin |
| 1993 | Fast perfection-information leader-election protocol with linear immunity. Jason Cooper, Nathan Linial |
| 1993 | Finding minimum-quotient cuts in planar graphs. James K. Park, Cynthia A. Phillips |
| 1993 | Finiteness results for sigmoidal "neural" networks. Angus Macintyre, Eduardo D. Sontag |
| 1993 | Fully polynomial Byzantine agreement in t+1 rounds. Juan A. Garay, Yoram Moses |
| 1993 | Generalized FLP impossibility result for t-resilient asynchronous computations. Elizabeth Borowsky, Eli Gafni |
| 1993 | How much can hardware help routing? Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal |
| 1993 | How to use expert advice. Nicolò Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, Manfred K. Warmuth |
| 1993 | Improved bounds on the max-flow min-cut ratio for multicommodity flows. Serge A. Plotkin, Éva Tardos |
| 1993 | Improved bounds on weak epsilon-nets for convex sets. Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, Micha Sharir, Emo Welzl |
| 1993 | Linear programming without the matrix. Christos H. Papadimitriou, Mihalis Yannakakis |
| 1993 | Locality based graph coloring. Mario Szegedy, Sundar Vishwanathan |
| 1993 | Lower bounds for randomized mutual exclusion. Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman |
| 1993 | Many birds with one stone: multi-objective approximation algorithms. R. Ravi, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Harry B. Hunt III |
| 1993 | Mapping the genome: some combinatorial problems arising in molecular biology. Richard M. Karp |
| 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 | Matchings in lattice graphs. Claire Kenyon, Dana Randall, Alistair Sinclair |
| 1993 | Matrix searching with the shortest path metric. John Hershberger, Subhash Suri |
| 1993 | Maximum k-chains in planar point sets: combinatorial structure and algorithms. Stefan Felsner, Lorenz Wernisch |
| 1993 | Modified ranks of tensors and the size of circuits. Pavel Pudlák, Vojtech Rödl |
| 1993 | Monotone monadic SNP and constraint satisfaction. Tomás Feder, Moshe Y. Vardi |
| 1993 | More deterministic simulation in logspace. Noam Nisan, David Zuckerman |
| 1993 | Multi-scale self-simulation: a technique for reconfiguring arrays with faults. Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman |
| 1993 | Multiple matching of rectangular patterns. Ramana M. Idury, Alejandro A. Schäffer |
| 1993 | On the generation of multivariate polynomials which are hard to factor. Adi Shamir |
| 1993 | On the hardness of approximating minimization problems. Carsten Lund, Mihalis Yannakakis |
| 1993 | On-line algorithms for cache sharing. Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan |
| 1993 | On-line load balancing with applications to machine scheduling and virtual circuit routing. James Aspnes, Yossi Azar, Amos Fiat, Serge A. Plotkin, Orli Waarts |
| 1993 | Online load balancing and network flow. Steven J. Phillips, Jeffery R. Westbrook |
| 1993 | Optimal online scheduling of parallel jobs with dependencies. Anja Feldmann, Ming-Yang Kao, Jirí Sgall, Shang-Hua Teng |
| 1993 | Parametric real-time reasoning. Rajeev Alur, Thomas A. Henzinger, Moshe Y. Vardi |
| 1993 | Piecewise linear paths among convex obstacles. Mark de Berg, Jirí Matousek, Otfried Schwarzkopf |
| 1993 | Polynomial space polynomial delay algorithms for listing families of graphs. Leslie Ann Goldberg |
| 1993 | Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions. Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor |
| 1993 | Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA S. Rao Kosaraju, David S. Johnson, Alok Aggarwal |
| 1993 | Proportionate progress: a notion of fairness in resource allocation. Sanjoy K. Baruah, N. K. Cohen, C. Greg Plaxton, Donald A. Varvel |
| 1993 | Quantum complexity theory. Ethan Bernstein, Umesh V. Vazirani |
| 1993 | Randomness-optimal unique element isolation, with applications to perfect matching and related problems. Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan |
| 1993 | Reinventing the wheel: an optimal data structure for connectivity queries. Robert F. Cohen, Giuseppe Di Battista, Arkady Kanevsky, Roberto Tamassia |
| 1993 | Routing permutations on graphs via matchings. Noga Alon, Fan R. K. Chung, Ronald L. Graham |
| 1993 | Self-routing superconcentrators. Nicholas Pippenger |
| 1993 | Separator based sparsification for dynamic planar graph algorithms. David Eppstein, Zvi Galil, Giuseppe F. Italiano, Thomas H. Spencer |
| 1993 | Short random walks on graphs. Greg Barnes, Uriel Feige |
| 1993 | Simulating threshold circuits by majority circuits. Mikael Goldmann, Marek Karpinski |
| 1993 | Size-depth trade-offs for threshold circuits. Russell Impagliazzo, Ramamohan Paturi, Michael E. Saks |
| 1993 | Some complexity issues on the simply connected regions of the two-dimensional plane. Arthur W. Chou, Ker-I Ko |
| 1993 | Space-efficient scheduling of multithreaded computations. Robert D. Blumofe, Charles E. Leiserson |
| 1993 | The asynchronous computability theorem for t-resilient tasks. Maurice Herlihy, Nir Shavit |
| 1993 | The biased coin problem. Ravi B. Boppana, Babu O. Narayanan |
| 1993 | The network inhibition problem. Cynthia A. Phillips |
| 1993 | Thermodynamics of computation and information distance. Charles H. Bennett, Péter Gács, Ming Li, Paul M. B. Vitányi, Wojciech H. Zurek |
| 1993 | Time optimal self-stabilizing synchronization. Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, George Varghese |
| 1993 | Time-space trade-offs for undirected st-connectivity on a JAG. Jeff Edmonds |
| 1993 | Wait-free k-set agreement is impossible: the topology of public knowledge. Michael E. Saks, Fotios Zaharoglou |
| 1993 | What can be computed locally? Moni Naor, Larry J. Stockmeyer |
| 1993 | k one-way heads cannot do string-matching. Tao Jiang, Ming Li |