Lalla Mouatadid

Department of Computer Science
University of Toronto
10 King's College Road.
Sandford Fleming Building, Room SF4306.
M5S 3G4, Toronto, ON

E-mail: firstname [at]


I'm a Ph.D student in the Theory Group, at the Department of Computer Science at the University of Toronto, fortunate to be working under the supervision of Derek Corneil and Allan Borodin.

My research interests lie in graph theory and algorithms, specifically on how graph searches can lead to simple linear and near linear time algorithms on structured families of graphs. I am also interested in the generation of combinatorial objects, I did a bit of work in that area in my undergrad. under Gara Pruesse's supervision.


Maximum Induced Matching Algorithms via Vertex Ordering Characterizations [pdf]
Michel Habib and Lalla Mouatadid
ISAAC 2017, LIPIcs. To appear.
Preliminary results presented at STOC'17 (Poster presentation) [poster].

A New Graph Parameter To Measure Linearity [pdf]
Pierre Charbit, Michel Habib, Lalla Mouatadid, and Reza Naserasr
COCOA 2017, LNCS, Springer. To appear.

Linear Time Maximum Weighted Independent Set on Cocomparability Graphs [pdf]
Ekkehard Kohler and Lalla Mouatadid
Information Processing Letters 116(6): 391-395, 2016.
First prize winner of Best Poster, ONCWIC 2013 [poster]

Linear Time LexDFS on Cocomparability Graphs [pdf]
Ekkehard Kohler and Lalla Mouatadid
SWAT, LNCS, Springer 319-330, 2014.

Path Graphs, Clique Trees and Flowers [pdf]
Lalla Mouatadid and Robert Robere
Manuscript, 2015

Other Projects & Expository Writings

Graph Searching & Perfect Graphs
Perfect graphs, by definition, have a nice structure, that graph searching seems to extract in a, often non-inexpensive, manner. We scratch the surface of this elegant research area by giving two examples: Lexicographic Breadth Search on Chordal Graphs, and Lexicographic Depth First Search on Cocomparability graphs.

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.

Characterization of complex genetic disease using exomic SNVs and gene expression data
Aziz Mezlini, Lalla Mouatadid, and Anna Goldenberg
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.

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


Course Instructor
   CSC373 - Algorithm Design and Analysis. (Summer '16)
   CSC373 - Algorithm Design and Analysis. (Summer '14)

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)