题目：Communication interruption between an AND－OR tree and its leaves
主讲人：东京都立大学， Toshio Suzuki教授
时间：2022年1月14日下午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（鈴木 登志雄），东京都立大学教授，BET9十年信誉玩家首选网址数学系，博士生导师，研究方向为数理逻辑，可计算性理论，是日本算法随机领域知名专家。主持日本JSPS科学研究基金5项，在DAM，IPL，APAL，TCS等杂志发表SCI论文40余篇．
