Interactive Proofs 姚鹏晖

Slides:



Advertisements
Similar presentations
导数 导数 一、主要内容 微分 第二章 习题课 二、典型例题. 求 导 法 则求 导 法 则 求 导 法 则求 导 法 则 基本公式 导 数 导 数 高阶导数 一、主要内容 微 分微 分 微 分微 分.
Advertisements

香港學校訓導人員協會 天水圍區聯絡網主辦 優質教育基金贊助 天水圍聯校 1999 領袖生培訓計劃.
飲料備製 ( 作業十 ) 組員 : 9A0M0009 林昆樺 9A0M0026 李元盛 9A0M0031 林殷正 ( 組長 ) 9A0M0046 邱于倫 9A0M0048 林裕嘉 9A0M0054 巫紀樺 指導老師 : 葉佳聖.
常用食物含水量表 食物单位原料重 g 含水量 ml 大米饭一碗 (170g) 大米粥一碗 (500g) 面条一碗 (170g) ( 汤另计 ) 蒸蛋糕一碗 (170g) 5025 藕粉 牛奶
1. 一. 人口分布  全球約十分之九的人口集中在北半球。  三大人口稠密區:亞洲東南半壁、歐洲、北美洲東部  季風亞洲人口占全球一半。  人口稀少區 太乾-北非撒哈拉沙漠 太濕-亞馬孫、剛果雨林 太冷-西伯利亞、南極 崎嶇-東非、青藏高原 2 台灣人口分佈狀況 (04 : 43) p.83.
题目:高血压病人的护理 系 别 :医学系 年级专业 : 06 护理 学生姓名 :陈恩琪 指导教师 : 林力敏老师 实习医院 :顺德中西医结合医院.
三信家商「 105 學年度」 升學進路暨報名作業說明會 教務處實研組 教務處 實研組 日期︰ 104 年 10 月 19 日 時間: am 10:00~11:50 地點:教學行政大樓 7F 講堂.
幾米 作業 1 飛上天空 我想飛上天空 遨遊在無際的天空 美麗的天空 漂亮的天空 這終究只是夢…… (李高仰)
贴着生活写作 慈溪中学 黄宏武.
学习全国“两会”精神 常州工学院  理学院党总支 2014年3月.
乘势而上再谱发展新篇章 -2012全国两会精神解读
开启新征程 点燃中国梦 开启新征程 点燃中国梦 ——学习、领会2013年全国“两会”精神.
人事服務課程 報告單位:人事室.
审计案例研究 第一讲 辅导教师 周桂芝.
十五條佛規 後學:張慈幸
各位弟兄姐妹,主內平安! 請將手機關靜音,帶著敬虔的心來到上帝的面前!
二十世纪外国文学专题 章丘电大 李颜.
第一节 呼吸道对空气的处理.
證道: 我是羊的門,我是好牧人 講題:「耶穌說:”I Am”『我是…』」之(四) : 講員: 梁淑英牧師
十面“霾”伏 湖南长沙民政职业技术学院“思政”第九组 组员:李亮亮 许静 赵凯丽 何敏 张艳欣 付幻菱 陈京萍 王诗雨.
佛教大雄中學 2007年度香港中學會考 放榜輔導 升學及就業輔導組.
如何对付脏空气.
高澱粉蔬菜是主食 文字取材: 蘇逸晴.
「讀一讀 好醒目」 家長講座 教育局 課程發展處 2011年4月.
教師執行計畫案聘任助理說明會 (勞務型、學習型申請方式說明)
水腫的原因 徐淑娟護理師 PM.
中国文学 王馨.
105年推甄及登記分發說明會 教務處 註冊組課務組.
台北縣三峽鎮立圖書館 陳銘泰 連原德 許誌真 紀寶涵 邱品沛 周映豆.
中国未成年人法制安全课程 雾霾哪里来? 初中段 第七讲.
青春期男生女生交往.
如何準備新聞採訪 國立台北大學中文系 老師:簡陳中
复习 1. 注意最值与极值的区别. 最值是整体概念而极值是局部概念. 极大值可能小于极小值,极小值可能大于极大值.
学生培养的过程性评价.
[聚會時, 請將傳呼機和手提電話關掉, 多謝合作]
幼兒動作發展與體能遊戲 二幼一甲 梁素嬌.
首都师范大学欢迎你! 2014年秋季学期开学典礼.
爱乐活 ——高中生命教育.
Chap 8 空间复杂度 可根据 提供的PPT素材+参考以前同学的报告, 修改成为有自己见解的讨论报告 建议: 底色用浅色(象牙白, 浅黄, 白色等) 适合色盲 色弱 观众 字体颜色选择余地大 在投影机 效果差时 也还能能看见.
金属学与热处理 主讲: 杨慧.
第三章 学习理论 主讲人 李 荟 平顶山学院.
复习 1. 微分中值定理的条件、结论及关系 费马引理 拉格朗日中值定理 罗尔定理 柯西中值定理 2. 微分中值定理的应用 关键:
北京师范大学体育与运动学院院长、博士生导师 国家基础教育课程教材专家工作委员会委员 全国体育教学指导委员会副主任 毛振明
[聚會時,請將傳呼機和手提電話關掉,多謝合作]
組員:蔡典龍4970E027 蕭積遠4970E026 王建智4970E050 李雅俐4970E025 賴品言4970E054
“物理照耀世界在中国”活动工作总结.
[聚會時,請將傳呼機和手提電話關掉,多謝合作]
何俊賢教學資料.
簡介 宜蘭市衛生所 簡介
SAT and max-sat Qi-Zhi Cai.
Randomized Algorithms
What have we learnt from
耆康會長者中央議會 <<長者與社會參與>>計劃培訓
Randomized computation
Computational Complexity 计算复杂性
Interactive Proofs 姚鹏晖
使徒行傳.
Boolean circuits 姚鹏晖 助教: 刘明谋 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502
An Introduction to Communication Complexity
Boolean circuits 姚鹏晖 助教: 刘明谋 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502
2019青春設計節 第二次籌備會議.
國民年金 np97006.
第三屆高中職智慧鐵人創意大賽 第一屆亞洲邀請賽 學生說明會
幼兒發展學習的評量與輔導---- 第四章—收集資料
Polynomial Hierarchy 姚鹏晖
新竹縣108年第一次鑑定安置 學前心評教師職前說明會
第6课 我是共和国的公民.
关于复杂性理论的一点探讨 孙广中
请大家起立,练习“站桩”:两手平伸,两脚与肩间宽,双脚尽量下蹲,上身保持平直。
105-1 Data Structure Homework 4
Presentation transcript:

