Lalla Mouatadid


Department of Computer Science - University of Toronto
Sandford Fleming Building, Office SF4306.

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

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
Pierre Charbit, Michel Habib, Lalla Mouatadid, and Reza Naserasr
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
Michel Habib, Fabien de Montgolfier, Lalla Mouatadid, Mengchuan Zou
Journal: Theoretical Computer Science (TCS), 2022
Conference: International Workshop on Combinatorial Algorithms (IWOCA), 2019


3. (α, β)-Modules in Graphs
Michel Habib, Lalla Mouatadid, Eric Sopena, Mengchuan Zou
Manuscript

4. Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
Michel Habib and Lalla Mouatadid
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
Michel Habib, Lalla Mouatadid, Mengchuan Zou
Conference: Conference on Algorithms and Discrete Applied Mathematics (CALDAM), 2020

6. Graph Searches and Geometric Convexities in Graphs
Feodor Dragan, Michel Habib, and Lalla Mouatadid
Manuscript
Conference: International Colloquium on Graph Theory (ICGT), 2018

7. A note on the De Bruijn-Erdos Theorem for Asteroidal-Triple Free Graphs
Lalla Mouatadid
Manuscript: 2017

8. Linear Time Maximum Weighted Independent Set on Cocomparability Graphs
Ekkehard Kohler and Lalla Mouatadid
Journal: Information Processing Letters (IPL), 2016
Poster: ONCWIC, 2013 [ First prize winner of Best Poster ]
Manuscript

9. Path Graphs, Clique Trees and Flowers
Lalla Mouatadid and Robert Robere
Manuscript: ArXiv, 2015

10. The LexDFS Structure of Posets
Derek Corneil, Lalla Mouatadid, Gara Pruesse
Manuscript, 2014
Slides: Gara's talk at Connections in Discrete Math at SFU.

11. Linear Time LexDFS on Cocomparability Graphs
Ekkehard Kohler and Lalla Mouatadid
Conference: Scandinavian Workshop on Algorithm Theory (SWAT), 2014

∞. Efficient Generation of the Ideals of a Poset
Lalla Mouatadid
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
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.
[pdf]