| 1996 | Fast Separator Decomposition for Finite Element Meshes. | Shang-Hua Teng |
| 1996 | Two-Guarding a Rectilinear Polygon. | Xuehou Tan, Binhai Zhu |
| 1996 | Area-Efficient Algorithms for Upward Straight-Line Tree Drawings (Extended Abstract). | Chan-Su Shin, Sung Kwon Kim, Kyung-Yong Chwa |
| 1996 | Distributed Computing in Asynchronous Networks with Byzantine Edges. | Vasant Shanbhogue, Moti Yung |
| 1996 | Efficient Deterministic Algorithms for Embedding Graphs on Books. | Farhad Shahrokhi, Weiping Shi |
| 1996 | Three Systems for Shared Generation of Authenticators. | Reihaneh Safavi-Naini |
| 1996 | Rectangular Grid Drawings of Plane Graphs. | Md. Saidur Rahman, Shin-Ichi Nakano, Takao Nishizeki |
| 1996 | Superconnectivity for Minimal Multi-loop Networks. | Jixiang Meng |
| 1996 | Some Notes on the Nearest Neighbour Interchange Distance. | Ming Li, John Tromp, Louxin Zhang |
| 1996 | On Sparse Parity Chack Matrices (Extended Abstract). | Hanno Lefmann, Pavel Pudlk, Petr Savick |
| 1996 | Probabilistic Analysis of Local Search and NP-Completeness Result for Constraint Satisfaction (Extended Abstract). | Hoong Chuin Lau |
| 1996 | Efficient Generation of Elliptic Curve Cryptosystems. | Kwok-Yan Lam, San Ling, Lucas Chi Kwong Hui |
| 1996 | Approximating Latin Square Extensions. | Ravi Kumar, Alexander Russell, Ravi Sundaram |
| 1996 | The Inverse Satisfiability Problem. | Dimitris J. Kavvadias, Martha Sideri |
| 1996 | Sparse Suffix Trees. | Juha Krkkinen, Esko Ukkonen |
| 1996 | Wormhole Versus Deflection Routing: A Case Study on the Mesh. | Efstratios Karaivazoglou, Paul G. Spirakis, Vasilis Triantafilou |
| 1996 | Combinatorial and Geometric Approaches to Counting Problems on Linear Matroids, Graphic Arrangements, and Partial Orders. | Hiroshi Imai, Satoru Iwata, Kyoko Sekine, Kensyu Yoshida |
| 1996 | On the Complexity of Commutativity Analysis. | Oscar H. Ibarra, Pedro C. Diniz, Martin C. Rinard |
| 1996 | Steiner Problems on Directed Acyclic Graphs. | Tsan-sheng Hsu, Kuo-Hui Tsai, Da-Wei Wang, D. T. Lee |
| 1996 | Optimal Bi-Level Augmentation for Selectivity Enhancing Graph Connectivity with Applications. | Tsan-sheng Hsu, Ming-Yang Kao |
| 1996 | A Note on the Simulation of Exponential Threshold Weights. | Thomas Hofmeister |
| 1996 | The Join Can Lower Complexity. | Lane A. Hemaspaandra, Zhigen Jiang, Jrg Rothe, Osamu Watanabe |
| 1996 | Harmonic Analysis, Real Approximation, and the Communication Complexity of Boolean Functions (Preliminary Version). | Vince Grolmusz |
| 1996 | On the Difficulty of Designing Good Classifiers. | Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou |
| 1996 | Exact Learning of Subclasses of CDNF Formulas with Membership Queries. | Carlos Domingo |