| 2005 | A Better Approximation Ratio for the Vertex Cover Problem. George Karakostas |
| 2005 | A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines. Martin Gairing, Burkhard Monien, Andreas Woclaw |
| 2005 | A Finite Basis for Failure Semantics. Wan J. Fokkink, Sumit Nain |
| 2005 | A Fully Abstract Encoding of the Michael Baldamus, Joachim Parrow, Björn Victor |
| 2005 | A Gentle Introduction to Semantic Subtyping. Giuseppe Castagna, Alain Frisch |
| 2005 | A Quantum Lower Bound for the Query Complexity of Simon's Problem. Pascal Koiran, Vincent Nesme, Natacha Portier |
| 2005 | A Tight Linear Bound on the Neighborhood of Inverse Cellular Automata. Eugen Czeizler, Jarkko Kari |
| 2005 | About Hoare Logics for Higher-Order Store. Bernhard Reus, Thomas Streicher |
| 2005 | All Quantum Adversary Methods Are Equivalent. Robert Spalek, Mario Szegedy |
| 2005 | An Accessible Approach to Behavioural Pseudometrics. Franck van Breugel, Claudio Hermida, Michael Makkai, James Worrell |
| 2005 | An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks. Christoph Ambühl |
| 2005 | An Õ( Telikepalli Kavitha |
| 2005 | Append-Only Signatures. Eike Kiltz, Anton Mityagin, Saurabh Panjwani, Barath Raghavan |
| 2005 | Approximate Guarding of Monotone and Rectilinear Polygons. Bengt J. Nilsson |
| 2005 | Approximating - Outperforming a Random Assignment with Almost a Linear Factor. Gustav Hast |
| 2005 | Approximation Algorithms for Euclidean Group TSP. Khaled M. Elbassioni, Aleksei V. Fishkin, Nabil H. Mustafa, René Sitters |
| 2005 | Approximation Algorithms for the Max-coloring Problem. Sriram V. Pemmaraju, Rajiv Raman |
| 2005 | Asynchronous Perfectly Secure Communication over One-Time Pads. Giovanni Di Crescenzo, Aggelos Kiayias |
| 2005 | Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, Moti Yung |
| 2005 | Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins. Martin Dietzfelbinger, Christoph Weidling |
| 2005 | Basic Observables for a Calculus for Global Computing. Rocco De Nicola, Daniele Gorla, Rosario Pugliese |
| 2005 | Basing Cryptographic Protocols on Tamper-Evident Seals. Tal Moran, Moni Naor |
| 2005 | Boneh-Franklin Identity Based Encryption Revisited. David Galindo |
| 2005 | Bounds on the Efficiency of "Black-Box" Commitment Schemes. Omer Horvitz, Jonathan Katz |
| 2005 | Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability. Henry C. Lin, Tim Roughgarden, Éva Tardos, Asher Walkover |
| 2005 | Cache-Aware and Cache-Oblivious Adaptive Sorting. Gerth Stølting Brodal, Rolf Fagerberg, Gabriel Moruz |
| 2005 | Cache-Oblivious Planar Shortest Paths. Hema Jampala, Norbert Zeh |
| 2005 | Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties. An Braeken, Yuri L. Borissov, Svetla Nikova, Bart Preneel |
| 2005 | Combining Intruder Theories. Yannick Chevalier, Michaël Rusinowitch |
| 2005 | Completely Non-malleable Schemes. Marc Fischlin |
| 2005 | Compositional Verification of Asynchronous Processes via Constraint Solving. Giorgio Delzanno, Maurizio Gabbrielli |
| 2005 | Computational Bounds on Hierarchical Data Processing with Applications to Information Security. Roberto Tamassia, Nikos Triandopoulos |
| 2005 | Computationally Sound Implementations of Equational Theories Against Passive Adversaries. Mathieu Baudet, Véronique Cortier, Steve Kremer |
| 2005 | Concurrent Zero Knowledge in the Public-Key Model. Giovanni Di Crescenzo, Ivan Visconti |
| 2005 | Congruences for Visibly Pushdown Languages. Rajeev Alur, Viraj Kumar, P. Madhusudan, Mahesh Viswanathan |
| 2005 | Decidability and Complexity Results for Timed Automata via Channel Machines. Parosh Aziz Abdulla, Johann Deneux, Joël Ouaknine, James Worrell |
| 2005 | Decidability in Syntactic Control of Interference. James Laird |
| 2005 | Designated Verifier Signature Schemes: Attacks, New Security Notions and a New Construction. Helger Lipmaa, Guilin Wang, Feng Bao |
| 2005 | Deterministic Constructions of Approximate Distance Oracles and Spanners. Liam Roditty, Mikkel Thorup, Uri Zwick |
| 2005 | Discrete Random Variables over Domains. Michael W. Mislove |
| 2005 | Distance Constrained Labelings of Graphs of Bounded Treewidth. Jirí Fiala, Petr A. Golovach, Jan Kratochvíl |
| 2005 | Dynamic Bin Packing of Unit Fractions Items. Wun-Tat Chan, Tak Wah Lam, Prudence W. H. Wong |
| 2005 | Dynamic Diffusion Load Balancing. Petra Berenbrink, Tom Friedetzky, Russell A. Martin |
| 2005 | Facility Location in Sublinear Time. Mihai Badoiu, Artur Czumaj, Piotr Indyk, Christian Sohler |
| 2005 | Fast Neighbor Joining. Isaac Elias, Jens Lagergren |
| 2005 | From Primal-Dual to Cost Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem. Jochen Könemann, Stefano Leonardi, Guido Schäfer, Stefan H. M. van Zwam |
| 2005 | Groupoids That Recognize Only Regular Languages. Martin Beaudry, François Lemieux, Denis Thérien |
| 2005 | Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity. Jeff Ford, Anna Gál |
| 2005 | Hierarchical Group Signatures. Mårten Trolin, Douglas Wikström |
| 2005 | Holographic Circuits. Leslie G. Valiant |
| 2005 | How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. Allan Borodin, David Cashman, Avner Magen |
| 2005 | Hybrid Trapdoor Commitments and Their Applications. Dario Catalano, Ivan Visconti |
| 2005 | Idealized Algol with Ground Recursion, and DPDA Equivalence. Andrzej S. Murawski, C.-H. Luke Ong, Igor Walukiewicz |
| 2005 | Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval. Stephanie Wehner, Ronald de Wolf |
| 2005 | Influential Nodes in a Diffusion Model for Social Networks. David Kempe, Jon M. Kleinberg, Éva Tardos |
| 2005 | LCA Queries in Directed Acyclic Graphs. Miroslaw Kowaluk, Andrzej Lingas |
| 2005 | Label-Guided Graph Exploration by a Finite Automaton. Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, David Peleg |
| 2005 | Linear Time Algorithms for Clustering Problems in Any Dimensions. Amit Kumar, Yogish Sabharwal, Sandeep Sen |
| 2005 | Logics for Unranked Trees: An Overview. Leonid Libkin |
| 2005 | Lower Bounds for Circuits with Few Modular and Symmetric Gates. Arkadev Chattopadhyay, Kristoffer Arnsfelt Hansen |
| 2005 | Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. Paul Beame, Toniann Pitassi, Nathan Segerlind |
| 2005 | Measure and Conquer: Domination - A Case Study. Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch |
| 2005 | NFAs With and Without Juraj Hromkovic, Georg Schnitger |
| 2005 | Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture. Martin Gairing, Thomas Lücking, Burkhard Monien, Karsten Tiemann |
| 2005 | New Approaches for Virtual Private Network Design. Friedrich Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo, Martin Skutella |
| 2005 | Noisy Turing Machines. Eugene Asarin, Pieter Collins |
| 2005 | On Dynamic Bit-Probe Complexity. Corina E. Patrascu, Mihai Patrascu |
| 2005 | On Round-Efficient Argument Systems. Hoeteck Wee |
| 2005 | On Steganographic Chosen Covertext Security. Nicholas Hopper |
| 2005 | On the Douglas Wikström |
| 2005 | On the Cover Time of Random Geometric Graphs. Chen Avin, Gunes Ercal |
| 2005 | On the Equivalence of -Automata. Marie-Pierre Béal, Sylvain Lombardy, Jacques Sakarovitch |
| 2005 | On the Existence of Hamiltonian Cycles in Random Intersection Graphs. Charilaos Efthymiou, Paul G. Spirakis |
| 2005 | On the Hardness of Embeddings Between Two Finite Metrics. |
| 2005 | On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group. Jaikumar Radhakrishnan, Martin Rötteler, Pranab Sen |
| 2005 | On the Wake-Up Problem in Radio Networks. Bogdan S. Chlebus, Leszek Gasieniec, Dariusz R. Kowalski, Tomasz Radzik |
| 2005 | Online Interval Coloring and Variants. Leah Epstein, Meital Levy |
| 2005 | Optimal Branch-Decomposition of Planar Graphs in Qian-Ping Gu, Hisao Tamaki |
| 2005 | Optimal Cover Time for a Graph-Based Coupon Collector Process. Nedialko B. Dimitrov, C. Greg Plaxton |
| 2005 | Optimal In-place Sorting of Vectors and Records. Gianni Franceschini, Roberto Grossi |
| 2005 | Optimal Spaced Seeds for Faster Approximate String Matching. Martin Farach-Colton, Gad M. Landau, Süleyman Cenk Sahinalp, Dekel Tsur |
| 2005 | Optimistic Asynchronous Atomic Broadcast. Klaus Kursawe, Victor Shoup |
| 2005 | Orthogonal Extensions in Structural Operational Semantics. Mohammad Reza Mousavi, Michel A. Reniers |
| 2005 | Password-Based Encryption Analyzed. Martín Abadi, Bogdan Warinschi |
| 2005 | Petri Algebras. Éric Badouel, Jules Chenou, Goulven Guillou |
| 2005 | Polynomial Time Preemptive Sum-Multicoloring on Paths. Annamária Kovács |
| 2005 | Preservation Under Extensions on Well-Behaved Finite Structures. Albert Atserias, Anuj Dawar, Martin Grohe |
| 2005 | Probabilistic Polynomial-Time Semantics for a Protocol Security Logic. Anupam Datta, Ante Derek, John C. Mitchell, Vitaly Shmatikov, Mathieu Turuani |
| 2005 | Quantum Complexity of Testing Group Commutativity. Frédéric Magniez, Ashwin Nayak |
| 2005 | Randomized Fast Design of Short DNA Words. Ming-Yang Kao, Manan Sanghi, Robert T. Schweller |
| 2005 | Recursive Markov Decision Processes and Recursive Stochastic Games. Kousha Etessami, Mihalis Yannakakis |
| 2005 | Reordering Buffer Management for Non-uniform Cost Models. Matthias Englert, Matthias Westermann |
| 2005 | Replacement Paths and Liam Roditty, Uri Zwick |
| 2005 | Restricted Two-Variable Sentences, Circuits and Communication Complexity. Pascal Tesson, Denis Thérien |
| 2005 | Semantic-Based Code Obfuscation by Abstract Interpretation. Mila Dalla Preda, Roberto Giacobazzi |
| 2005 | Signaling P Systems and Verification Problems. Cheng Li, Zhe Dang, Oscar H. Ibarra, Hsu-Chun Yen |
| 2005 | Simple Extractors via Constructions of Cryptographic Pseudo-random Generators. Marius Zimand |
| 2005 | Simulated Annealing Beats Metropolis in Combinatorial Optimization. Ingo Wegener |
| 2005 | Single-Database Private Information Retrieval with Constant Communication Rate. Craig Gentry, Zulfikar Ramzan |
| 2005 | Single-Key AIL-MACs from Any FIL-MAC. Ueli M. Maurer, Johan Sjödin |
| 2005 | Single-Prover Concurrent Zero Knowledge in Almost Constant Rounds. Giuseppe Persiano, Ivan Visconti |
| 2005 | Solvability of a System of Bivariate Polynomial Equations over a Finite Field. Neeraj Kayal |
| 2005 | Spatial Logics for Bigraphs. Giovanni Conforti, Damiano Macedonio, Vladimiro Sassone |
| 2005 | Stability and Similarity of Link Analysis Ranking Algorithms. Debora Donato, Stefano Leonardi, Panayiotis Tsaparas |
| 2005 | Stochastic Steiner Trees Without a Root. Anupam Gupta, Martin Pál |
| 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 | The Complexity of Stochastic Rabin and Streett Games'. Krishnendu Chatterjee, Luca de Alfaro, Thomas A. Henzinger |
| 2005 | The Efficiency and Fairness of a Fixed Budget Resource Allocation Game. Li Zhang |
| 2005 | The Generalized Deadlock Resolution Problem. Kamal Jain, Mohammad Taghi Hajiaghayi, Kunal Talwar |
| 2005 | The Polyranking Principle. Aaron R. Bradley, Zohar Manna, Henny B. Sipma |
| 2005 | The Tree Inclusion Problem: In Optimal Space and Faster. Philip Bille, Inge Li Gørtz |
| 2005 | Tight Lower Bounds for Query Processing on Streaming and External Memory Data. Martin Grohe, Christoph Koch, Nicole Schweikardt |
| 2005 | Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. Scott Diehl, Dieter van Melkebeek |
| 2005 | Towards Optimal Multiple Selection. Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, Peter Sanders |
| 2005 | Union-Find with Constant Time Deletions. Stephen Alstrup, Inge Li Gørtz, Theis Rauhe, Mikkel Thorup, Uri Zwick |
| 2005 | Unsafe Grammars and Panic Automata. Teodor Knapik, Damian Niwinski, Pawel Urzyczyn, Igor Walukiewicz |
| 2005 | Up-to Techniques for Weak Bisimulation. Damien Pous |
| 2005 | Weighted Automata and Weighted Logics. Manfred Droste, Paul Gastin |
| 2005 | Worst Case Optimal Union-Intersection Expression Evaluation. Ehsan Chiniforooshan, Arash Farzan, Mehdi Mirzazadeh |