| 1996 | The Complexity of Probabilistic versus Deterministic Finite Automata. | Andris Ambainis |
| 1996 | StUSPACE(log n) <= DSPACE(log²n / log log n). | Eric Allender, Klaus-Jrn Lange |
| 1995 | Algorithms for Finding f-Colorings of Partial k-Trees. | Xiao Zhou, Takao Nishizeki |
| 1995 | Deciding Bisimulation and Trace Equivalences for Systems with Many Identical Processes. | Hsu-Chun Yen, Shi-Tsuen Jian, Ta-Pang Lao |
| 1995 | Learning of Restricted RNLC Graph Languages. | Sei'ichi Tani, Koichi Yamazaki |
| 1995 | An Approximation Algorithm for Alphabet Indexing Problem. | Shinichi Shimozono |
| 1995 | Fast Approximate Dictionary Matching. | Fei Shi |
| 1995 | Computing the Tutte Polynomial of a Graph of Moderate Size. | Kyoko Sekine, Hiroshi Imai, Seiichiro Tani |
| 1995 | On the Complexity of Testing for Catastrophic Faults. | Nicola Santoro, Jiajun Ren, Amiya Nayak |
| 1995 | Should Amdahl's Law Be Repealed? (Abstract). | Franco P. Preparata |
| 1995 | Optimal Information Delivery. | Christos H. Papadimitriou, Srinivas Ramanathan, P. Venkat Rangan |
| 1995 | An Approximation Algorithm for MAX 3-SAT. | Takao Ono, Tomio Hirata, Takao Asano |
| 1995 | Algorithmic Problems Arising from Genome Informatics (Abstract). | Satoru Miyano |
| 1995 | A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions. | Kazuhisa Makino, Toshihide Ibaraki |
| 1995 | Logspace Verifiers, NC, and NP. | Satyanarayana V. Lokam, Meena Mahajan, V. Vinay |
| 1995 | Scheduling Parallel Tasks with Individual Deadlines. | Oh-Heum Kwon, Kyung-Yong Chwa |
| 1995 | Finding a Shortest Pair of Paths on the Plane with Obstacles and Crossing Areas. | Yoshiyuki Kusakari, Hitoshi Suzuki, Takao Nishizeki |
| 1995 | The First Subquadratic Algorithm for Complete Linkage Clustering. | Drago Krznaric, Christos Levcopoulos |
| 1995 | A Fast and Space - Economical Algorithm for Length - Limited Coding. | Jyrki Katajainen, Alistair Moffat, Andrew Turpin |
| 1995 | Structure in Average Case Complexity. | Christoph Karg, Rainer Schuler |
| 1995 | Spanning Closed Trail and Hamiltonian Cycle in Grid Graphs. | Cho Hwan-Gue, Alexander Zelikovsky |
| 1995 | A Linear Time Algorithm For Finding Maximal Planar Subgraphs. | Wen-Lian Hsu |
| 1995 | Undirected Vertex-Connectivity Structure and Smallest Four-Vertex-Connectivity Augmentation. | Tsan-sheng Hsu |
| 1995 | A Hard Problem That is Almost Always Easy. | George Havas, Bohdan S. Majewski |
| 1995 | Embeddings of Hyper-Rings in Hypercubes. | Yukihiro Hamada, Aohan Mei, Yasuaki Nishitani, Yoshihide Igarashi |