| 2004 | Learning DNFs and Circuits Using Teaching Assistants. | N. V. Vinodchandran |
| 2004 | Computational Complexity Classification of Partition under Compaction and Retraction. | Narayan Vikas |
| 2004 | Computing Phylogenetic Roots with Bounded Degrees and Errors Is Hard. | Tatsuie Tsukiji, Zhi-Zhong Chen |
| 2004 | The Worst-Case Time Complexity for Generating All Maximal Cliques. | Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi |
| 2004 | A Faster Algorithm for the All-Pairs Shortest Path Problem and Its Application. | Tadao Takaoka |
| 2004 | Robust Geometric Computation Based on Digital Topology. | Kokichi Sugihara |
| 2004 | On the Complexity of Samples for Learning. | Joel Ratsaby |
| 2004 | Fault Hamiltonicity of Meshes with Two Wraparound Edges. | Kyoung-Wook Park, Hyeong-Seok Lim, Jung-Heum Park, Hee-Chul Kim |
| 2004 | One-to-Many Disjoint Path Covers in a Graph with Faulty Elements. | Jung-Heum Park |
| 2004 | Adjacency of Optimal Regions for Huffman Trees. | Kensuke Onishi |
| 2004 | The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups. | Gustav Nordh, Peter Jonsson |
| 2004 | On the Orthogonal Drawing of Outerplanar Graphs. | Kumiko Nomura, Satoshi Tayu, Shuichi Ueno |
| 2004 | Dynamic Storage Allocation and On-Line Colouring Interval Graphs. | N. S. Narayanaswamy |
| 2004 | On the Expected Time for Herman's Probabilistic Self-stabilizing Algorithm. | Toshio Nakata |
| 2004 | On the Power of One-Sided Error Quantum Pushdown Automata with Classical Stack Operations. | Masaki Nakanishi |
| 2004 | Some Open Problems in Decidability of Brick (Labelled Polyomino) Codes. | Malgorzata Moczurad, Wlodzimierz Moczurad |
| 2004 | Canonical Decomposition, Realizer, Schnyder Labeling and Orderly Spanning Trees of Plane Graphs. | Kazuyuki Miura, Machiko Azuma, Takao Nishizeki |
| 2004 | Towards Constructing Optimal Strip Move Sequences. | Meena Mahajan, Raghavan Rama, Vijayakumar Sundarrajan |
| 2004 | On the Selection and Assignment with Minimum Quantity Commitments. | Andrew Lim, Fan Wang, Zhou Xu |
| 2004 | k-Center Problems with Minimum Coverage. | Andrew Lim, Brian Rodrigues, Fan Wang, Zhou Xu |
| 2004 | Transshipment Through Crossdocks with Inventory and Time Windows. | Andrew Lim, Zhaowei Miao, Brian Rodrigues, Zhou Xu |
| 2004 | Minimizing Maximum Lateness on Identical Parallel Batch Processing Machines. | Shuguang Li, Guojun Li, Shaoqiang Zhang |
| 2004 | New Approximation Algorithms for Some Dynamic Storage Allocation Problems. | Shuai Cheng Li, Hon Wai Leong, Steven K. Quek |
| 2004 | An Efficient Online Algorithm for Square Detection. | Ho-fung Leung, Zeshan Peng, Hing-Fung Ting |
| 2004 | Large Triangles in the d-Dimensional Unit-Cube. | Hanno Lefmann |