跳到主要内容

德赢vwin官网客户端

理论研究德赢vwin官网客户端

URCS的理论计算机科学研究侧重于算法和计算复杂性,以及它德赢vwin官网客户端们在计算社会选择理论、密码学和安全、马尔可夫链/计数等广泛领域的应用。

该部门理论的核心学院包括莱恩a Hemaspaandra,乔尔Seiferas,Daniel Stefankovic.,Muthuramakrishnan Venkitasubramaniam

教师

莱恩a Hemaspaandra

Lane A. Hemashaandra(BS Yale,Stanford女士,博士康奈尔)是NSF总统府年轻调查员奖的受援人员和亚历山大·冯·洪堡基金会的贝塞尔研究奖,是一名ACM杰出科学家。德赢vwin官网客户端Lane的研究德赢vwin官网客户端兴趣包括计算社交选择理论(见我们的CACM文章),复杂性和算法。他和他的合作者已经崩溃了强大的指数时间层次结构,发现了Lewis Carroll的1876年选举系统的确切复杂性,并建造了计算抵抗所有标准攻击的选举系统。里有同致的书复杂性理论伴侣半可行算法理论著书立说近百篇,期刊论文多篇编辑的职位

乔尔Seiferas

乔尔·塞弗拉斯(SB mathematics, SM and PhD, MIT计算机科学)是《计算机与机器无关的复杂性》一书的作者理论计算机科学手册以及关于AKS排序网络的章节并行计算百科全书。Joel也被授予ACM杰出科学家的称号,以表彰他在基于自动的复杂性、模拟、算法和下限方面的基础研究——包括在非决定论、层次和复杂性类方面的主要研究工作;德赢vwin官网客户端多线程磁带的仿真;Kolmogorov复杂度的下界字符串匹配;排序网络;和细胞自动机。

Daniel Stefankovic.

Daniel Stefankovic在芝加哥大学获得博士学位后,于2005年7月加入URCS。他的研究德赢vwin官网客户端兴趣集中在理论计算机科学,特别是:曲面上曲线的算法问题、马尔可夫链采样、算法博弈论、图形绘制以及离散和连续傅里叶变换的应用。

Muthuramakrishnan Venkitasubramaniam

Muthuramakrishnan Venkitasubramaniam于2011年秋季加入URCS。他在康奈尔大学获得博士学位,现为CI研究员,在纽约大学Courant数学科学研究所进行博士后研究。他的研究德赢vwin官网客户端领域是密码学及其与复杂性理论的相互作用,特别是:理解密码学协议的安全组成,有效结构所需的最小假设,密码学原语的内在复杂性,以及基于np -硬度的密码学。作为他论文的一部分,他提出了一个统一的框架,以有效地实现任何安全的并行安全多方计算任务(STOC'09);这类任务的一些例子包括匿名电子选举、隐私保护拍卖和容错分布式计算。

URCS理论集团与RIT(罗彻斯特理工学院)理论集团密切合作,群体共同运行理论运河研讨会系列。

项目页面

项目名称 简短的总结
离散数学在计算机科学中的应用

本项目研究离散数学在计算机科学中的应用。主题包括组合学、计数、编码理论、博弈论、学习理论和路由。

计算复杂性:减少,资源和鲁棒性

这个项目专注于复杂性理论。它的利益包括:裁军;资源和模型;鲁棒性;以及启发式算法的威力。

计算社会选择理论和算法博弈论

该项目研究了政治科学与经济学的复杂性和算法方面 - 特别是投票理论和博弈论。我们的工作范围从外会分配对投票系统理论研究的实验研究和合作博弈论。我们对复杂性可以作为保护选举免受攻击的工具特别感兴趣。

图形绘制,曲面曲线计算,弦图

该项目研究了图形绘制区域(网络图可视化)所产生的理论问题。研究的主题示例是:交叉数量的变体及其连接,平面概念的概念,以及表面上曲线的算法问题。

计算课程

这个项目研究的是计数课程。术语“计数类”指的是某些类的集合——比如#P、SPP、概率类、基于匹配的类等等——它们是根据不确定机器的接受路径的数量定义的。

半可行算法

研究了半可行集的性质。一个集合是半可行的(又名p选择),如果有一个多项式时间算法,给定集合的任意两个元素选择其中一个,并且这样做的方式是,如果两个元素中有一个恰好属于这个集合,算法总是选择那个。这可以成为引导搜索的模型。

基于复杂度理论的单向函数、密码学和伪随机生成器

该项目研究了复杂的理论单向功能,密码学和伪随机发电机。一个中央焦点正在寻求关于各种类型的单向功能存在的特征。同样感兴趣的是可以在不泄露信息的情况下进行查询,并更多地了解基于基础复杂性 - 理论概念之间的连接以及所有伪随机发生器是否不安全。该项目处于最坏情况的成语中,即,它研究所谓的复杂性无论是单向功能。

向下折叠和查询顺序

每个人都知道更有意义首先查找在网上约会本年度计算复杂度会议的日期,然后电话你的旅行社买到票,而不是首先打电话给你的旅行社(不知道日期),然后咨询在线约会书找到日期。在现实生活中,秩序很重要。这个项目试图确定一个人的日常生活直觉,即秩序的重要性,是否可以延续到复杂性理论。它还试图找到强大的类崩溃导致其较弱的同类崩溃的情况。

信息含量低的集合

该项目侧重于一组低信息内容,例如稀疏集合。