# Theoretical computer science

There have been 2 completed talks and 8 topic suggestions tagged with theoretical computer science.

There are many subfields of theoretical computer science, including:

## Completed Talks

### Expander Graphs

Delivered by Frieda Rong on Wednesday November 29, 2017

In this talk, we’ll study graphs which are “sparse” yet “highly connected”. Known as expanders, these graphs exhibit interesting properties which can be viewed from a rich array of analytic, combinatorial, and probabilistic perspectives. Contributions of expanders range from the proof of important results in complexity theory to derandomization of algorithms to the construction of robust networks and cryptographic hash functions. We’ll see one application to coding theory, where expanders can be used to provide asymptotically “good” error-correcting codes with linear time encoding and decoding.

Prerequisites: linear algebra (familiarity with eigenvalues and eigenvectors).

### Automatic sequences

Delivered by Laindon Burnett on Wednesday October 25, 2017

This talk will begin with a brief overview behind the theory of words in mathematics as well as the theory of finite automata in theoretical computer science. After this, we will define what an automatic sequence is, prove some fundamental theorems about them, and investigate some of their more intriguing properties. The majority of information presented comes from the text “Automatic Sequences: Theory, Applications, Generalisations” by Jean-Paul Allouche and the University of Waterloo's own Jeffrey Shallit, from the department of Computer Science.

The speaker has provided a PDF document covering the same content as this talk.

## Talk Suggestions

### Completeness, Incompleteness, and Turing Machines

This topic studies the connection between Gödel’s incompleteness theorems and turing machines and how each implies the other

Possible reference materials for this topic include

### Conway’s Game of Life

Possible reference materials for this topic include

### Expander Graphs and Applications

Expander graphs are sparse graphs with strong connectivity properties and finds applications in complexity theory, designing of computer networks and the theory of error-correcting codes.

Possible reference materials for this topic include

### Lindenmeyer systems

Originally developed to model plant growth, L-systems are a logical approach to various scientific questions, as well as one of many ways to generate artistically pleasing fractals.

Possible reference materials for this topic include

### P vs. NP

Possible reference materials for this topic include

• Arora, Bazak: Computational Complexity

### Presburger Arithmetic

Possible reference materials for this topic include

### Separating Words Problem

Given two strings, we can write a computer program to tell them apart. A special kind of very simple computer program that accepts or rejects strings, using only a finite number of states while reading the string, is called a deterministic finite automaton. (These deterministic finite automata can also be expressed as a regular expression.) For any two strings of length $n$, there is some deterministic finite automaton (or regular expression) that recognizes one and not the other, and there is some smallest one. In the worst case, it is known (Robson 1989) that any two strings of length $n$ can be separated by an automaton of size $O(n^{2/5} (\log n)^{3/5})$, but this is not known to be optimal. The optimal upper bound remains an open problem.

Possible reference materials for this topic include