ALBCOM: Research: Algorithms and Complexity
   ALBCOM: Algorithms, Bioinformatics, Complexity and Formal Methods
  Prizes & Distinctions
  In the media
  Former members
 Research: Algorithms and Complexity

ALBCOM has a strong and diverse group in Algorithms and Complexity Theory. The goals of the group are, broadly speaking, to provide a mathematical understanding of fundamental issues in Computer Science, and to use this understanding to produce better algorithms, protocols, and systems. Research interests include data structures, sequential and parallel algorithm design, complexity theory, combinatorics, dynamic networks, heuristics. Many members of the group . Many members of our group work also work in other areas of ALBCOM in other areas as well We welcome students who have a combination either of theoretical and application-oriented research interests. Prospective students should look into (web page)

Some of the topics which we are currently working on are:

Graph layout and isoperimetric problems

Layout of graphs with applications to circuit placement We are interested in the study of the complexity for graph layout and isoperimetric problems. in particular, we work on design, analytical and empirical evaluation of algorithms and heuristics for those problems. On the practical side, we are working into applying some of the previous ideas to find faster algorithms to partition of VLSI.

Participants: J. Daz, J. Petit, M. Serna

Circuit complexity and universal derandomization.

The so-called hardness vs. randomness tradeoff allowed the construction of good pseudorandom generators from hard Boolean functions of large circuit complexity. An implication is that the existence of explicit hard Boolean functions would imply universal efficient derandomization of probabilistic algorithms. Recent work has focussed in trying to establish some sort of converse with partial success: does universal derandomization entail the existence of explicit hard Boolean functions? We are interested in studying this question for several models of circuits and computational resources.

Participants: A. Atserias

Dynamic Networks

We are interested in modeling the formation and evolution of dynamic networks in different scenarios with the aim of performing an indepth study of their performance at an application level. In particular we work in the modelization of randomly deployed networks of sensors and networks forming over time by mobile agents. We expect to use, apart from simulation, probabilistic methods, analysis in adversarial situations and game theory to analyze the performance of the models in realistic settings.

Participants: C. lvarez, M. Blesa, J. Daz, X. Prez, J. Petit, M. Serna,

Parameterized complexity and exact algorithms

We are interested in finding whether a hard problems exhibits some kind of efficient algorithm, thus looking for exact and parameterized algorithms for them. For parameterized problems, efficiency means an FPT algorithm that solves the problem, so we look for natural problem parameters that might lead to such an algorithm. In particular we are interested in finding new algorithmic paradigms for the design of FPT algorithms for counting the number of solutions to parameterized problem. We are currently working in several parameterizations of layout and embedding problems. For hard problems, with an exponential time algorithm, efficiency is measured by the decrease of the constant in the base of the exponent. Apart for identifying further problems that allow this level of efficiency, we are interested in developping complexity tools that allows a finer classification of the problems with respect to this notion of efficiency.

Participants: J. Daz, M. Serna, D. Thilikos

Game theory

The fundamental question posed by Papadimitriou has initiated a line of research towards understanding the complexity of computing a pure or a mixed Nash equilibrium. We plan to anlyze, from a computational complexity point of view, several elementary notions of equilibria in games. We are also interested in the use of Game Theory as a tool to analyze the behaviour of selfish computational units that interact in a distributed scenario in close connection with network problems.

Participants: C. lvarez, M. Blesa, J. Gabarr, M. Serna.

Design and Analysis of Algorithms

This research area covers both design and analysis of algorithms, with the focus on algorithms and data structures for fundamental problems such as searching and sorting. Our main interest is in practical algorithms and data structures, developing well-engineered prototypes of our proposals to compare and to study their performance in practice, and in their precise mathematical analysis (average-case, probability distribution, ...). In the last years, there is also increasing interest in experimentation as a fundamental tool to explore new algorithmic ideas as well as a solid foundation for algorithm engineering practices.

Participants: A. Duch, C. Martinez, X. Molinero, J. Petit, S. Roura.

Approximate algorithms for tackling combinatorial optimization problems

Many relevant optimization problems arising in areas such as bioinformatics, logistics, engineering, and telecommunications can be modelled as combinatorial optimization problems. We are interested in approximate algorithms for tackling these problems. In contrast to complete methods, these algorithms do not guarantee to find an optimal solution. Instead they are used to provide "good enough" solutions in a reasonable amount of computation time. On the theoretical side, we try to learn more about the working of some particular algorithms. This is done with the aim of improving their applicability in practise. On the practical side, we develop applications to important combinatorial optimization problems arising, for example, in telecommunications. One of our particular interests is the metaheuristic ant colony optimization , which is inspired by the foraging behaviour of real ant colonies.

Participants: M. J. Blesa, C. Blum