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

Slides:



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

中正國中 特教組長 粘玉芳 校內分機 : /02/21. 下列條件擇一: 一、身心障礙手冊 二、特殊教育學生鑑定及就學輔導會證明.
如何科学认识风水 主讲嘉宾孙百川 揭开神秘的面纱 揭开神秘的面纱 破除迷信的枷锁 破除迷信的枷锁 还易经本来面目 还易经本来面目 学易用易不迷易 学易用易不迷易.
魏晉南北朝的胡漢融和概況. 北朝的漢胡融和 1) 北朝漢胡 融和的概 況 2) 北魏孝文 帝推行的 漢化措施 及影響 北邊民族徙居中原,由 來已久。自曹魏招用胡 兵始,沿邊胡族內徙日 繁。不少胡族君主更傾 心嚮慕漢族文化,大力 促成胡漢的融和。北魏 推行的漢化措施,影響 尤為深遠。
猜谜语 有个小娃娃,真是没 礼貌。 见到小树摇一摇,吓 得树叶哇哇叫。 见到小花逗一逗,摘 去她的太阳帽。 没人和它交朋友,只 好自已到外处跑。
示範課 -- 作文立意. 重溫作文構思課  構思嘗試深化  多角度思考  宜先剖析題目, 運用聯想, 循序漸進擴大範圍, 然後歸納材料, 定訂主題  同學的作品, 反映部分能夠掌握, 主線清晰, 層 層深入, 舉例恰當  但有部分同學只有枝葉, 欠缺主線, 更無中心思 想, 反映立意不足.
幼教人員法律事件探討 ─ 幼兒教育及照顧法 姚其壯 第一章 總則〈第一條至第六條〉 第二章 幼稚園設立及其教保服務 〈第七條至第十四條〉 第三章 幼稚園組織與人員資格及權益 〈第十五條至第二十八條〉 第四章 幼稚權益保障 〈第二十九條至第三十三條〉 第五章 家長之權利與義務 〈第三十四條至第四十條〉
畫面中的兩個人要去參加金融業儲備幹部的面試 活動,你認為誰的面試穿著是正確的? V.S 動動腦 V.S 動動腦 慎重 讓人感到 尊重 輕便 讓人聯想 隨便 畫面中的兩個人要去參加金融業儲備幹部的面試 活動,你認為誰的面試穿著是正確的?
口試準備及口語表達技巧 民國 98 年 2 月 26 日 12:00pm 國立三重高中 陸芳瑜老師 1.
IT 服务与业务发展融合 王维航 北京华胜天成科技股份有限公司 十分钟的悲剧.
高考心理辅导  福建中医药大学  林山  高考是什么?  真有那么 “ 苦大仇深 ” ?  为什么不能是 “ 快乐挑战 ” ?  高考(事) --- 认知(怎么个事 - 压力大小) --- 情绪反应(烦躁、焦虑、害怕 VS 自信、 从容、期盼) --- 行为表现(发挥正常.
蕭文生 中正大學法律系教授兼法學院院長.  壹、前言  貳、司法院釋字第六八四號解釋  參、大學生之受教權  肆、大學自治之範疇  伍、大學生之其他基本權利  陸、救濟管道之改善  柒、結語.
大陸學歷採認相關問題 楊景堯 淡江大學中國大陸研究所. 學歷採認的定義與範圍 廣義的定義 — 承認學歷 狹義的定義 — 具備任職, 任教, 考試資格 範圍 — 高等教育為主 台灣人取得大陸學歷的採認 大陸人取得大陸學歷的採認 外國人取得大陸學歷的採認.
從〈音樂家與職籃巨星〉談 我的人生書寫 王溢嘉 《蟲洞書簡》的寫作因緣 〈音樂家與職籃巨星〉出處:《蟲洞書簡》 1994 看到青春期的兒女 心有所感 寓意 穿越蟲洞旅行 遇到過去的自己 收信人M是我( me ) 寄信人W也是我( Wang ) 寫給兒女 年輕學子 過去的自己.
提昇餐廳供餐品質 及服務滿意度 標竿學習主題 標竿學習計劃排定進度 分析客戶對餐廳供餐滿意度偏低原因:
幾米 作業 1 飛上天空 我想飛上天空 遨遊在無際的天空 美麗的天空 漂亮的天空 這終究只是夢…… (李高仰)
贴着生活写作 慈溪中学 黄宏武.
黄帝内经 内经教研室 王黎.
如何做個稱職的父母 財團法人雲林縣雲萱婦幼文教基金會 王招萍.
学习全国“两会”精神 常州工学院  理学院党总支 2014年3月.
乘势而上再谱发展新篇章 -2012全国两会精神解读
开启新征程 点燃中国梦 开启新征程 点燃中国梦 ——学习、领会2013年全国“两会”精神.
Ch17 績效管理 章首個案:員工績效管理:奇異強迫排名,3M的15%「私釀酒」時間 17.1 績效管理的意義 17.2 績效管理的流程
职官与科举 职官:在国家机构中担任一定职务的官吏,这里面有职官的名称、职权范围和品级地位等方面的内容。
花开有日 芬芳天下 “国培计划(2012)” ——幼儿园骨干教师远程培训项目 山东幼儿园教师8班第4期简报 主办人:张瑞美     
《卖火柴的小女孩》 《海的女儿》 你 认 识 这 些 图 片 的 故 事 吗 《丑小鸭》 《拇指姑娘》 它们都来自于哪位作家笔下?
民主國家的政府體制 我國的中央政府體制 我國中央政府的功能 地方政府組織與功能
台塑石化 與 全國 之 財務分析 :企管二甲、乙 班級 指導 :楊雪蘭 老師 :第六組 組別 組員
各位弟兄姐妹,主內平安! 請將手機關靜音,帶著敬虔的心來到上帝的面前!
成長的腳印 記敘文 課文朗讀.
銷售與顧客關係管理 巫立宇.邱志聖 著.
李白杜甫詩中的"月"和"風" --電腦如何用於古典詩詞鑒賞
第一节 呼吸道对空气的处理.
十面“霾”伏 湖南长沙民政职业技术学院“思政”第九组 组员:李亮亮 许静 赵凯丽 何敏 张艳欣 付幻菱 陈京萍 王诗雨.
如何对付脏空气.
語文強化系列 ~修辭大觀~ 創意文句‧生動鮮明 康軒6上語文特寫.
20、豆花庄的小家伙们.
CH11 心理疾病 李志鴻.
近代的中华民族可谓多灾多难,饱受了西方列强的侵略。在前两课的学习中,我们已经了解了西方列强发动的两次侵略战争,下面我们来简单地回顾一下,这两次战争的名字叫什么?侵略者分别是谁? 在中国近代史上,侵略中国时间最长、危害最大的是哪个国家?
教師執行計畫案聘任助理說明會 (勞務型、學習型申請方式說明)
华 夏 之 祖 第 3 课.
法學緒論第六單元:法律適用 設計課程︰ 財經法律系 --楊東連 法學緒論-6.
第一節 進入職場前的準備 第二節 培養求職能力 第三節 當前的就業趨勢 第四節 新世代工作地圖
水腫的原因 徐淑娟護理師 PM.
中国未成年人法制安全课程 雾霾哪里来? 初中段 第七讲.
学生培养的过程性评价.
9理直氣和—記敘文 說理如強硬,則不易被接受,以故事方式來激發反思,是比較不傷和氣而且高明的技巧。
CH1 . 集 合 与 命 题.
Ch19 創業精神 管理學:整合觀點與創新思維3/e.中山大學企管系 著.前程文化 出版.
以考试说明带动二轮复习 福州第三中学 张璐.
歡迎第一次來參加聚會的 福音朋友與弟兄姊妹
何俊賢教學資料.
跨越海峡的生命桥.
SAT and max-sat Qi-Zhi Cai.
What have we learnt from
Interactive Proofs 姚鹏晖
Randomized computation
Computational Complexity 计算复杂性
教學原理.
Interactive Proofs 姚鹏晖
Boolean circuits 姚鹏晖 助教: 刘明谋 答疑时间: 周四 2pm-4pm, 计算机科学与技术楼 502
An Introduction to Communication Complexity
2019青春設計節 第二次籌備會議.
國民年金 np97006.
Polynomial Hierarchy 姚鹏晖
工程數學 Chapter 14 Complex integration indefinite integral 楊學成 老師.
第6课 我是共和国的公民.
请大家起立,练习“站桩”:两手平伸,两脚与肩间宽,双脚尽量下蹲,上身保持平直。
愛永不止息 VS. 恩賜會止息 Why? 現在 主再來 所知、所見有限 (預言也有限) 面對面、全知道 (不再需預言)
105-1 Data Structure Homework 4
Presentation transcript:

Boolean circuits 姚鹏晖 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 Complexity class P/poly, P vs. P/poly CKT-SAT is NP complete Uniformly generated circuits Turing machines with advice.

NP vs P/poly

NP vs P/poly

EXP vs P/poly

Upper bounds imply lower bounds

Existence of hard functions

Existence of hard functions

Nonuniform Hierarchy Theorem

NC and AC

NC and parallel algorithms

P-completeness

Circuit lower bounds: Complexity theory’s Waterloo

ACC0

Frontiers of Circuit lower bounds

Other approaches to circuit lower bounds Decision tree complexity Ch 12 Communication complexity Ch 13 Circuit lower bounds Algebraic complexity Ch16 Proof complexity Ch15

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