详细内容 当前位置:首页 > 科学研究 > 学术交流
【明理讲坛】东京都立大学鈴木登志雄教授讲座
发布时间:2022-01-13【告诉好友】 【关闭窗口】

题目:Communication interruption between an AND-OR tree and its leaves

主讲人:东京都立大学, Toshio Suzuki教授

时间:2022114日下午14:00-16:00

ZOOM 会议ID: 996 1657 1217

密码 272659

You can join the meeting at

https://zoom.us/j/99616571217?pwd=WWRlMWYxWXJROVJObnI4Mjh2Y215Zz09

摘要:We investigate a variant of an AND-OR tree where leaves are connected to internal nodes via communication channels, and these channels possibly have high probability of interruption.We let depth-first communication denote the following protocol:once an algorithm make a query to a leaf then it continuesto make queries to that leaf until return of an answer.We give a sufficient condition for an interruption probabilitysetting having the following property. For any independent andidentical distribution on the truth assignments (probability isassumed to be neither 0 nor 1), any depth-first search algorithmthat performs depth-first communication is not optimal.We give a concrete example of such interruption probabilitysetting by means of the Riemann zeta function. Our result makessharp contrast with the counterpart on the usual AND-OR tree(Tarsi) that optimal and depth-first algorithm exists.

欢迎全校师生参加!

报告人简介:Toshio Suzuki(鈴木 登志雄),东京都立大学教授,理学院数学系,博士生导师,研究方向为数理逻辑,可计算性理论,是日本算法随机域知名专家。主持日本JSPS科学研究基金5项,在DAM,IPL,APAL,TCS等杂志发表SCI论文40

      
      
【关闭窗口】