Randomized computation

Slides:



Advertisements
Similar presentations
1 曾老師、各位同學大家好 ! 首先自我介紹 ; 個人聯合大學電機系 畢業,服完兩年兵役後, 75 年開始就 業 ; 四年內換了幾個工作, 79 年創立貿 特科技, 90 年、 91 年分別於大陸寧波 與昆山設立特一電子與柏特電子,經 歷 20 年的工作磨鍊,今天事業上算是 穩定、成熟 ! 承蒙曾老師看重,利用一.
Advertisements

中正國中 特教組長 粘玉芳 校內分機 : /02/21. 下列條件擇一: 一、身心障礙手冊 二、特殊教育學生鑑定及就學輔導會證明.
示範課 -- 作文立意. 重溫作文構思課  構思嘗試深化  多角度思考  宜先剖析題目, 運用聯想, 循序漸進擴大範圍, 然後歸納材料, 定訂主題  同學的作品, 反映部分能夠掌握, 主線清晰, 層 層深入, 舉例恰當  但有部分同學只有枝葉, 欠缺主線, 更無中心思 想, 反映立意不足.
幼教人員法律事件探討 ─ 幼兒教育及照顧法 姚其壯 第一章 總則〈第一條至第六條〉 第二章 幼稚園設立及其教保服務 〈第七條至第十四條〉 第三章 幼稚園組織與人員資格及權益 〈第十五條至第二十八條〉 第四章 幼稚權益保障 〈第二十九條至第三十三條〉 第五章 家長之權利與義務 〈第三十四條至第四十條〉
畫面中的兩個人要去參加金融業儲備幹部的面試 活動,你認為誰的面試穿著是正確的? V.S 動動腦 V.S 動動腦 慎重 讓人感到 尊重 輕便 讓人聯想 隨便 畫面中的兩個人要去參加金融業儲備幹部的面試 活動,你認為誰的面試穿著是正確的?
口試準備及口語表達技巧 民國 98 年 2 月 26 日 12:00pm 國立三重高中 陸芳瑜老師 1.
IT 服务与业务发展融合 王维航 北京华胜天成科技股份有限公司 十分钟的悲剧.
高考心理辅导  福建中医药大学  林山  高考是什么?  真有那么 “ 苦大仇深 ” ?  为什么不能是 “ 快乐挑战 ” ?  高考(事) --- 认知(怎么个事 - 压力大小) --- 情绪反应(烦躁、焦虑、害怕 VS 自信、 从容、期盼) --- 行为表现(发挥正常.
蕭文生 中正大學法律系教授兼法學院院長.  壹、前言  貳、司法院釋字第六八四號解釋  參、大學生之受教權  肆、大學自治之範疇  伍、大學生之其他基本權利  陸、救濟管道之改善  柒、結語.
提昇餐廳供餐品質 及服務滿意度 標竿學習主題 標竿學習計劃排定進度 分析客戶對餐廳供餐滿意度偏低原因:
第八課 謝 天. 第八課 謝 天 作者主旨文章作法 民國 陳之藩 謙卑感 恩,功 成不居 以「謝天」的傳統觀念 為中心,經由疑惑、思 索、領悟三個層次的敘 述,賦予新的意義 ★題目含義:表示對很多「人」的感謝。
蔬菜大觀園 V.S 大家來種菜 蔬菜的外觀及分類  蔬菜是我們常吃的食物,蔬菜的外觀形狀不 同,有各種不同的顏色、形狀、氣味等,嚐 起來的味道也不相同。  蔬菜的營養價值不盡相同,可實用的部位也 不同,有的是根、有的是莖、有的是葉、有 的是花、有的是果實,還有的是種子。  依據蔬菜種類和食用部位的不同,可以將蔬.
社工之路的通行證 --- 社工師證照 考試心得分享 東吳大學社工系碩一 呂錦綸. 一、考前準備 閱讀主流老師的書籍、掌握各科概要。 閱讀主流老師的書籍、掌握各科概要。 重視概念性的知識,打好基礎是很重要低 ~ 重視概念性的知識,打好基礎是很重要低 ~ 是必備讀物 ! 是必備讀物 ! 勤作考古題,參考當年度碩士班考試及高.
政府的权力:依法行使. 政府的权力:依法行使 重庆“最牛钉子户”事件 九龙坡区法院一名张院长称,法院已组织6次调解,有时1天就有2次调解。3月28日下午,九龙坡区委书记郑洪还专门接待吴苹3小时。1日,在法院组织下,拆迁双方基本达成口头协议,今天下午,双方签字生效。按协议,吴苹选择了异地实物安置方案,开发商将其在沙坪坝开发的一处门面房,按同样面积交付吴苹,吴同意此方案.
第八課 馮諼客孟嘗君 謀職達人 來也.
心理学辅导.
幾米 作業 1 飛上天空 我想飛上天空 遨遊在無際的天空 美麗的天空 漂亮的天空 這終究只是夢…… (李高仰)
蔬菜大觀園V.S大家來種菜 高雄市楠梓區翠屏國中小教師 林珮如
“腸”保安康 現代人的腸胃保健.
那一段「詩聲戀」的日子 孟令今老師.
獨立國家國協 1.地形 2.氣候 3.產業.
綜合活動領域 教學分享.
國小學童財金生活教育 主講人: 秘書長陳琬惠 社團法人中華民國財金智慧教育推廣協會.
诚信人生 ---高二(2)班主题班会.
兩岸融合教育之議題: 以東莞台商子弟學校為例
航向未來 飛揚國際 —關於華航與長榮的財務報表 指導老師: 組員:張甄芸 4A 鄭雅華 4A070079
学习全国“两会”精神 常州工学院  理学院党总支 2014年3月.
乘势而上再谱发展新篇章 -2012全国两会精神解读
开启新征程 点燃中国梦 开启新征程 点燃中国梦 ——学习、领会2013年全国“两会”精神.
世界史.
面对苦难 (约翰福音15:18-16:4) 2/22/15 我们不属世界,神从这世界中拣选了我们,却没有为我们另设一处“世外桃源”,乃是让我们住在地上,以他的信实为粮,以他的生命为光。既然在这被罪玷污的世界中,就会有苦难仇恨,然而它们不能打倒我们,因为它们 无目的 无缘故 无胜算 在世上我们虽有苦难,也可以放心,因为耶稣已经胜了世界。
   時間 國立臺南師範學院數學教育系     謝  堅.
如果你没法阻止战争,那你就把战争的真相告诉世界
程焕文 中山大学资讯管理学院 2015年10月17日 山东·临沂
102學年度第二學期 208家長座談會 歐陽美慧.
小綠葉蟬的『祕蜜』~ 蜜香烏龍茶.
個人投資理財與策略 富蘭克林:邱良弼.
第六章 中国公务员制度 干部 VS 公务员.
穿越迷雾,读懂全球化经济本质 谈美国次贷危机与人民币升值问题.
教育部 試辦中小學 教師專業發展評鑑基本概念 台中教育大學 徐照麗.
大陸教育基本現況認識 楊景堯 淡江大學中國大陸研究所.
第三章 魏晉南北朝的分合.
华东师范大学第二附属中学 作者:高二(7)班 顾韬 景琰杰 指导教师:张成鹏
移民與文化--鄉愁的想像 王婉甄.
性別平權.
各位弟兄姐妹,主內平安! 請將手機關靜音,帶著敬虔的心來到上帝的面前!
第一节 呼吸道对空气的处理.
十面“霾”伏 湖南长沙民政职业技术学院“思政”第九组 组员:李亮亮 许静 赵凯丽 何敏 张艳欣 付幻菱 陈京萍 王诗雨.
如何对付脏空气.
教師執行計畫案聘任助理說明會 (勞務型、學習型申請方式說明)
第一節 進入職場前的準備 第二節 培養求職能力 第三節 當前的就業趨勢 第四節 新世代工作地圖
水腫的原因 徐淑娟護理師 PM.
中国未成年人法制安全课程 雾霾哪里来? 初中段 第七讲.
学生培养的过程性评价.
債券型基金回顧與展望 中華信用評等 資深協理 蔡東松 2005年1月25日.
何俊賢教學資料.
SAT and max-sat Qi-Zhi Cai.
Randomized Algorithms
What have we learnt from
Interactive Proofs 姚鹏晖
Computational Complexity 计算复杂性
Interactive Proofs 姚鹏晖
Boolean circuits 姚鹏晖 助教: 刘明谋 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502
An Introduction to Communication Complexity
Boolean circuits 姚鹏晖 助教: 刘明谋 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502
2019青春設計節 第二次籌備會議.
Polynomial Hierarchy 姚鹏晖
第6课 我是共和国的公民.
105-1 Data Structure Homework 4
Presentation transcript:

Randomized computation 姚鹏晖 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 Boolean circuits and complexity class P/poly Polynomial hierarchy Probabilistic Turing machines and complexity classes BPP, RP, coRP, ZPP BPP algorithms for Median, PRIMES, PIT, PERFECT MATCHING Error reduction General random choices vs. fair random coins 回顾每一个item,定义,定理,证明

Unified definitions 概括这些的区别, what is coBPP?

Unified definitions

Unified definitions

BPP vs. P/poly 这个 r_0 很难找,所以这个证明并不表明BPP 存在多项式时间算法

BPP vs. PH

BPP vs. P/poly

BPP vs. P/poly

Hierarchy theorem and complete problems? Syntactic 存在,任意 Semantic 不能用纯逻辑语句来表示

Randomized reductions

Randomized space-bounded computation

Random walk on graphs

Random walk on graphs

Random walk on graphs

Randomness-efficient repetitions: a glimpse to derandomization

Randomness-efficient repetitions: a glimpse to derandomization

Hardness vs. Randomness

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前