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:

Related Tags

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

Quick links: Google search, arXiv.org search, propose to present a talk

computability computer science incompleteness logic theoretical computer science turing machine

Conway’s Game of Life

Possible reference materials for this topic include

Quick links: Google search, arXiv.org search, propose to present a talk

automaton cellular automaton computer science first year friendly recreational mathematics theoretical computer science

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

Quick links: Google search, arXiv.org search, propose to present a talk

coding theory complexity theory graph theory theoretical computer science

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

Quick links: Google search, arXiv.org search, propose to present a talk

art biology botany computability computer science fractal logic theoretical computer science

P vs. NP

Possible reference materials for this topic include

Quick links: Google search, arXiv.org search, propose to present a talk

computability computational complexity computer science open problem theoretical computer science

Presburger Arithmetic

Possible reference materials for this topic include

Quick links: Google search, arXiv.org search, propose to present a talk

computability computational complexity computer science logic theoretical computer science

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

Quick links: Google search, arXiv.org search, propose to present a talk

automaton computer science open problem theoretical computer science

Unique Games Conjecture

The Unique Games Conjecture, if true, implies that many problems that lack exact polynomial time solutions also lack approximate polynomial time solutions. It was formulated by Subhash Khot in 2002 and is still unsolved.

Possible reference materials for this topic include

Quick links: Google search, arXiv.org search, propose to present a talk

computational complexity computer science open problem theoretical computer science