"When you want to build a ship, then do not drum the men together in order to procure wood, to give instructions or to distribute the work, but teach them longing for the wide endless sea." - A. de Saint-Exupery

Welcome!

This is the official web site of the Algorithms and Complexity Laboratory (ACLab) of the Department of Computer Science of the University of the Philippines Diliman. ACLab currently has 7 regular members, headed by Henry N. Adorna, Professor of Computer Science.

ACLab conducts research on a diverse range of topics, all anchored on a theoretical computer science perspective. Current active research areas include formal models, natural computing, algorithmics for hard problems, bioinformatics, and data analysis and visualization.

Recent News and Announcements

10 August 2015

Details on a lecture by Jhoirene Clemente:

Title: Online Algorithms and Advice Complexity

Abstract: Many real world problems arise in so-called online environments. In these environments, information arrives in a piecewise manner and decisions are needed to be made without incomplete information about the future. Problems arising in such environments are called online problems and algorithms solving these problems are called online algorithms. In contrast, problems with complete information of the input are called offline algorithms. Not knowing the whole input is a huge disadvantage for online problems and so optimality is not always guaranteed even for problems that are polynomial-time solvable in the offline setting. Some examples of online problems are the paging problem, the ski-rental problem, and the time-series search problem. Algorithms for these problems are analyzed using competitive ratio, which is the worst ratio between the cost of the online  algorithm with respect to the offline counterpart. In this lecture, we will provide an introduction to online algorithms and competitive analysis. We will also provide an overview of advice complexity, which is used to measure the minimum amount of information needed by an online algorithm to be optimal. We will provide in this lecture some interesting questions about the advice complexity of online algorithms.

Date: 27 August, 2015

Time: 16:30h - 17:30h, GMT+8

Venue: Room 317

This lecture is open the public.

ACLab cover photo by Jhoirene Clemente

Recent Publications

  1. F.G.C. Cabarle, H.N. Adorna,  M.J. Perez-Jimenez.:  Sequential Spiking Neural P Systems with Structural Plasticity Based on Max/Min Spike Number. Neural Computing and Applications. http://dx.doi.org/10.1007/s00521-015-1937-5 (2015) [jour/SCI/ISI/2013 IF: 1.763] 
  2. F.G.C. Cabarle, H.N. Adorna,  M.J. Perez-Jimenez.: Asynchronous Spiking Neural P Systems with Structural Plasticity. (accepted, full paper) 14th International Conference on Unconventional and Natural Computation (UCNC), 31 Aug - 04 Sep, 2015, Auckland, New Zealand.
  3. F.G.C. Cabarle, H.N. Adorna,  M.J. Perez-Jimenez, T. Song.: Spiking Neural P Systems with Structural Plasticity. Neural Computing and Applications. http://dx.doi.org/10.1007/s00521-015-1857-4 (2015) [jour/SCI/ISI/2013 IF: 1.763]
  4. R.A.B. Juayong, H.N. Adorna: Relating Computations in Non-cooperative Transition P Systems and Evolution-Communication P Systems with Energy. Fundamenta Informaticae vol. 136(3) pp. 209-217 (2015) [jour/SCI/ISI/2013 IF: 0.479]