the top of this page

content
Recruit: Sep. 2009

Term: Apr. 2010 ～ Mar. 2015

Term: Apr. 2010 ～ Mar. 2015

Research Interests: Theoretical Computer Science

Research Topic: Linear Programming Based Techniques for Formula Size Lower Bounds

Kenya has been interested in fundamental objects such as the universe and elementary particles from childhood, and always dreamed of becoming a scientist. Currently, he is interested in the nature of computation and intelligence by clarifying what is computable or incomputable with a computer in a theoretical setting. In particular, he would like to prove the limits of computation mathematically. This would confirm the impossibility of constructing a faster solution for a certain problem, no matter what level of brilliance is brought to bear, and prevent people from making permanent wasteful efforts towards more efficient designs of algorithms. To this end, he will discuss the structural complexity of a formula, which is a fundamental computational model, and develop techniques to prove the limits (lower bounds) against making a smaller formula by utilizing the ideas of linear programming theory.