| 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 | Geometric Discrepancy Revisited | Bernard Chazelle |
| 1993 | A Tight Lower Bound for k-Set Agreement | Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, Mark R. Tuttle |
| 1993 | Sensitive Functions and Approximate Problems | Shiva Chaudhuri |
| 1993 | On Bounded Queries and Approximation | Richard Chang, William I. Gasarch |
| 1993 | Optimal Parallel All-Nearest-Neighbors Using the Well-Separated Pair Decomposition (Preliminary Version) | Paul B. Callahan |
| 1993 | Exact Learning via the Monotone Theory (Extended Abstract) | Nader H. Bshouty |
| 1993 | Product Range Spaces, Sensitive Sampling, and Derandomization | Herv Brnnimann, Bernard Chazelle, Jir Matousek |
| 1993 | A Quantum Bit Commitment Scheme Provably Unbreakable by both Parties | Gilles Brassard, Claude Crpeau, Richard Jozsa, Denis Langlois |
| 1993 | Learning an Intersection of k Halfspaces over a Uniform Distribution | Avrim Blum, Ravi Kannan |
| 1993 | An On-Line Algorithm for Improving Performance in Navigation | Avrim Blum, Prasad Chalasani |
| 1993 | When can we sort in o(n log n) time? | Amir M. Ben-Amram, Zvi Galil |
| 1993 | Las Vegas algorithms for matrix groups | Robert Beals, Lszl Babai |
| 1993 | A Polynomial Time Algorithm for Counting Integral Points in Polyhedra when the Dimension Is Fixed | Alexander I. Barvinok |
| 1993 | Time-Space Bounds for Directed s-t Connectivity on JAG Models (Extended Abstract) | Greg Barnes, Jeff Edmonds |
| 1993 | Genome Rearrangements and Sorting by Reversals | Vineet Bafna, Pavel A. Pevzner |
| 1993 | A Simple Local-Control Approximation Algorithm for Multicommodity Flow | Baruch Awerbuch, Frank Thomson Leighton |
| 1993 | Heat & Dump: Competitive Distributed Paging | Baruch Awerbuch, Yair Bartal, Amos Fiat |
| 1993 | Near-Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers | Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg |
| 1993 | Throughput-Competitive On-Line Routing | Baruch Awerbuch, Yossi Azar, Serge A. Plotkin |
| 1993 | Highly Efficient Asynchronous Execution of Large-Grained Parallel Programs | Yonatan Aumann, Zvi M. Kedem, Krishna V. Palem, Michael O. Rabin |
| 1993 | General Bounds on Statistical Query Learning and PAC Learning with Noise via Hypothesis Bounding | Javed A. Aslam, Scott E. Decatur |
| 1993 | The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations | Sanjeev Arora, Lszl Babai, Jacques Stern, Z. Sweedyk |
| 1993 | The Union of Convex Polyhedra in Three Dimensions | Boris Aronov, Micha Sharir |
| 1993 | Scale-sensitive Dimensions, Uniform Convergence, and Learnability | Noga Alon, Shai Ben-David, Nicol Cesa-Bianchi, David Haussler |