| 2005 | A Better Approximation Ratio for the Vertex Cover Problem. | George Karakostas |
| 2005 | Randomized Fast Design of Short DNA Words. | Ming-Yang Kao, Manan Sanghi, Robert T. Schweller |
| 2005 | Towards Optimal Multiple Selection. | Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, Peter Sanders |
| 2005 | Cache-Oblivious Planar Shortest Paths. | Hema Jampala, Norbert Zeh |
| 2005 | The Generalized Deadlock Resolution Problem. | Kamal Jain, Mohammad Taghi Hajiaghayi, Kunal Talwar |
| 2005 | NFAs With and Without | Juraj Hromkovic, Georg Schnitger |
| 2005 | Bounds on the Efficiency of "Black-Box" Commitment Schemes. | Omer Horvitz, Jonathan Katz |
| 2005 | On Steganographic Chosen Covertext Security. | Nicholas Hopper |
| 2005 | Approximating - Outperforming a Random Assignment with Almost a Linear Factor. | Gustav Hast |
| 2005 | Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of Type | Mitsuhiro Haneda, Mitsuru Kawazoe, Tetsuya Takahashi |
| 2005 | Optimal Branch-Decomposition of Planar Graphs in | Qian-Ping Gu, Hisao Tamaki |
| 2005 | Stochastic Steiner Trees Without a Root. | Anupam Gupta, Martin Pl |
| 2005 | Tight Lower Bounds for Query Processing on Streaming and External Memory Data. | Martin Grohe, Christoph Koch, Nicole Schweikardt |
| 2005 | Single-Database Private Information Retrieval with Constant Communication Rate. | Craig Gentry, Zulfikar Ramzan |
| 2005 | Boneh-Franklin Identity Based Encryption Revisited. | David Galindo |
| 2005 | A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines. | Martin Gairing, Burkhard Monien, Andreas Woclaw |
| 2005 | Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture. | Martin Gairing, Thomas Lcking, Burkhard Monien, Karsten Tiemann |
| 2005 | Optimal In-place Sorting of Vectors and Records. | Gianni Franceschini, Roberto Grossi |
| 2005 | Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity. | Jeff Ford, Anna Gl |
| 2005 | Measure and Conquer: Domination - A Case Study. | Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch |
| 2005 | A Finite Basis for Failure Semantics. | Wan J. Fokkink, Sumit Nain |
| 2005 | Completely Non-malleable Schemes. | Marc Fischlin |
| 2005 | Distance Constrained Labelings of Graphs of Bounded Treewidth. | Jir Fiala, Petr A. Golovach, Jan Kratochvl |
| 2005 | Optimal Spaced Seeds for Faster Approximate String Matching. | Martin Farach-Colton, Gad M. Landau, Sleyman Cenk Sahinalp, Dekel Tsur |
| 2005 | Recursive Markov Decision Processes and Recursive Stochastic Games. | Kousha Etessami, Mihalis Yannakakis |