| 2004 | On Partial Lifting and the Elliptic Curve Discrete Logarithm Problem. | Qi Cheng, Ming-Deh A. Huang |
| 2004 | Superimposing Voronoi Complexes for Shape Deformation. | Chao Chen, Ho-Lun Cheng |
| 2004 | On the Range Maximum-Sum Segment Query Problem. | Kuan-Yu Chen, Kun-Mao Chao |
| 2004 | An Efficient Exact Algorithm for the Minimum Ultrametric Tree Problem. | Hsin-Fu Chen, Maw-Shang Chang |
| 2004 | On-Line Windows Scheduling of Temporary Items. | Wun-Tat Chan, Prudence W. H. Wong |
| 2004 | Geometric Optimization Problems Over Sliding Windows. | Timothy M. Chan, Bashir S. Sadjad |
| 2004 | The Polymatroid Steiner Problems. | Gruia Calinescu, Alexander Zelikovsky |
| 2004 | Bounding the Payment of Approximate Truthful Mechanisms. | Gruia Calinescu |
| 2004 | Random Access to Advice Strings and Collapsing Results. | Jin-yi Cai, Osamu Watanabe |
| 2004 | Flexibility of Steiner Trees in Uniform Orientation Metrics. | Marcus Brazil, Pawel Winter, Martin Zachariasen |
| 2004 | Structural Similarity in Graphs (A Relaxation Approach for Role Assignment). | Ulrik Brandes, Jrgen Lerner |
| 2004 | Augmenting the Edge-Connectivity of a Spider Tree. | Davide Bil, Guido Proietti |
| 2004 | On Nash Equilibria for Multicast Transmissions in Ad-Hoc Wireless Networks. | Vittorio Bil, Michele Flammini, Giovanna Melideo, Luca Moscardelli |
| 2004 | Equipartitions of Measures by 2-Fans. | Sergey Bereg |
| 2004 | Efficient Algorithms for k Maximum Sums. | Fredrik Bengtsson, Jingsen Chen |
| 2004 | Poly-APX- and PTAS-Completeness in Standard and Differential Approximation. | Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos |
| 2004 | Structural Alignment of Two RNA Sequences with Lagrangian Relaxation. | Markus Bauer, Gunnar W. Klau |
| 2004 | Voronoi Diagrams with a Transportation Network on the Euclidean Plane. | Sang Won Bae, Kyung-Yong Chwa |
| 2004 | A Generalization of Magic Squares with Applications to Digital Halftoning. | Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. Nandy, Shinji Sasahara, Takeaki Uno |
| 2004 | Polyline Fitting of Planar Points Under Min-sum Criteria. | Boris Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama |
| 2004 | Multicriteria Global Minimum Cuts. | Amitai Armon, Uri Zwick |
| 2004 | Approximate Distance Oracles for Graphs with Dense Clusters. | Mattias Andersson, Joachim Gudmundsson, Christos Levcopoulos |
| 2004 | Generalized Function Matching. | Amihood Amir, Igor Nor |
| 2004 | On the Monotone Circuit Complexity of Quadratic Boolean Functions. | Kazuyuki Amano, Akira Maruoka |
| 2004 | Property-Preserving Data Reconstruction. | Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu |