"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


This is the official web site of the Algorithms and Complexity Laboratory (ACLab) of the Department of Computer Science at the University of the Philippines Diliman. ACLab was founded in 2007 by Henry N. Adorna, Professor of Computer Science.

ACLab regular members, (under)graduate students, and collaborators conduct investigations 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

2 Oct 2017

The following papers are presented during the 6th Asian Conference on Membrane Computing (ACMC2017) 21-25 September, 2017,  Chengdu, China
  1. R.T. de La Cruz, F.G.C. Cabarle, X. ZengArithmetic and Memory Module using Spiking Neural P Systems with Structural Plasticity
  2. J.P. Carandang, F.G.C. Cabarle, H. Adorna, N.H. Hernandez, M.A. Martinez-Del-AmorNondeterminism in Spiking Neural P Systems: Algorithms and Simulations.
  3. J.G Torres, K. Buno, F.G. Cabarle. Some Notes on Spiking Neural dP Systems.
  4.  H. Adorna, L. Pan and B. Song. On Distributed Solution to k-SAT on Membrane Computing

2 Oct 2017

The following papers are presented during the Workshop on Computation: Theory and Practice (WCTP2017), September 12--13, 2017, Osaka University Nakanoshima Center, Osaka, Japan
  1. G. Solano, G. BlinM. Raffinot, J. Caro. A Clique Finding Algorithm for the Approximate Gene Cluster Discovery Problem
  2. J. Clemente, J.P. Carandang, H. Adorna, J.E. Evangelista. PepSquad: A Tool for Finding Compact Structural Motifs from Peptides. 
  3. J. Aborot. An oracle design for Grover's quantum search algorithm in solving the exact string matching problem. 
  4. J.R. Basiloña, M.R.T. Gueco, J. Clemente, J. Malinao, R.A. Juayong, J.M. Yap, H. Adorna. A Polynomial-Time Algorithm for Computing the Translocation Syntenic Distance of Special Graphs. 
  5. I. Ordanel, H. Adorna, J. Clemente. Approximation of two simple variations of the Poset Cover Problem.

20 July 2017

The following submissions of the members of ACLab to 18th International Conference on Membrane Computing (CMC 18) to be held at University of Bradford, U.K. on 24-28 July 2017 are accepted for oral presentation. (Slide presentations of the papers can be found HERE.)

1. On Evolution-Communication P systems with Energy Having

Bounded and Unbounded Communication

(R. Juayong, N. Hernandez, F. Cabarle, K. Buño, H. Adorna)

2. A Simulation of Transition P Systems by Numerical P Systems

with Migrating Variables

(N. Hernandez, H. Adorna)

3. Communication Complexity of Distributed Tissue-like P

Systems for Solving SAT Problem

(K. Buño, H. Adorna, L. Pan, B. Song)

4. Deterministic Solutions to NP-Complete Problems

using Numerical P Systems with Lower Thresholds

(I. Macababayao, E. Amores, N. Hernandez, F. Cabarle)

5. Simulating Evolutional Symport/Antiport by Evolution-

Communication and vice versa in Tissue P Systems with

Parallel Communication

(H. Adorna, A. Alhazov, L. Pan, B. Song)

6. On Languages Generated by Spiking Neural P System with

Structural Plasticity

(T. dela Cruz, F. Cabarle, X. Zeng)


19 June 2017

ACLab is pleased to announce that Richelle Ann B. Juayong has completed all her requirements for the degree of Doctor of Philosophy in Computer Science. Rich will be receiving her doctorate from the College of Engineering, University of the Philippines Diliman (Department of Computer Science).


16 June 2017

The Algorithms and Complexity lab (in short, AClab) is celebrating Theory Days from 22 to 23 June 2017. The two main reasons for the celebration of the Theory Days (open to the general public) are to celebrate the 10th anniversary of AClab, and the 105th birthday of Alan Mathison Turing (the founder of computer science). Theory Days aim to celebrate both these reasons by providing invited lectures under the general theme of discrete mathematics and theoretical computer science.

More details regarding this celebration can be found at the Theory Days 2017 page.

29 May 2017

Details of a guest and public lecture last 27 February 2017:

"Showing the Correctness of Algorithms using
Machine Learning and Automated Reasoning."

Date: 27. February 2017 (Monday)

Time: 2pm to 4pm, 

Venue: Lecture Hall 
2/f UPAECH, Department of Computer Science, 
College of Eng'g.

Title: Showing the Correctness of Algorithms using
Machine Learning and Automated Reasoning

Dr. Cezary Kaliszyk Uni. Innsbruck

With the increasing complexity of software and hardware, showing the correctness and security of the involved algorithms becomes more and more important. Highest levels of certainty about such properties can today be achieved using formal proof methods. In this talk I will introduce formal proof and discuss the main challenges the field faces presently. The most powerful techniques today combine machine learning with automated reasoning. I will introduce the various machine learning problems including the selection of relevant knowledge, choice of reasoning techniques, and generation of intermediate statements, as well as discuss the currently used algorithms and their relation to reasoning. 

Bio: Cezary Kaliszyk is a researcher at the University of Innsbruck, Austria. His main interests are providing proof advice and automation for formal proof. He received a MSc from the University of Warsaw, Poland in 2005, and a PhD in computer science in 2009, from the Radboud University, Netherlands. He spent a year at the Technical University of Munich working with nominal logic in the Isabelle proof assistant, two years at the University of Tsukuba, and has been working in the Computational Logic group in Innsbruck, Austria since 2012. He has been a recipient of grants from the European Research Council, Austrian Science Fund, Japan Society for the Promotion of Science, Austrian Agency for International Cooperation. His industry experience includes working at Google Research as a faculty advisor.

11 April 2017

ACLab would like to congratulate regular member Jasmine Malinao for earning her doctorate from the Institute of Computer Graphics and Algorithms in the Vienna University of Technology. Jas underwent graduate study in the Doctoratsstudium der technischen Wissenschaften (Doctorate study in technical sciences) program of VUT.

Padayon at mabuhay!

"Ten years of Computer Science Theory at UP Diliman" 
presented by Henry N. Adorna during Theory Days 2017.