Michael Levet's Homepage

<!doctype html> <html lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <meta name="description" content="Michael Levet's Homepage."> <title>Michael Levet's Homepage</title> <link rel="stylesheet" href="https://michaellevet.github.io/css/layouts/pure-min.css">   <link rel="stylesheet" href="https://michaellevet.github.io/css/layouts/side-menu.css">  </head> <body> <div id="layout">  <a href="#menu" id="menuLink" class="menu-link">  <span></span> </a> <div id="menu"> <div class="pure-menu"> <a class="pure-menu-heading" href="#">Navigation</a> <ul class="pure-menu-list"> <li class="pure-menu-item"><a href="#home" class="pure-menu-link">Home</a></li> <li class="pure-menu-item"><a href="#currentteaching" class="pure-menu-link">Current Courses</a></li> <li class="pure-menu-item"><a href="#research" class="pure-menu-link">Research Interests</a></li> <li class="pure-menu-item" class="menu-item-divided pure-menu-selected"> <a href="#publications" class="pure-menu-link">Publications</a> </li> <li class="pure-menu-item"><a href="teaching.html" class="pure-menu-link">Teaching History</a></li> <li class="pure-menu-item"><a href="#notes" class="pure-menu-link">My Course<br/> Materials</a></li> <li class="pure-menu-item"><a href="#books" class="pure-menu-link">Book <br/> Recommendations</a></li> <li class="pure-menu-item"><a href="#links" class="pure-menu-link">Helpful Links</a></li> </ul> </div> </div> <div id="main"> <div class="header"> <h1>Michael Levet</h1> </div> <div class="content"> <h2 class="content-subhead" id="home">Contact Information</h2> <p> <ul> <li>Assistant Professor of Computer Science, College of Charleston</li> <li>Office: Harbor Walk East (HWEA) 312</li> <li>Email Me: lastnamefirstinitial (at) cofc (dot) edu</li> <li>Pronouns: He/Him/His</li> </ul> </p> <h2 class="content-subhead" id="currentteaching">Current and Upcoming Courses:</h2> <p> <ul> <li> College of Charleston <ul> <li>Spring 2025: CSCI 300 Seminar in Computing</li> <li>Spring 2025: CSCI 350 Digital Logic and Computer Organization (2 sections)</li> <li>Spring 2025: CSCI 399/CSIS 691 Computational Complexity (Independent Study)</li> <li>Fall 2024: <a href="https://michaellevet.github.io/F24/CSCI300/index.html">CSCI 300 Seminar in Computing</a></li> <li>Fall 2024: <a href="https://michaellevet.github.io/F24/CSCI310/index.html">CSCI 310 Advanced Algorithms (2 sections)</a></li> </ul> </li> </ul> </p> <h2 class="content-subhead" id="research">Research Interests</h2> <p> <ul> <li>Algebraic Combinatorics, Algorithms in Finite Groups, Computational Complexity, Descriptive Complexity, Isomorphism Testing, Phylogenetics, Relation Algebras</li> </ul> </p> <h2 class="content-subhead" id="publications">Publications:</h2> <p> <ul> <li>Pairwise Rearrangement in the Single Cut-and-Join Model is Fixed Parameter Tractable (Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Inne Singgih, Grace Stadnyk, Alexander Wiedemann), (<a href="https://arxiv.org/abs/2402.01942">arXiv</a>, <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.3">Conference Version</a>), SWAT 2024. </li> <li>On the Constant Depth Circuit Complexity of Generating Quasigroups (Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Wei脽), (<a href="https://arxiv.org/abs/2402.00133">arXiv</a>, <a href="https://dl.acm.org/doi/10.1145/3666000.3669691">Conference Version</a>), ISSAC 2024. </li> <li>Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman (Michael Levet, Puck Rombach, Nicholas Sieger), (<a href="https://arxiv.org/abs/2306.17777">arXiv</a>, <a href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32">Conference Version</a>), SWAT 2024. </li> <li>Moments of Colored Permutation Statistics on Conjugacy Classes (Jesse Campion Loth, Michael Levet, Kevin Liu, Sheila Sundaram, Mei Yin), (<a href="https://arxiv.org/abs/2305.11800">arXiv</a>, <a href="https://fpsac2024.rub.de/public/extended_abstracts/liuK.pdf">Conference Version</a>); FPSAC 2024. </li> <li>Complexity and Enumeration in Models of Genome Rearrangement (Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Elizabeth Matson, Inne Singgih, Grace Stadnyk, Xinyi Wang, Alexander Wiedemann), COCOON 2023, full journal version in <em>Theoretical Computer Science</em> (2024). (<a href="https://arxiv.org/abs/2305.01851">arXiv</a>, <a href="https://link.springer.com/chapter/10.1007/978-3-031-49190-0_1">Conference Version</a>, <a href="https://doi.org/10.1016/j.tcs.2024.114880">Journal Version</a>). </li> <li><a href="mythesis.pdf">On the Combinatorial and Logical Complexities of Algebraic Structures</a> (PhD Dissertation)</li>  <li><a href="https://arxiv.org/abs/2301.00898">Permutation Statistics in Conjugacy Classes of the Symmetric Group</a> (Jesse Campion Loth, Michael Levet, Kevin Liu, Eric Nathan Stucky, Sheila Sundaram, Mei Yin), <em>Preprint</em>. </li> <li>Count-Free Weisfeiler--Leman and Group Isomorphism (Nathaniel A. Collins, Michael Levet), <em>International Journal of Algebra and Computation</em> (2024) (<a href="https://arxiv.org/abs/2212.11247">arXiv</a>, <a href="https://doi.org/10.1142/S0218196724500103">Journal</a>). </li> <li>On the Descriptive Complexity of Groups without Abelian Normal Subgroups (Joshua A. Grochow, Michael Levet), Accepted for non-archival presentation in Highlights of Logic, Games, and Automata 2023; GandALF 2023 (<a href="https://arxiv.org/abs/2209.13725">arXiv</a>, <a href="https://dx.doi.org/10.4204/EPTCS.390.12">Conference Version</a>). </li> <li>Comer Schemes, Relation Algebras, and the Flexible Atom Conjecture (Jeremy F. Alm, David Andrews, Michael Levet), RAMiCS 2023, to appear in <em>Fundamenta Informaticae</em> (<a href="https://arxiv.org/abs/1905.11914">arXiv</a>, <a href="https://link.springer.com/chapter/10.1007/978-3-031-28083-2_2">Conference Version</a>) .</li> <li>Directed Ramsey and Anti-Ramsey Schemes and the Flexible Atom Conjecture (Jeremy F. Alm, Michael Levet), <em>International Journal of Algebra and Computation</em> (2023), (<a href="https://arxiv.org/abs/1901.06781">arXiv</a>, <a href="https://doi.org/10.1142/S0218196723500595">Journal</a>). </li> <li>On the Complexity of Identifying Strongly Regular Graphs (Michael Levet), <em>Australasian Journal of Combinatorics</em> (2023), (<a href="https://arxiv.org/abs/2207.05930">arXiv</a>, <a href="https://ajc.maths.uq.edu.au/pdf/87/ajc_v87_p041.pdf">Journal</a>) </li> <li> Experience Report: Standards-Based Grading at Scale in Algorithms- (Lijun Chen, Joshua A. Grochow, Ryan Layer, Michael Levet), <em>ITiCSE 2022</em>. (<a href="https://dl.acm.org/doi/10.1145/3502718.3524750">Conference Version</a>; <a href="https://arxiv.org/abs/2204.12046">Extended Preprint</a>) </li> <li> On the Parallel Complexity of Group Isomorphism via Weisfeiler--Leman- (Joshua A. Grochow, Michael Levet), <em>FCT 2023</em>, where it received a Best Paper Award. (<a href="https://arxiv.org/abs/2112.11487">arXiv</a>, <a href="https://link.springer.com/chapter/10.1007/978-3-031-43587-4_17">Conference Version (Extended Abstract)</a>) </li> <li>Improved bounds on the size of the smallest representation of relation algebra 32<sub>65</sub>- (Jeremy F. Alm, Michael Levet, Saeed Moazami, Jorge Montero-Vallejo, Linda Pham, Dave Sexton, Xiaonan Xu), <em>Algebra Universalis</em> (2022), (<a href="https://arxiv.org/abs/1911.00620">arXiv</a>, <a href="https://link.springer.com/article/10.1007/s00012-022-00791-4">Journal</a>). </li> <li> Master's Thesis: “<a href="modelmain.pdf">Graph Homomorphisms and Vector Colorings</a> ” </li> <li> <a href="http://link.springer.com/article/10.1007/s11047-016-9584-z">Activity in Boolean Networks</a> - (Abhijin Adiga, Hilton Galyean, Chris J. Kuhlman, Michael Levet, Henning S. Mortveit, Sichao Wu), <em>Journal of Natural Computing (2017)</em>. </li> <li> <a href="https://link.springer.com/chapter/10.1007/978-3-319-47509-7_6">A Mechanism Design Approach For Influence Maximization</a> - (Michael Levet, Siddharth Krishnan), <em>GameNets (2016)</em>. </li> <li> <a href="https://link.springer.com/chapter/10.1007/978-3-662-47221-7_16">Network Structure and Activity in Boolean Networks</a> - (Abhijin Adiga, Hilton Galyean, Chris J. Kuhlman, Michael Levet, Henning S. Mortveit, Sichao Wu), <em>Cellular Automata and Discrete Complex Systems (2015)</em>. </li> </ul> </p>  <h2 class="content-subhead" id="notes">My Course Materials</h2> <p> I welcome comments, suggestions, and corrections. Please reach out to me via email with any feedback you may have regarding my notes. <ul> <li><a href="Lecture_Notes.pdf">Theory of Computation (Draft)</a> (Mathematical Preliminaries, Finite State Automata, Group Theory, Computability, Complexity) </li> <li><a href="Computational_Complexity_Notes.pdf">Computational Complexity Notes (Draft)</a></li> <li> <a href="Algorithms_Notes.pdf">Algorithms Lecture Notes (Draft)</a> <ul> <li>Adopted as the official course text in CSCI 3104 Algorithms in Summer 2021 and Spring 2022</li> </ul> </li> <li><a href="FCPS_Lecture_Notes.pdf">Fundamentals of Computer Science Lecture Notes</a> (Introduction to Java, Discrete Math, and Digital Logic)</li> <li><a href="Game_Theory_Notes.pdf">Introduction to Game Theory</a></li> <li>My guided-discovery <a href="Shannon_Capacity.pdf">problem set</a> introducing the Shannon Capacity of a Graph</li> <li> During the Spring 2020, Fall 2020, and Summer 2021 semesters, I have implemented active learning in my Algorithms recitations. Here are some of my active learning worksheets. These have since been adopted in CSCI 3104 Algorithms during the Fall 2021 and Spring 2022 semesters. <ul> <li><a href="Algorithms/Recitation_Week2.pdf">Runtime Analysis</a></li> <li><a href="Algorithms/Recitation_Week4.pdf">Quickselect</a></li> <li><a href="Algorithms/Recitation_Week5.pdf">Introduction to Graph Theory</a> and my accompanying <a href="Algorithms/Graph_Theory_Notes.pdf">Graph Theory Notes</a></li> <li><a href="Algorithms/Recitation_Week6.pdf">Trees</a></li> <li><a href="Algorithms/Recitation_Week9_Flows.pdf">Flows</a></li> <li><a href="Algorithms/Recitation_Week10_Rod_Cutting.pdf">Dynamic Programming- Rod Cutting</a></li> <li><a href="Algorithms/Nim.pdf">Dynamic Programming- Game of Nim</a></li> </ul> </li> </ul> </p> <h2 class="content-subhead" id="books">Book Recommendations</h2> <ul> <li> A First Course in Proofs <ul> <li> <a href="https://open.umn.edu/opentextbooks/BookDetail.aspx?bookId=7"><em> Book of Proof </em>- Richard Hammack</a> </li> <li> <a href="http://www.math.vt.edu/people/elder/Math3034/"><em>An Introduction to Mathematical Proofs</em>- Jimmy Arnold </a></li> </ul> </li> <li> Favorite Combinatorics and Graph Theory Books <ul> <li> <em> Bijective Combinatorics </em>- Nicholas Loehr </li> <li> <em> Introduction to Graph Theory </em>- Douglas West</li> <li> <em> Algebraic Graph Theory</em> - Chris Godsil and Gordon Royle</li> <li> <em> An Introduction to the Theory of Graph Spectra</em>- Drago&scaron; M. Cvetkovi&cacute;, Peter Rowlinson, and Slobodon Simi&cacute; </li> <li> <em> Linear Algebra Methods in Combinatorics With Applications to Geometry and Computer Science</em>- Laszlo Babai and Peter Frankl </li> </ul> </li> <li> Theory of Computation and Algorithms <ul> <li> <em>Introduction to Algorithms</em>- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein</li> <li> <em>Computational Complexity: A Modern Approach</em>- Sanjeev Arora and Boaz Barak</li> <li> <a href="https://cs.brown.edu/people/jsavage/book/"><em>Models of Computation</em>- John E. Savage</a></li> <li> <em> Introduction to the Theory of Computation </em>- Michael Sipser </li> <li> <em>Introduction to Automata Theory, Languages and Computation</em> (1st Edition)- John E. Hopcroft and Jeffrey D. Ullman. <br/> </li> <li> <em>Introduction to Automata Theory, Languages and Computation</em> (3rd Edition)- John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman </li> <li> <strong>Remark:</strong> The 1st Edition of Hopcroft and Ullman's text is a beautifully written book full of a lot of important material. However, it is really geared at a mathematically mature audience. The 3rd edition is more watered down in terms of the material, but the authors emphasize proof strategy. The later edition is more appropriate for an audience with minimal proofs-based mathematics. </li> </ul> </li> <li> Linear Algebra <ul> <li> <em>Linear Algebra</em>- Stephen H. Friedberg, Arnold J. Insel, and Lawrence E. Spence</li> <li> <em>Advanced Linear Algebra</em>- Nicholas Loehr</li> </ul> </li> <li> Abstract Algebra <ul> <li> <a href="https://open.umn.edu/opentextbooks/BookDetail.aspx?bookId=217"><em> Abstract Algebra: Theory and Applications</em>- Thomas Judson</a> </li> <li> <em>A Book of Abstract Algebra</em>- Charles C. Pinter</li> <li> <em>Abstract Algebra</em>- David Dummit and Richard Foote</li> </ul> </li> <li>Microeconomics and Game Theory <ul> <li> <a href="https://homes.cs.washington.edu/~karlin/GameTheoryBook.pdf"><em>Game Theory, Alive</em>- Anna R. Karlin and Yuval Peres</a></li> <li> <a href="http://jasonhartline.com/MDnA/"><em>Mechanism Design and Approximation</em>- Jason D. Hartline</a></li> <li> <em>Auction Theory</em>- Vijay Krishna</li> <li> <em>Algorithmic Game Theory</em>- Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani</li> <li> <a href="http://people.math.sc.edu/thornef/schc212/index.html">Frank Thorne's Lecture Notes on the Mathematics of Game Shows</a></li> </ul> </li> </ul> <h2 class="content-subhead" id="links">Helpful Links</h2> <p> <ul> <li><a href="Algorithms/HW3_PH.pdf">Polynomial-Time Hierarchy Problem Set</a></li>  <li> <a href="http://people.math.sc.edu/cooper/proofs.pdf">Why do we have to learn proofs!?</a>- Josh Cooper</li> <li> <a href="http://staffhome.ecm.uwa.edu.au/~00043886/humour/invalid.proofs.html">Invalid Proof Techniques</a> </li> <li> <a href="http://tutorial.math.lamar.edu/">Paul's Notes for Lower Level Math Classes</a> </li> </ul> </p> </div> </div> </div> <script src="js/ui.js"></script> </body> </html>

CINXE.COM

Michael Levet's Homepage