## Ville Salo

### Writings Related to my Studies

Some things I wrote during my studies.

- 2014
- My PhD Thesis: Subshifts with Simple Cellular Automata
- 200 pages
- supervisor Jarkko Kari
- Best Ph.D. Thesis in Computer Science in 2015 award from the Finnish Society for Computer Science
- notes here

- My PhD Thesis: Subshifts with Simple Cellular Automata
- 2013
- IP = PSPACE
- with Ilkka Törmä, 18 pages
- written for the course Seminar on Algorithmic Complexity

- IP = PSPACE
- 2012
- The Paris-Harrington Theorem
- with Ilkka Törmä, 9 pages + 9 pages of python
- written for the course Ramsey Theory and Related Topics

- Known Theorems about Substitutions, and Homemade Proofs for Them
- with Ilkka Törmä, 7 pages
- written for a course on Substitutions

- The Paris-Harrington Theorem
- 2011
- On the Existence of Dense or Sparse NP-Hard Languages
- 6 pages
- written for the course Algorithmic Complexity

- My Master's Thesis:
Classes of Picture Languages Defined by Tiling Systems, Automata and Closure Properties
- 104 pages
- supervisor Jarkko Kari
- University of Turku graduate thesis of the year

- On the Existence of Dense or Sparse NP-Hard Languages
- 2010
- My Bachelor's Thesis:
Fully Polynomial Approximation Schemes for the Knapsack Problem
- in Finnish, "Täysin polynomiaikaisia approksimaatioalgoritmeja kapsäkkiongelmaan"
- 31 pages
- supervisor Olli Nevalainen

- My Bachelor's Thesis:
Fully Polynomial Approximation Schemes for the Knapsack Problem