Interactive Proofs 姚鹏晖 Email: pyao@nju.edu.cn 助教: 刘明谋 liu.mingmou@smail.nju.edu.cn 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502 http://tcs.nju.edu.cn/wiki/index.php/Main_Page

What we have learnt Deterministic TM and complexity classes P, PSPACE, EXP Nondeterministic TM and complexity classes NP, NEXP Polynomial hierarchy Probabilistic Turing machines and complexity classes BPP, RP, coRP, ZPP 回顾每一个item,定义,定理,证明

Definition of NP

Definition of NP

Deterministic interactive proofs

Deterministic interactive proof systems

Deterministic interactive proof systems

Deterministic interactive proof systems

Probabilistic verifier

Basic properties of IP

Interactive proofs for graph nonisomorphism

Interactive proofs for graph nonisomorphism

Quadratic nonresiduosity

Interactive proofs for graph nonisomorphism

Zero-knowledge proofs

Zero-knowledge proofs for GI

Public coins and AM

Facts on MA and AM

Multiprover interactive proofs

Multiprover interactive proofs

Two-prover one-round game

Two-prover one-round game and 3SAT

CHSH game The God does not play dice. Albert Einstein Bell’s Inequality

GNI and AM

Hash functions

Set lower bound protocol

Set lower bound protocol

Homework 或放到计算机科学与技术楼502门口信封 (中英文不限) Chapter 7. Exercise 7.1,7.3,7.5,7.6,7.9 作业发送给助教刘明谋 liu.mingmou@smail.nju.edu.cn 或放到计算机科学与技术楼502门口信封 (中英文不限) 交作业时间:11月29日10:00前