| 1996 | Improved Length Lower Bounds for Reflecting Sequences. | H. K. Dai, Kevin E. Flannery |
| 1996 | Improved Non-approximability Results for Vertex Cover with Density Constraints. | Andrea E. F. Clementi, Luca Trevisan |
| 1996 | Weight Biased Leftist Trees and Modified Skip Lists. | Seonghun Cho, Sartaj Sahni |
| 1996 | Finding a Hidden Code by Asking Questions. | Zhixiang Chen, Carlos Cunha, Steven Homer |
| 1996 | Finding Large Planar Subgraphs and Large Subgraphs of a Given Genus. | Gruia Calinescu, Cristina G. Fernandes |
| 1996 | Reduction Algorithms for Constructing Solutions in Graphs with Small Treewidth. | Hans L. Bodlaender, Babette de Fluiter |
| 1996 | Reductions and Convergence Rates of Average Time. | Jay Belanger, Jie Wang |
| 1996 | Output-Sensitive Reporting of Disjoint Paths (Extended Abstract). | Giuseppe Di Battista, Roberto Tamassia, Luca Vismara |
| 1996 | A Note on the Self-Witnessing Property of Computational Problems. | Vikraman Arvind |
| 1996 | Improved Bounds for On-line Load Balancing. | Matthew Andrews, Michel X. Goemans, Lisa Zhang |
| 1996 | A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy (Extended Abstract). | Eric Allender |
| 1996 | Approximating Minimum Keys and Optimal Substructure Screens. | Tatsuya Akutsu, Feng Bao |
| 1996 | Straight Skeletons for General Polygonal Figures in the Plane. | Oswin Aichholzer, Franz Aurenhammer |
| 1995 | The Complexity of Mean Payoff Games. | Uri Zwick, Mike Paterson |
| 1995 | Simple Reduction of f-Colorings to Edge-Colorings. | Xiao Zhou, Takao Nishizeki |
| 1995 | An Asynchrolous Parallel Method for Linaer Systems. | You Zhaoyong, Wang Chuanglong |
| 1995 | Computing Infinite Relations Using Finite Expressions: A New Approach To The Safety Issue In Relational Databases. | Ruogu Zhang |
| 1995 | Scheduling Task-Tree with Additive Scales on Parallel / Distributed Machines. | Xiangdong Yu, Moti Yung |
| 1995 | Convexity of Minimal Total Dominating Functions in Graphs. | Bo Yu |
| 1995 | A Better Subgraph of the Minimum Weight Triangulation. | Bo-Ting Yang |
| 1995 | Pandiagonal Magic Squares. | Cheng-Xu Xu, Zhun-Wei Lu |
| 1995 | On a Kind of Sequence of Polynomials. | Zhang Xiangde |
| 1995 | Non-empty Cross-3-Intersection Theorems of Subsets. | Shiquan Wu |
| 1995 | Document Processing, Theory, and Practice (Abstract). | Derick Wood |
| 1995 | Computations with Finite Closure Systems and Implications. | Marcel Wild |