Toolkit for Theoretical Computer Science (Spring '24)
References
[TJ] Abstract Algebra: Theory and Applications Thomas W. Judson
[ADS] Applied Discrete Structures, Al Doerr, Ken Levasseur
Lecture 1
Introduced the Counting under Symmetries Problem
Group Theory
Read
- Chapters 3-6 in [TJ] (Mostly simple examples only. You may skip over familiar parts)
Solve
- Let $H$ be a subgroup of $G$ which is a finite group. Consider the relation $R$ defined by $aRb$ if $ a - b \in H$.
- Show that $R$ is an equivalance relation.
- Show that all equivalence classes under this relation has size $= |H|$.
Lecture 2
Legrange’s Theorem, Fermat Little Theorem, Orbits and Stabilizers
Read
- Slides
- Chapters 6 in [TJ] (Mostly simple examples only. You may skip over familiar parts)
Solve
- A cyclic group is a group which is generated by a single element. Show that all subgroups of a cyclic group are also cyclic.
- Use the Polya Theorem covered in class to count the number of colorings with R,B of pie chart where each part has the same size with angle ($2\pi/n$). Note that rotating a pie chart about the center results in the same pie chart.
Lecture 3
Burside-Polya Lemma (Dr. Kshitij Gajjar)
Read
Lecture 4
Fix points of permutations
Cycle Structure
Proof of Fermat Little Theorem using Burnside Lemma
Finding large cuts using randomness
Method of Conditional Expectations
Read
For randomized algorithms, read: Chapter 2 of https://www.cs.purdue.edu/homes/spa/courses/pg17/mu-book.pdf
Solve
Consider a 3-SAT problem with $n$ variables and $m$ clauses
- Give a randomized algorithm which gives an assignment that on expectation satisfies $7/8$ fraction of the clauses.
- Give a deterministic algorithm which outputs assignment that always satisfies $7/8$ fraction of the clauses.
Let $p$ be a prime and $n, k$ positive integers, $F = \left\{ f:\mathbb{Z}_p^k \rightarrow [n] \right\}$ (the set of all functions from $\mathbb{Z}_p^k$ to $[n]$.). For a function $f \in F$, and $a \in \mathbb{Z}_p^k$, the translation of $f$ by $a$ is the function $g(x) = f(x + a)$ (addition is defined coordinate-wise modulo $p$).
- Define a group and a group action of that group on $F$ that captures translations, which could be used to count the number of distinct functions with translation symmetry (ie. $f(x)$ and $g(x) = f(x + a)$ is in the same orbit).
- Let $a \in \mathbb{Z}^k_p \setminus \{ 0^k \}$ . What is the number of cycles in the permutation corresponding to the translation by $a$?
- Use above to show that $p^k$ divides $n^{p^k} - n^{p^{k-1}}$.
[Hint] This is the strict generalization of the example we did in class: the proof of FLT theorem. For getting that result, substitute $k=1$ and $n = a$.
Lecture 5
Randomized algorithm for MinCut.
(http://faculty.cs.tamu.edu/klappi/cpsc411s09/minimum_cut.pdf)
Ramsey Theorem using Probabilistic Method
(Section 2.1 in http://www.cs.cmu.edu/~15850/handouts/matousek-vondrak-prob-ln.pdf)
Lecture 6
Hamiltonian Paths in Tournaments (see Section 3.2 in https://www.cs.cmu.edu/~15850/handouts/matousek-vondrak-prob-ln.pdf)
Intersecting Families (Erdos Ko Rado Theorem) (see Section 2.3 in https://www.cs.cmu.edu/~15850/handouts/matousek-vondrak-prob-ln.pdf)
Sperner’s Lemma (see Section 1.2.1 in https://ocw.mit.edu/courses/18-226-probabilistic-method-in-combinatorics-fall-2020/mit18_226f20_full_notes.pdf)
Randomized Protocol for Equality checking (see last para of page 6 in https://people.cs.rutgers.edu/~sa1497/courses/cs514-s20/lec8.pdf)
Lecture 7
Spectral Graph Theory
Expanders Read Section 4.1.1
Lecture 8
Coding Theory Read Chapter 28
Assignment Problems
Let $G$ be a undirected d-regular graph and $A$ be its adjacency matrix. Show that
- The eigen values of $A$ are between $-d$ and $d$.
- The number of connected components of $G$ $=$ the number of linearly independent eigen vectors of $A$ with eigen value $d$.
- $-d$ is an eigen value of $A$ if and only of $G$ is a bipartite graph.
Lecture 9
Expander Codes Read