General Information
| Student: | Jakub Pekárek |
|---|---|
| Office: | CoRE 407 |
| School: | Computer Science Institute of Charles University in Prague |
| Adviser: | Periklis Papakonstantinou |
| Project: | Time Versus Space |
| 2017 project | |
| 2016 project | |
| MAW (my academic webpage) |
Thanks to Martin Loebl!
the Czech Group
I am here as a senior member of the group of Czech students
The Czech group consists of Pavel K🍩blich Dvořák (our coordinator and benevolent ruler), Andrej Dedík, Aneta Šťastná, Jan Petr, Jan Soukup, Lukáš Ondráček, Mikhail Beliyeu, Petr Chmel, Petra Pelikánová, Radim Předstíraný, and myself.
Project Description
Together with part of the Czech group I am working working on a project with our advisor Periklis Papakonstantinou.
Progress
Week-1
The first week was all about meetings with mentors and starting up our research by writing articles and playing around with the basic definitions and concepts to obtain intuition and undestanding of the questions of interest.
Week-2
We made this awesome presentation and established the most important functionality of our webpages.
In terms of our research, we have explored some options of various transitions between turing machines and circuits. Since these models work in a diametrically different way, lots of technical details influence the relations between time and space, which we are trying to handle with atmost care and precision. We are trying to obtaing a sufficiently good starting point to launch our pebbling attack compressing space into lots of time.
We also solved all puzzles on the back side of a cereal box we bought a few days ago. There was a maze and one of our secondary goal is a maze-related problem, so it might count as research.
On Friday, we met with Periklis for the second time. He agrees that all our cereal-box solutions seems valid, but asked for more in-depth analysis to be presented to him next week to be sure. If we find time while he is here, he'll also listen to our oblivious circuit design with bounded degeneracy which we managed to pull off earlier.
Week-3
We have spent a few days revising our partial results to see where we stand. According to Periklis, some of it is already publishable, so we want to make sure everything is firmly in place before we venture onwards.
By the end of the week we have confirmed that our results are correct. However something else is flawed. We have found a mistake in a paper we were trying to improve/adjust for our purposes. It is a paper from Princeton Institute of Advanced Study, so finding a mistake in something like that as quite worth mentioning in a resume.
Week-4
On Monday, our sincere efforst to do research were smothered by visit of Bell Labs. After that we tried to fix the flawed paper, but the mistake is too severe.
We have managed to completely unpack and analyze several constructions to turing- machine conversion, alternation trade-offs and circuit compressions. Our hope was to find a way to reconcile these distinct creatures and aplly them simultaneously to a single computation model. We found out, that very deep all of the constructions work the same way, so putting several together doe not produce anything new. This was a shocking discovery as there is nothing previously known sugessting this is even possible.
After this discovery we have reoriented our efforts towards other more exotic ways of obtaining a result of the flavor we want.
Week-5
In the beginning of hte week, we have sucessfully applied our new approach to derive several interesting results. Later on we spent a lot of time tweaking our constructions under difeerent conditions, exploring different types of consequences.
Though these results are of a different type then intended, for single tape machines, the methods used are in themselves of intererst. We would like to generalize our results to multitape computations, however multitape data mechanics quite incompatible with our methods, as witnessed by trivial conterexamples.
Week-6
We continued to explore other ways to express structural complexity of computation. Our goal is to limit the overall amount of problematic behavior of the machine and allow enough problematic steps to go through without failing to leave out only specificly behaving types of computations.
Week-7
We compiled the results we managed to achieve so far and reviewed our methods and constructions applying the new points of view and tools developed on the way. We also established a battle plan to deal with the remaining problems after the end of the program.