《NCTCS2017陆品燕教授特邀报告》由会员分享，可在线阅读，更多相关《NCTCS2017陆品燕教授特邀报告（49页珍藏版）》请在金锄头文库上搜索。
1、理论计算机科学 一门交叉学科 陆品燕 理论计算机科学研究中心 上海财经大学 理论计算机 理论计算机 数学 经济学 科学 技术 理论计算机 理论计算机 数学 经济学 科学 技术 数学 理论计算机科学是数学的一个分支 数学的三个要素 定义 定理 证明 1936年 图灵关于图灵机的论文 图灵机 可计算与不可计算 希尔伯特第十问题 1900年国际数学家大会 23个问题 计算复杂性 NP vs P 世界七大数学难题之一 千禧年大奖难题 2006年国际数学家大会 NP完全理论 计算问题的分类 图同态问题 图同态问题 图同态问题 图同态问题 图同态问题 图同态问题 二分定理 Dyer Greenhill 0
2、0 图同态的计数问题的计算复杂性分为 如果目标图的每个连通分支都是带自环的完全图或者 完全二分图 那么该计算问题是多项式时间可解的 对于所有其他情况 该计算问题是 P完全的 图同态计数问题的代数表达 1 2 H vi vj H 011 101 110 3 coloring 带权重的图同态问题 1 2 H vi vj H 211 121 112 Spin systems in Statistic Physics Graphical models in machine learning partition function Bulatov Grohe 05 二分定理 负权和复数权重 11 1 1
3、was an obstacle for while Quantum spin systems Determinant vs permanent Surprising tractable families due to algebraic cancelation 1 2 H vi vj 负权和复数权重 Goldberg Grohe Jerrum Thurley 08 实数 权重的二分定理 11 1 1 是多项式时间可计算的 Cai Chen L 10 复数权重的完整二分定理 本人应丘成桐先生邀请在第五届国际华人数学家 大会上作一个45分种的特邀报告 理论计算机 理论计算机 数学 经济学 科学 技
4、术 科学 科学发现的基本方法 实验 推理 计算 自然科学与理论计算机的交叉 生物信息学 量子信息与量子计算 统计物理 FKT算法 三位统计物理学家Fisher Kasteleyn Temperley 计算平面图的完美匹配数目 统计物理中双原子 分子 Diatomic molecule 结构的配分函数 基于代数方法的多项式时间算法 全息算法 图灵奖得主Valiant教授在2004年提出的新的设计 多项式时间算法的方法 通过一个全息规约 本质上是一个基变换 把其 他问题规约到平面图上的完美匹配数 然后通过FKT算法求解 从艺术到科学 Cai L STOC 2007 Holographic Algo
5、rithms from Art to Science 证明了一系列数学刻画定理 通用的设计全息算法的系统方法 American Scientist 专题报道 相变现象 微观参数的连续变化引起宏观状态的突变 水的三态 物质的磁性等等 相变现象也在计算问题中出现 可满足性问题 SAT 二状态自旋系统的配分函数 Li L Yin 2012 理论计算机 理论计算机 数学 经济学 科学 技术 计算经济学 经济学中的计算问题 计算视角下的经济学问题 经济学视角下的计算问题 Turing s invisible hand 计算经济学成为一个重要的研究领域 理论计算机 人工智能 和经济学 旗舰会议 EC WI
6、NE SAGT 著名博客站点 Turing s invisible hand 下周的ADL讲习班 定价 拍卖 商业模式 定价是最常用最普遍的 对买家来说比较简单 对卖家来说是可预测的收入 什么时候需要拍卖 不知道如何定价 对于买家的估值与市场需要没有足 够的信息 利用买家之间的竞争获得更大的收益 拍卖规则的设计 经济学的传统方法 诺贝尔奖得主Myerson的最优拍卖理论 目标 设计一个拍卖策略最大化期望收益 假设 竞标人的估值取自一个已知的分布 最优拍卖策略非常依赖于具体的分布 没有分布 也就不知道怎么设计最优拍卖策略 甚至不知道怎么比较两个拍卖机制的优劣 在所有可能的输入上都好 平均性能比较
7、好 不可能 不知道分布 竞争分析法 Competitive analysis 把拍卖的收益与一个经济上有意义的基准量 benchmark进行比较 在最坏情况下来衡量一个拍卖机制的好坏 竞争比 Competitive ratio 一个拍卖机制A相对于基准量 的竞争比 max Rev 数字产品的拍卖 数字产品可以无限量生产 没有额外成本 比较的基准是最优统一定价时的收益 Goldberg Hartline Wright 01 O 1 Feige Flaxman Hartline Kleinberg 05 15 Alaei Malekian Srinivasan 09 4 68 Fiat Goldb
8、erg Hartline Karlin 02 4 Goldberg Hartline 03 3 39 Hartline McGrew 05 3 25 Ichiba Iwama 10 3 12 Goldberg Hartline Karlin Saks 04 2 42 Chen Gravin L 14 2 42 Turing s invisible hand 的博 文 理论计算机 理论计算机 数学 经济学 科学 技术 理论与应用 很多来源于理论研究的算法 概念等在应用中产 生了巨大的作用 是新技术的重要基石 差分隐私 Differential Privacy 很多启发式的算法在应用中首先被发展起
9、来 之 后理论解释了其所以然 并提供新的视角 信念传播算法 Belief Propagation 的严格化 差分隐私 Differential Privacy 敏感数据的有用性和隐私性 差分隐私 Dwork 2006 On Optimal Differentially Private Mechanisms for Count Range Queries Zeng Cai L Naughton 2013 信念传播 Belief Propagation BP算法在统计物理和机器学习中被广泛应用 是一个启发式算法 不保证收敛性和正确性 通过修正计算树来保证正确性 通过相关性衰减技术分析收敛性 相关性
10、衰减技术 边覆盖的计数问题 Lin Liu L SODA 2014 单调CNF的解计数问题 Liu L SODA 2015 二分图独立集的计数问题 Liu L STOC 2015 图染色的计数问题 L Yang Zhang Zhu SODA 2017 机器学习与理论 PAC学习模型 SVM学习算法 在线学习算法 Combinatorial Multi Armed Bandit with General Reward Functions Chen Hu Li Li Liu L NIPS 2016 深度学习的理论解释 理论计算机 理论计算机 数学 经济学 科学 技术 理论计算机科学研究中心 ITC
11、S 一流的师资 Pinyan LuNick Gravin Bundit Laekhanukit Zihe Wang Yuan Lin 讲席教授组 Xiaohui BeiNanyang Technological University Jin Yi CaiUniversity of Wisconsin Madison Yang CaiMcGill University Jing ChenStony Brook University Kai Min ChungInstitute of Information Science Academia Sinica Fu HuUniversity of Br
12、itish Columbia Minming LiCity University of Hong Kong Richard PengGeorgia Institute of Technology Mingji XiaChinese Academy of Sciences Lirong XiaRensselaer Polytechnic Institute RPI Shengyu ZhangThe Chinese University of Hong Kong Yuan ZhouIndiana University Bloomington 除了全职成员 我们还有一支来自海外名校的讲席教授组 他们每人每年在上 财至少访问一个月 合作科研及联合培养学生 活跃的学术活动 一年多的时间里举办过四次国际研讨会 国际暑期课程四门 举行学术讲 座50余次 一共接待了来访学者50余人次 包括来自美国 加拿大 欧洲 澳 洲 新加坡 日本 香港 台湾等地的理论计算机科学家 关注我们
