位置：立项数据库 > 立项详情页
理论计算机科学
  • 项目名称：理论计算机科学
  • 项目类别：优秀青年科学基金项目
  • 批准号：61222202
  • 申请代码：F020101
  • 项目来源：国家自然科学基金
  • 研究期限：2013-01-01-2015-12-31
  • 项目负责人：孙晓明
  • 依托单位：中国科学院计算技术研究所
  • 批准年度：2012
中文摘要：

申请人围绕通信复杂度、判定树复杂度、参数化复杂度等理论计算机科学中的关键基础问题开展研究，证明了LIS 问题数据只读一遍的最优复杂度，解决了Liben-Nowell 提出的未解问题，给出了第一个近似LIS 长度的复杂性下界；提出了低维空间中可变步长的新随机游动模型，证明了低维空间中局部搜索问题极限意义下最优的复杂度下界；提出了最近邻字符串问题新的固定参数算法和近似算法，大幅改进了这类问题的复杂度。相关研究工作已发表在FOCS，SODA，Recomb，SIAM J. COMP，IEEE Tran. Info. Theory，J. Cryptology等会议和期刊上，共发表SCI论文18篇，EI论文26篇，研究工作得到了国际同行的认可，在google scholar中总引用170余次，其中发表在FOCS 06上的论文被Algorithmica杂志列为05-06年量子计算方面最重要的进展之一。

中文主题词： 判定树复杂性；流式算法；空间复杂性；图性质；计算复杂性
结论摘要：

英文主题词decision tree complexity；streaming algorithms；space complexity；graph properties；computational complexity

成果综合统计
成果类型
数量
  • 期刊论文
  • 会议论文
  • 专利
  • 获奖
  • 著作
  • 17
  • 64
  • 0
  • 0
  • 0
期刊论文
Any monotone property of 3-uniform hypergraphs is weakly evasive
大数据时代的简约计算
会议论文
Tight Bounds for Graph Problems in Insertion Streams
Tight Bounds for Graph Problems in Insertion Streams
Tight Bounds for Graph Problems in Insertion Streams
Tight Bounds for Graph Problems in Insertion Streams
Tighter relations between sensitivity and other complexity measures
How to select the top k elements from evolving data?
How to select the top k elements from evolving data?
How to select the top k elements from evolving data?
How to select the top k elements from evolving data?
On the communication complexity of linear algebraic problems in the message passing model
On the communication complexity of linear algebraic problems in the message passing model
Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games
Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games
On the communication complexity of linear algebraic problems in the message passing model
Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games
Computing the Least-Core and Nucleolus for Threshold Cardinality Matching Games
Minimizing seed set selection with probabilistic coverage guarantee in a social network
Minimizing seed set selection with probabilistic coverage guarantee in a social network
Solving multi-choice secretary problem in parallel: An optimal observation-selection protocol
Solving multi-choice secretary problem in parallel: An optimal observation-selection protocol
Solving multi-choice secretary problem in parallel: An optimal observation-selection protocol
Solving multi-choice secretary problem in parallel: An optimal observation-selection protocol
On the communication complexity of linear algebraic problems in the message passing model
Optimal Pricing for Improving Efficiency of Taxi Systems
Optimal Pricing for Improving Efficiency of Taxi Systems
Optimal Pricing for Improving Efficiency of Taxi Systems
Influence Maximization in Dynamic Social Networks
Influence Maximization in Dynamic Social Networks
Space-bounded communication complexity
Determinantal Complexities and Field Extensions
Determinantal Complexities and Field Extensions
Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
Optimal Pricing for Improving Efficiency of Taxi Systems
Tighter relations between sensitivity and other complexity measures
Tighter relations between sensitivity and other complexity measures
Space-bounded communication complexity
Space-bounded communication complexity
Space-bounded communication complexity
Learning Market Parameters using Aggregate Demand Queries
Minimizing seed set selection with probabilistic coverage guarantee in a social network
Minimizing seed set selection with probabilistic coverage guarantee in a social network
Multi-classes Feature Engineering with Sliding Window for Purchase Prediction in Mobile Commerce
Multi-classes Feature Engineering with Sliding Window for Purchase Prediction in Mobile Commerce
Multi-classes Feature Engineering with Sliding Window for Purchase Prediction in Mobile Commerce
Learning Market Parameters using Aggregate Demand Queries
Learning Market Parameters using Aggregate Demand Queries
Learning Market Parameters using Aggregate Demand Queries
Influence Maximization in Dynamic Social Networks
The least-core and nucleolus of path cooperative games
The least-core and nucleolus of path cooperative games
On the power of parity queries in boolean decision trees
On the power of parity queries in boolean decision trees
Multi-classes Feature Engineering with Sliding Window for Purchase Prediction in Mobile Commerce
Determinantal Complexities and Field Extensions
Determinantal Complexities and Field Extensions
Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
Any Monotone Property of 3-Uniform Hypergraphs Is Weakly Evasive
Influence Maximization in Dynamic Social Networks
Tighter relations between sensitivity and other complexity measures
The least-core and nucleolus of path cooperative games
The least-core and nucleolus of path cooperative games
On the power of parity queries in boolean decision trees
On the power of parity queries in boolean decision trees
相关项目
布尔函数判定树复杂性的理论与方法
期刊论文 12 会议论文 4 著作 1
多重齐次多项式优化的近似算法及其应用
期刊论文 25
关联物流运输优化调度的理论与方法研究
期刊论文 21 会议论文 6 获奖 1
装配型排序理论- - 计算复杂性、近似算法和随机算法
期刊论文 41
广义组合优化逆问题的算法设计与分析
期刊论文 2 会议论文 3
非离散系统中的可计算性和计算复杂性研究
期刊论文 12 会议论文 6
数据流模型与判定树模型中的几个问题研究
期刊论文 17 会议论文 69
服装生产管理中的若干调度新模型及算法研究
期刊论文 15 会议论文 3
计算机科学技术的基础理论
期刊论文 19 会议论文 9 著作 2
孙晓明的项目
大数据结构与关系的度量与简约计算
期刊论文 7
数据流模型与判定树模型中的几个问题研究
期刊论文 17 会议论文 69