Dimitri Surinx

Last week I had the second meeting with my advisor Prof. dr. Frank Neven, this time I had to explain to him what I had learned in the last couple of weeks.

I learned about several interesting topics:

• Oblivious simulation of a Turing machine only introduces a quadratic slowdown
• PSPACE completeness of TBQF (something we skipped during our Computational complexity course)
• LADNERS theorem: when then there exist languages that are not in P and not NP-complete.
• The polynomial hierarchy is a generalization of coNP and NP, I proved that if two levels of the hierarchy are equal, then the hierarchy collapses. I also learned that the polynomial hierarchy can also be defined using oracles and alternating Turing machines

I am currently reading about randomized computation.

Time flies by so quickly, the day i started studying at Hasselt University seems just like yesterday, while i already finished my first semester of my third bachelor year.

Last week, the second semester of my third bachelor started. In this semester I have to write my bachelor thesis.

The subject of my bachelor thesis will be: Advanced topics in Computational Complexity.
The topics will be:

• The polynomial hierarchy and alternations
• Randomized computation
• Interactive proofs
• PCP theorem and hardness of approximation
• (optional) Cryptography

I really want to thank my advisor Prof. Dr. Frank Neven, who spend a lot of time helping me select very interesting topics for this thesis.

I will post my progress on this thesis here and hope you will find it as interesting as I do.