- Small-depth circuits for Turing machines with few reversals
- Project Year:
2019
- REU Student (s):
Kyle Hess | University of California-Los Angeles CA
- Student 1 Institution:
University of California-Los Angeles
- Project Mentor:
Periklis Papakonstantinou
- Project Mentor Area:
Management Science and Information Systems
- Project Abstract:
We studied a new method for simulating T(n)-time-bounded Turing machines
by unbounded circuits with low depth and size polynomial in T. Our construction
offers lower depth circuits than the ones by Ryan Williams in the case
that the total number of reversals of every tape head is less than O(T=logT).
This continues a research direction of Borodin to study the connections between
simultaneous Turing machine time and space complexity and simultaneous
circuit size and depth complexity, which is heavily connected to the research of
Hopcroft, Paul, and Valiant on time and space. Finally, reducing the depth of circuits for Turing machines has applications to parallelizing sequential computations, as discussed in Ryan Williams' aforementioned paper.
