# Lalla Mouatadid

Department of Computer Science - University of Toronto

~~Sandford Fleming Building, Office SF4306~~.

**E-mail**: firstname [at] cs.toronto.edu

[ Publications ] [ CV ] [ PhD thesis ] [ My sister's work ]

Click here for all publications.

1. A New Graph Parameter To Measure Linearity

Journal: Journal of Graph Theory (JGT), 2023

Conference: International Conference on Combinatorial Optimization and Applications (COCOA), 2017

2. A General Algorithmic Scheme for Modular Decompositions of Hypergraphs

Journal: Theoretical Computer Science (TCS), 2022

Conference: International Workshop on Combinatorial Algorithms (IWOCA), 2019

3. (α, β)-Modules in Graphs

Manuscript

4. Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

Journal: Algorithmica, 2020

Poster: Symposium on Theory of Computing (STOC), 2017

Conference: International Symposium on Algorithms and Computation (ISAAC), 2017

5. Approximating Modular Decomposition is Hard

Conference: Conference on Algorithms and Discrete Applied Mathematics (CALDAM), 2020

6. Graph Searches and Geometric Convexities in Graphs

Manuscript

Conference: International Colloquium on Graph Theory (ICGT), 2018

7. A note on the De Bruijn-Erdos Theorem for Asteroidal-Triple Free Graphs

Manuscript: 2017

8. Linear Time Maximum Weighted Independent Set on Cocomparability Graphs

Journal: Information Processing Letters (IPL), 2016

Poster: ONCWIC, 2013 [

Manuscript

9. Path Graphs, Clique Trees and Flowers

Manuscript: ArXiv, 2015

10. The LexDFS Structure of Posets

Manuscript, 2014

Slides: Gara's talk at Connections in Discrete Math at SFU.

11. Linear Time LexDFS on Cocomparability Graphs

Conference: Scandinavian Workshop on Algorithm Theory (SWAT), 2014

∞. Efficient Generation of the Ideals of a Poset

Conference Slides: MAthFest MAA, 2009

CSC373 - Algorithm Design and Analysis. (2016)

CSC373 - Algorithm Design and Analysis. (2014)

CSC473 - Advanced Algorithms. (Winter '17)

CSC2404 - Computability and Logic (Graduate course). (Fall '16)

CSC2420 - Algorithm Design, Analysis and Theory (Graduate course). (Winter '15)

CSC373 - Algorithm Design and Analysis. (Winter & Fall '14, Winter '15)

CSC263 - Data Structures and Analysis (Fall '15, Winter '16)

CSC236 - Introduction to Theory of Computation (Winter '14 & Fall '14, '12)

CSC165 - Mathematical Expression and Reasoning for Computer Science. (Winter, Summer, Fall '13 & Fall '16)

Graph Searching & Perfect Graphs

For some reason (*whispers*: convex geometries), graph searching seems to extract useful algorithmic structure from various graph classes. This structure often leads to elegant and simple linear time algorithms. We illustrate this point with two graph searches on two perfect graph classes: Lexicographic Breadth Search on Chordal Graphs, and Lexicographic Depth First Search on Cocomparability graphs.

[pdf]

Szemerédi's Regularity Lemma

An expository writing where I discuss Diestel's proof of the Regularity Lemma, and the co-NP completeness of regularity testing.

[pdf]

Characterization of complex genetic disease using exomic SNVs and gene expression data

A class project for Machine Learning in Computational Biology that Aziz and I worked on, under the supervision of Dr. Goldenberg. We explored combining both exome sequences and gene expression in order to identify harmful genes and to characterize the mechanism, that when disrupted, can cause the disease. Aziz made great extensions to this work, and thus the paper won't be available until his results are published.

fMRI Classification of Cognitive States Across Multiple Subjects

The problem considered in this study is to differentiate between two cognitive states (reading a sentence or looking at an image), by training one classifier across multiple subjects. Human brains differ anatomically in shape and size. It is therefore complicated to generalize the outcome of fMRI scans, since the number of voxels differ from one subject's brain to another. In this work, I examine the possibility of training one classifier to use across multiple subjects. Succeeding in doing so will allow us to associate brain activities to cognitive states independently from the anatomy of the brain.

[pdf]

I'm a recent Ph.D graduate from the Theory Group at the University of Toronto, where I was supervised by Allan Borodin and Derek Corneil.

My research interests are in graph theory and algorithms, particularly on algorithmic and structural graph theory, modular decomposition, convex geometries, antimatroids, and the generation of combinatorial objects.

[ Publications ] [ CV ] [ PhD thesis ] [ My sister's work ]

**Sporadic Updates**- [
**Talk**] I'm invited to speak at the ICALP workshop Graph Width Parameters: from Structure to Algorithms. - [
**Talk**] I'll be presenting our work on (α, β)-Modules at CanaDAM. - [
**Talk**] I'll be giving a talk at the**Stanford Theory Seminar**in October. - [
**Award**] I've been awarded the**NSERC PostDoc Fellowship**for 2019-2021! [Declined] - [
**Talk**] I'll be presenting our work on Modular Decomposition of Hypergraphs at GROW 2019. - [
**Award**] I've been awarded the Alfred B. Lehman Graduate Scholarship! - [
**Research Visit**] I'll be visiting Blair Sullivan@NC State on August. - [
**Talk**] I'll be presenting our work on Antimatroids and Convexities at ICGT 2018 in Lyon. - [
**Seminar**] I'll be participating/talking at the**Dagstuhl**seminar on High Performance Graph Algorithms. - [
**Talk**] See you at SIAM Discrete Math in Denver! I'll be presenting our work on Induced Matching. - [
**Talk**] I'll be giving a talk at the**Princeton Math Seminar**on Graph Searches on Structured Graph Classes. - [
**Research Visit**] I'm visiting**Princeton**this November. - [
**Talk**] In China for a conference + talks, see you at**Shanghai Jiao Tong University**! - [
**Seminar**] I'm organizing GROW 2017 at the Fields Institute with Derek. - [
**HLF**] I've been invited by Steve Cook to participate in the**Heidelberg Laureate Forum**2016! - [
**Talk**] I'm invited to talk at the GRASTA Workshop on Graph Search, held in Leiden this year. - [
**Teaching**] I'll be teaching CSC373 this summer! - [
**Award**] I've been awarded the**NSERC Graduate Scholarship**for 2015-2018! - [
**Research Visit**] I'll be away all summer visiting**Paris 7**and**BTU**, Germany. - [
**Talk**] In Copenhagen next month to present our work on Linear Time LexDFS! - [
**Teaching**] I'll be teaching CSC373 (Algorithms and Complexity)! - [
**Award**]**First Prize**(Full participation covered to Grace Hopper) for our work on Linear Time WMIS on Cocomp! - [
**Talk**] In Boca Raton this spring to present our work on Linear Time LexDFS.

