This page is under construction.

<center>
<p>
<h3>CMSC 36500 = Math 37500 </h3>

<p>
<h2>Algorithms in Finite Groups: <br>
The Graph Isomorphism problem </h2>

<p>
<h2>Spring 2017</h2>
<h3>TuTh 12:00-1:20, Ryerson 276</h3>

<p>
<h3>Instructor: L&aacute;szl&oacute; Babai</h3>
</center>
</p>
<h3>
<font color="red">NEW:</font> Reading
</h3>
Instructor's paper <a href="version2.1.pdf"><i>
Graph Isomorphism in Quasipolynomial Time</i>, Version 2.1</a>
(May 23, 2017).  This version represents a significant but
incomplete update of Version 2, posted on arXiv.
(See WARNING on the paper's front page and in the Acknowledgments.)
The paper is referenced as [GIQ] in the Class 17 notes.
<p>
<h2>Grading</h2>
Graded homework 40% <br>
<a href="quiz.pdf">Quiz (May 16, 25 min) 12.5%</a> 
&nbsp;&nbsp;&nbsp;&nbsp; see <b><a href="stat.html">statistics</a></b><br>
<a href="final.pdf">Test (May 30, 75 min) 42.5%</a> <br>
Class participation 5%
</p>
<p>
<h2> A REQUEST </h2>
Please send email to the instructor with answers to the following
questions.  Please answer the questions even if you do not require
a grade but you are attending the class.
<h3>Please respond by Friday, May 5.</h3>
<ul>
  <li> your name
  <li> your UChicago status: if undergraduate, what year/major/minor<br>
        if PhD student: department, area of specialization, advisor,
            years in the program, expected year of graduation<br>
        if other: please describe
  <li> type of grade sought: letter grade (A..F), Pass/Fail, R (grad students
         only), no grade
 <li>  are you graduating this quarter?
</ul>
</p>
<p>

<h3>Class notes by Robert Green and Angela Wu, including homework 
    (not verified by instructor unless expressly stated otherwise)</h3>
<p>
<a href="wu18.pdf">Class 18 - May 25</a> due May 30.  Verified notes.
</p>
<p>
<a href="wu17.pdf">Class 17 - May 23</a> due May 25.  Detailed, verified notes.
</p>
<p>
<a href="wu16.pdf">Class 16 - May 18</a> due May 23.  Detailed, verified notes.
</p>
<p>
<a href="wu15.pdf">Class 15 - May 16</a> due May 18.  Detailed, verified notes.
</p>
<p>
<a href="wu14.pdf">Class 14 - May 11</a> due May 16.  Detailed, verified notes.
</p>
<p>
<a href="wu13.pdf">Class 13 - May 9</a> due May 11.  Partially verified notes.
</p>
<p>
<a href="wu12.pdf">Class 12 - May 4</a> due May 9.  Detailed, verified notes.
</p>
<p>
<a href="wu11.pdf">Class 11 - May 2</a> due May 4.  Detailed, verified notes.
</p>
<p>
<a href="wu8.pdf">Class 8 - April 20</a> due April 25.  Detailed, verified notes.
</p>
<p>
<a href="wu7.pdf">Class 7 - April 18</a> due April 20
</p>
<p>
<a href="wu6.pdf">Class 6 - April 13</a> due April 18
</p>
<p>
<a href="green5.pdf">Class 5 - April 11</a> due April 13
</p>
<p>
<a href="green4.pdf">Class 4 - April 6</a> due April 11
</p>
<p>
<a href="green3.pdf">Class 3 - April 4</a> due April 6
</p>
<p>
<a href="green2.pdf">Class 2 - March 30</a> due April 4
</p>
<p>
<a href="green1.pdf">Class 1 - March 28</a> due March 30
</p>

<p>
The course may be of interest to those interested in finite groups,
combinatorics, and the interaction of these fields with
the theory of algorithms.
</p>

<p>
<h3>Synopsis</h3>
</p>

<p>
The main goal of the course is a full presentation of the 
quasipolynomial-time algorithm for the Graph Isomorphism problem 
I announced in November 2015.
</p>

<p>
Toward this goal, we shall spend much of the time studying 
</p>

<ul>
  <li> the structural and asymptotic theory of finite permutation groups and 
  <li> the structure of highly regular combinatorial objects called 
       <i>coherent configurations</i>.
</ul>

<p>
This is a pure mathematics course, no prior knowledge of the theory
of algorithms is required.
</p>

<p>
The prerequisite is basic familiarity with finite groups, on the
level of the group theory segment of an undergraduate abstract
algebra course: be comfortable with the proofs of Sylow's theorems
and the Jordan--H&ouml;lder Theorem.
</p>

<p>
The course will begin with an introduction to elements of group
theory beyond the normal undergraduate curriculum, including
solvability, nilpotence, and classes of finite simple groups.
</p>

<p>
The material will overlap with my 
<a href="http://people.cs.uchicago.edu/~laci/14groups">
2014 course by the same course number</a>.   You may want to
check out the exercises posted there.
</p>