I am supervising projects in 2022.
Projects on Combinatorial Group Testing
Research area: Group testing consists of testing for defective items in a set of items by combining items into groups or tests (see https://en.wikipedia.org/wiki/Group_testing). In combinatorial group testing (CGT), we try to construct the minimum number of tests necessary to identify d defective individuals in a set of n items. For example, if there is one infected individual in a group of n individuals, we can combine items into pools/groups and perform log n tests on the groups to identify the infected individual.
This strategy has been applied to coronavirus testing (see
The mathematical strategy that could transform coronavirus testing, Nature, Vol 583, July 2020), but there are many other applications in cryptography and communications. For intro on CGT see book by Du and Hwang.
This project topic: This project is related to ongoing research described in manuscript/article: "Structure-aware combinatorial group testing: a new method for pandemic screening" by Thais Bardini Idalino and Lucia Moura
(https://arxiv.org/pdf/2202.09264.pdf)
article abstract: Combinatorial group testing (CGT) is used to identify defective items from a set of items by grouping them together and performing a small number of tests on the groups.
Recently, group testing has been used to design efficient COVID-19 testing, so that resources are saved while still identifying all infected individuals. Due to test waiting times, a focus is given to non-adaptive CGT, where groups are designed a priori and all tests can be done in parallel. The design of the groups can be done using Cover-Free Families (CFFs). The main assumption behind CFFs is that a small number d of positives are randomly spread across a population of n individuals. However, for infectious diseases, it is reasonable to assume that infections show up in clusters of individuals with high contact (children in the same classroom within a school, households within a neighbourhood, students taking the same courses within a university, people seating close to each other in a stadium). The general structure of these communities can be modeled using hypergraphs, where vertices are items to be tested and edges represent clusters containing high contacts. We consider hypergraphs with non-overlapping edges and overlapping edges (first two examples and last two examples, respectively). We give constructions of what we call structure-aware CFF, which uses the structure of the underlying hypergraph. We revisit old CFF constructions, boosting the number of defectives they can identify by taking the hypergraph structure into account. We also provide new constructions based on hypergraph parameters.
We are interested in testing these methods in real data, which requires data preparation, representing the communities as edges of a hypergraph and implementing algorithms to create the hypergraphs and the group testing matrix based on various mathematical constructions. Hypergraphs are generalizations of graphs where edges contain two or more vertices (in graphs edges connect 2 vertices).
Students involved in the project will be taught the methods and background and will be reporting their progress in weekly meetings with the supervisor.
Below there are two types of opportunities for undergraduates to be involved in this project - via a summer long full-time internship or via work on their honours project. Someone finishing their honours project in Winter 2022 could potentially participate in both. If there is more than one student qualified for a honour's project, it is possible to divide the project into two somewhat independent parts or aspects as suggested in projects A and B below.
- Full-time summer research project on "Combinatorial Algorithms for Structure-aware Combinatorial Group Testing" or similar title.
Proposal can be submitted for funding under the NSERC USRA program; Application deadline at Uottawa is March 1, 2022. Project proposal preparation with supervisor during February 2021.
Results announced April 1, 2022. Undergraduate research full time for 16 weeks May-August 2022. NSERC stipulates: Canadian citizen or permanent resident of Canada; work cannot be held jointly with daytime courses nor with work term.
High CGPA required to have a chance of being awarded this competitive award; competition is among a number of scholarships available for the University of Ottawa (Science and Engineering) undergraduates; it works for someone that graduates the term before (Winter 2022) and is not yet enrolled in master's. Contact Lucia Moura if interested.
- Honour's project A (CSI4900, Winter 2022) Community-aware group testing A - Algorithms for hypergraph and for struct-aware combinatorial group testing.
Short description: Build hypergraph from real data and synthetic data describing the communities. Implementation of data structures and algorithms for hypergraphs. Analysing properties of hypergraphs. Apply non-adaptive methods for combinatorial group testing to the more general case of community aware group testing. Perform experiments and analyse results.
Strength sought in: algorithms, programming, graph theory, graph algorithms, combinatorics and discrete mathematics.
- Honour's project B (CSI4900, Winter 2022) Community-aware group testing B - algorithms to build cover-free families and structure-aware cover-free families.
Short description: Algorithms for constructing cover-free families using various constructions (e.g. Sperner construction, product construction, block design construction, polynomials over finite fields).
Using hypergraphs based on communities to build structure aware cover-free families. Perform experiments and analyse results.
Strength sought in: algorithms, programming, combinatorics, discrete mathematics,
graph theory, graph algorithms.
Interested students should contact Lucia Moura lmoura@uottawa.ca to setup an interview. In the email, please introduce yourself highlighting your strengths and interests, indicate the type of project and attach CV and transcripts.
Recent short-term projects supervised by Lucia Moura
- Matthew Demczyk, Sudoku clue minimization with metaheuristic search and dancing links. CSI4900 undergraduate project, Fall 2021.
- Biliang Wang, Implementing MULTIDOKU, a multiplayer game based on Sodoku and relying on combinatorial algorithms. CSI6900 Master's project, Winter 2001.
- Ben Burke and Wei Hu, Deep reinforced learning for solving combinatorial games with exponential action spaces (co-supervised with Yongyi Mao). CSI4900 undergraduate project, Fall 2020.
Winner of Cognos Prize (shared with another group).
Last update January 19, 2022.