ALGORITHMS & COMPLEXITY LAB

"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."

— Antoine de Saint-Exupéry

Welcome!

This is the official website of the Algorithms and Complexity Laboratory (ACLab) of the Department of Computer Science at the University of the Philippines Diliman.

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: Algorithm Design, Efficient Data Structures, Nature-inspired Computation, Online Computation, Parallel Algorithms, Algorithmic Visual Simulators

Research Agenda:

1. Devise exact, approximation, and parameterized algorithms, as well as heuristics, for solving intractable problems.
2. Investigate and develop novel competitive algorithms for online computation that achieve optimal or near-optimal competitive ratios.
3. Explore unconventional and nature-inspired algorithms, such as evolutionary algorithms, membrane computing, and quantum computing, for solving computationally hard problems.
4. Develop efficient data structures tailored for the unique challenges in bioinformatics, such as handling large-scale genomic data, molecular structures, and biological networks.
5. Design parallel algorithms and optimize data storage management to efficiently utilize Graphics Processing Units (GPUs) and other parallel computing architectures.
6. Create visual simulators for algorithmic games and computational systems.

A special interest group focusing on Parallelism and Concurrency has the following research agenda.

Investigate fundamental problems of parallel or concurrent computing, such as topology, scheduling, speedup, efficiency, scalability, reconfigurability, communication, and reversibility;
Research on the interplay, and frontiers, between serial/sequential computing, and parallel or concurrent computing;
Develop tools, including visual ones, to design, reason, or analyze parallel computations;
Investigate new forms of parallelization or concurrency, including emergent properties or phenomena, cooperation, interaction, nature, or bio-inspired paradigms;
Explore ways to improve the pedagogy of parallel and computational thinking and their philosophical or societal impact;

Recent Publications

Ivy Ordanel, Proceso Fernandez Jr., Richelle Ann Juayong, Jhoirene Clemente, and Henry Adorna, Parameterized Algorithm for the Poset Cover Problem, Philippine Journal of Science, Vol. 153 No. 1, February 2024
Willie Jr N. Coronel, Joshua Relucio, Ivy D. Ordanel and Richelle Ann B. Juayong, Two Heuristics for the Tree Poset Cover Problem, In Proceedings of the Workshop on Computation Theory and Practice 2023 (WCTP 2023), December 4-6, 2023, Hokkaido Japan
Jhoirene Clemente, Richelle Ann Juayong and Ivy Ordanel, Some Weighted Clique Minimization Problems and their Approximability Properties, Geoffrey Solano, In Proceedings of the Workshop on Computation Theory and Practice 2023 (WCTP 2023), December 4-6, 2023, Hokkaido Japan
Clarence Gabriel Kasilag, Pollux Rey and Jhoirene Clemente, Empirical Competitive Analysis for the Online Assignment Problem with ML Predictions, In Proceedings of the Workshop on Computation Theory and Practice 2023 (WCTP 2023), December 4-6, 2023, Hokkaido Japan
Derryn Joi O. Martirez, Raphael Justin C. Portuguez and Jhoirene B. Clemente, Parallel Polynomial Time Approximation Scheme (PTAS) for the Closest Substring Problem, In Proceedings of the Workshop on Computation Theory and Practice 2023 (WCTP 2023), December 4-6, 2023, Hokkaido Japan
Jan Apolline Estrella, Christian Quinzon, Francis George Cabarle and Jhoirene Clemente, More Attention to COVID-19: Investigation of State-Of-The-Art Transformer PEGASUS-X Hyperparameters for Abstractive Summarization of COVID-19 Research, In Proceedings of the Workshop on Computation Theory and Practice 2023 (WCTP 2023), December 4-6, 2023, Hokkaido Japan
Julia Pineda, Andrew Sopungco and Jhoirene Clemente, Design and Implementation of a Parallel PTAS for Finding Structural Motifs on Graphics Processing Units (GPUs), In Proceedings of the Workshop on Computation Theory and Practice 2023 (WCTP 2023), December 4-6, 2023, Hokkaido Japan
Louie Gallos, Jose Lorenzo Sotto, Francis George Cabarle and Henry Adorna, WebSnapse v3: Optimization of the Web-based Simulator of Spiking Neural P System using Matrix Representation, WebAssembly and other tools, In Proceedings of the Workshop on Computation Theory and Practice 2023 (WCTP 2023), December 4-6, 2023, Hokkaido Japan
Mutya Gulapa, Jarred Luzada, Francis George Cabarle, Henry Adorna and Daryll Ko, WebSnapse Reloaded: The Next-Generation Spiking Neural P System Visual Simulator using Client-Server Architecture, In Proceedings of the Workshop on Computation Theory and Practice 2023 (WCTP 2023), December 4-6, 2023, Hokkaido Japan
Brocka B., Yap S., Clemente J., Parallel Polynomial-Time Approximation Scheme (PTAS) for Finding Compact Structural Motifs, Accepted for paper presentation to 2023 10th International Conference on Biomedical and Bioinformatics Engineering (ICBBE 2023) to be held onsite in Ritsumeikan University, Kyoto, Japan on November 9-12, 2023
Estrella JA., Quinzon C., Cabarle, FG., Clemente, J., Attention to COVID-19: Abstractive Summarization of COVID-19 Research with State-Of-The-Art Transformers, Accepted for paper presentation to 2023 IEEE Region 10 Conference (TENCON) to be held onsite in Chiang Mai, Thailand on 31 October - 3 November 2023 [https://doi.org/10.1109/TENCON58879.2023.10322357]
Ayla Nikki Lorreen Odasco, Matthew Lemuel Rey, Francis George Cabarle et al. Improving GPU Web Simulations of Spiking Neural P Systems, 02 March 2023, PREPRINT (Version 1) available at Research Square [https://doi.org/10.21203/rs.3.rs-2640951/v1]
Cabarle F. et al. (2023). GPU simulations of spiking neural p systems on modern web browsers. Natural Computing. Volume 22, 171-180. https://doi.org/10.1007/s11047-022-09914-1
Buño, K. C., & Adorna, H. (2023). Solving 3-SAT in distributed P systems with string objects. Theoretical Computer Science, 964, 113976. https://doi.org/10.1016/j.tcs.2023.113976
Labao, A. B., & Adorna, H. N. (2023). Communication Complexities of Leakage-secure PKE Cryptosystems and Generic Transformations. Philippine Journal of Science, 152(1), 125–140.
Addawe J., Caro J., Juayong R. (2023). Machine Learning Methods for Modeling Dengue Incidence in Local Communities. Novel & Intelligent Digital Systems. https://doi.org/10.1007/978-3-031-17601-2_38