Tokyo Institute of Technology, Tokyo, Japan, September 23, 2016

This workshop is held at the Tokyo Institute of Technology, Ookayama campus, on the 10th floor of West Building 8E (number 19, in the centre of the map). Participants do not need to register.

Ookayama Station is located near the main gate of the campus.

Schedule

13:30-14:00 Weiguang Peng (Tohoku University), The Eigen-distribution for Multi-branching Trees.

Game tree is a simple model to compute Boolean functions. To eliminate the reluctant assignments in computing the value of root, Liu an Tanaka (2009) defined the concepts of i-set (i=0,1) and E^i-distribution. They showed that for any uniform binary tree, the E^1-distribution is the unique eigen-distribution with respect to deterministic algorithms. In this talk we will consider the equivalence of E^i

14:00-14:30 Shohei Okisaka (Tohoku University), The eigen-distribution of game trees with leaf cost function.

Saks and Wigderson introduced leaf cost functions to prove a lower bound on the randomized complexity of game trees. We extend our previous results to the game trees with leaf cost function. In this talk, we will explain the proof of our results.

14:30-15:00 Keita Yokoyama (JAIST), Problem Session.

15:30-17:45 Stephen G. Simpson (Vanderbilt University)
CTFM Companion Lecture: A tutorial on degrees of unsolvability.
Abstract
Slides