General Information
| Student: | Kyle Hess |
|---|---|
| Office: | CoRE |
| School: | University of California Los Angeles |
| Adviser: | Periklis Papakonstantinou |
| Project: | Time Versus Space |
Project Description
Together with part of the Czech group I am working working on a project with our advisor Periklis Papakonstantinou.
Progress
Week 1
I didn't get much done research-wise this week as I spent it getting oriented and settled in to the new environment at Rutgers.
Week 2
This week I gave a presentation on the research project I would be working on. Since I initially was working on the depth irreducibility hypothesis. You'll see my presentation was on that.
I also read half of a 66 page paper on a new model of parallel RAM without bit operations in which the authors were able to prove a seperation from polynomial time. It was my intent at this point to prove the depth irreducibility hypothesis for this weak version of parallel computation, so I paid good attention to studying every last detail of the model so that I would be able to prove things about it well.
Late this week, I also met with my advisor, Periklis Papakonstantinou, for the first time (there were some delays in meeting him earlier). I also met with some of his other students working on the relation between time and space. Since I preferred working in a group, Periklis transferred me to work with them on this problem. They caught me up on their new method for designing small uniform circuits for deterministic time machines and I read a paper on Ryan Williams which achieved similar results through seemingly different methods.
Week 3
This week, we met up with Periklis again, where I was to present the main results in Ryan Williams' paper. However, while looking over it again, I found what seemed a flaw in his argument where he seemed to equate universal quantifiers with existential ones.
Later, we tried to salvage the result and see if it could be used to improve our results, but we weren't able to come up with anything. We then tried to improve a different result from the paper which simulated time-bounded deterministic machines by low-space alternating machines with few alternations. We thought that a component of the algorithm where $\log(T)$ steps of the deterministic machine were simulated without alternations could be made more efficient in order to allow it to simulate more steps.
Sadly, after multiple attempts at solving this, we still weren't able to improve upon the efficiency of this algorithm. Pavel suggested using some sort of Savitch-like recursion, but this required either high amounts of space or extra alternations, and I suggested the use of pebbling, but this was hindered by the fact that we would have had to re-guess the input each time.
Week 4
This week, I received confirmation from another professor that Ryan Williams' result was probably flawed, and later found even more evidence: as stated, his result would imply that semi-unbounded circuits are equivalent to unbounded ones. In the circuit complexity world, this is highly unlikely.
I also looked into the difference between our oblivious circuit simulation of time-bounded machines and Ryan Williams' circuit to see if we could combine the two results to get an even stronger one. Sadly, I found that Ryan Williams actually used a nearly equivalent method to ours, only obscured by some unecessary middle steps. This spelled the death knell for proceeding any further with the methods we had used so far.
However, Jakub had an ingenious idea: prove a space-bounded simulation for a time-bounded machine by assuming at the very least a bound on the number of reversals. This way, we could at least get some sort of result.
Week 5
I did not do any research the beginning of this week since I had to go home for a doctor's appointment, but when I came back I found the others had been busy coming up with some methods for efficiently simulating time and reversal bounded one-tape turing machines.
They ultimately failed to come up with a simulation that brought about new results, but with some slight tweaking I believe I found a way to improve what they had so far to get low depth circuits for any time-bounded turing machine with one tape. After some work, I was not able to immediately extend the result to multiple tapes, and I am afraid this is not possible. However, I am hopeful that after presenting it to the others they will have more ingenious ideas that can get us around the major roadblocks I found.