Eiji Takimoto, Dr.Eng., Professor

Research Interest

• Online decision making

  We often encounter the problem of decision making in an online framework in which predictions (or prediction-based decisions) and the rewards against them are presented repeatedly. For instance, two-player game, universal coding, investment in a stock market, network routing are typical ones. We develop general methods that perform as well as the optimal strategy.

• Computational learning theory

  Learning can be thought of as a process of inducing some rules as hypotheses behind the observed data. From algorithmic, computational, and information-theoretic points of view, we investigate how much amount of data and time is sufficient or needed to produce good hypotheses, and what combinatorial properties characterize the hardness of learning.

• Complexity theory

  Objects to be computed are typically represented by combinations of predetermined sets of elementary elements. It is of great importance to estimate how large number of elements are required in information processing and hardware design, since the complexity is directly related to the cost. For various representation models such as Boolean formulas and threshold circuits, we develop useful measures that characterize the complexity.