**TCS Publications**Click here for all publications.

1. A New Graph Parameter To Measure Linearity

Journal: Journal of Graph Theory (JGT), 2023

Conference: International Conference on Combinatorial Optimization and Applications (COCOA), 2017

2. A General Algorithmic Scheme for Modular Decompositions of Hypergraphs

Journal: Theoretical Computer Science (TCS), 2022

Conference: International Workshop on Combinatorial Algorithms (IWOCA), 2019

3. (α, β)-Modules in Graphs

Manuscript

4. Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

Journal: Algorithmica, 2020

Poster: Symposium on Theory of Computing (STOC), 2017

Conference: International Symposium on Algorithms and Computation (ISAAC), 2017

5. Approximating Modular Decomposition is Hard

Conference: Conference on Algorithms and Discrete Applied Mathematics (CALDAM), 2020

6. Graph Searches and Geometric Convexities in Graphs

Manuscript

Conference: International Colloquium on Graph Theory (ICGT), 2018

7. A note on the De Bruijn-Erdos Theorem for Asteroidal-Triple Free Graphs

Manuscript: 2017

8. Linear Time Maximum Weighted Independent Set on Cocomparability Graphs

Journal: Information Processing Letters (IPL), 2016

Poster: ONCWIC, 2013 [

**First prize**winner of Best Poster ]Manuscript

9. Path Graphs, Clique Trees and Flowers

Manuscript: ArXiv, 2015

10. The LexDFS Structure of Posets

Manuscript, 2014

Slides: Gara's talk at Connections in Discrete Math at SFU.

11. Linear Time LexDFS on Cocomparability Graphs

Conference: Scandinavian Workshop on Algorithm Theory (SWAT), 2014

∞. Efficient Generation of the Ideals of a Poset

Conference Slides: MAthFest MAA, 2009

Generation of Ideals of Crown Posets in a Gray Code Manner, in Constant Amortized Time:
A work I did in my undergrad., under the supervision of Gara Pruesse, and presented
at the MAA MathFest conference.

**Teaching****Course Instructor**CSC373 - Algorithm Design and Analysis. (2016)

CSC373 - Algorithm Design and Analysis. (2014)

**Teaching Assistant**CSC473 - Advanced Algorithms. (Winter '17)

CSC2404 - Computability and Logic (Graduate course). (Fall '16)

CSC2420 - Algorithm Design, Analysis and Theory (Graduate course). (Winter '15)

CSC373 - Algorithm Design and Analysis. (Winter & Fall '14, Winter '15)

CSC263 - Data Structures and Analysis (Fall '15, Winter '16)

CSC236 - Introduction to Theory of Computation (Winter '14 & Fall '14, '12)

CSC165 - Mathematical Expression and Reasoning for Computer Science. (Winter, Summer, Fall '13 & Fall '16)

**Other Projects & Expository Writings**Graph Searching & Perfect Graphs

For some reason (*whispers*: convex geometries), graph searching seems to extract useful algorithmic structure from various graph classes. This structure often leads to elegant and simple linear time algorithms. We illustrate this point with two graph searches on two perfect graph classes: Lexicographic Breadth Search on Chordal Graphs, and Lexicographic Depth First Search on Cocomparability graphs.

[pdf]

Szemerédi's Regularity Lemma

An expository writing where I discuss Diestel's proof of the Regularity Lemma, and the co-NP completeness of regularity testing.

[pdf]

Characterization of complex genetic disease using exomic SNVs and gene expression data

A class project for Machine Learning in Computational Biology that Aziz and I worked on, under the supervision of Dr. Goldenberg. We explored combining both exome sequences and gene expression in order to identify harmful genes and to characterize the mechanism, that when disrupted, can cause the disease. Aziz made great extensions to this work, and thus the paper won't be available until his results are published.

fMRI Classification of Cognitive States Across Multiple Subjects

The problem considered in this study is to differentiate between two cognitive states (reading a sentence or looking at an image), by training one classifier across multiple subjects. Human brains differ anatomically in shape and size. It is therefore complicated to generalize the outcome of fMRI scans, since the number of voxels differ from one subject's brain to another. In this work, I examine the possibility of training one classifier to use across multiple subjects. Succeeding in doing so will allow us to associate brain activities to cognitive states independently from the anatomy of the brain.

[pdf]