教育新闻网布里斯托大学的学者将在计算机科学的两个基本问题上提出新的突破。这些结果将在本周于世界领先的计算机科学国际会议上发表。
第56届IEEE计算机科学基础年度研讨会将于10月18日至20日在加利福尼亚举行。
计算机科学中最具挑战性的问题之一是是否存在难以证明的问题。这在未解决的计算机科学问题(P = NP是否能解决问题的任何人将获得100万美元的奖励)中最著名。
在第一篇文章，新动态和在线问题无条件的硬度结果，拉斐尔克利福德博士，读者在算法设计在大学的计算机科学系，并从同事奥胡斯大学，已经证明了硬度结果矩阵向量乘法，一个基本工具的版本在许多应用数学中 研究人员继续显示出有关数据动态变化的问题的进一步硬度结果。
研究小组研究了两个基本问题的细胞探针复杂性：矩阵向量乘法和动态集不相交的一种形式，称为Patrascu多相问题。研究人员针对这些问题提出了改进的无条件下界，并介绍了具有独立利益的新证明技术。其中包括一项能够证明以下形式的强阈值下限的技术：如果我们坚持要有非常快的查询时间，则更新时间必须足够慢才能计算出具有每个可能查询答案的查找表。这是首次证明这种类型的下限。
研究人员的下限被证明等于有史以来的最高值，并给出了这样一个数学证明的第二个例子，即使允许潜在的解决方案使用随机数，该证明也成立。
在第二篇论文《在近乎线性的时间内构建线性大小的频谱稀疏度》中，大学计算机科学系计算机科学讲师He He博士和麻省理工学院的博士生Yin Tat Lee提出了第一种构建算法在几乎线性的时间内运行的线性大小的频谱稀疏器。
当今大数据场景中越来越多的应用程序需要处理数百万个顶点的图。尽管传统算法可以直接应用在这些庞大的图形中，但是当图形包含数百万个顶点时，这些算法通常太慢而无法实用。而且，存储这些实用的大量图形非常昂贵。
何孙博士说：“过去十年来，进行了深入研究以克服这两个瓶颈。一种值得注意的方法是通过称为频谱稀疏化的中间步骤，这是通过继承输入图的许多属性的非常稀疏的图来近似任何输入图。由于大多数算法在稀疏图中的运行速度更快，因此频谱稀疏化是加快许多实际图形算法运行速度的关键中间步骤，包括在无向图中找到近似最大流量，以及近似求解线性系统等。”
使用频谱稀疏化，研究人员在稀疏图中运行了许多算法，并且也获得了大约正确的结果。这个通用框架使他们可以在一定程度上加快各种算法的运行速度。但是，要使整个方法切实可行，关键问题是找到更快的频谱稀疏构造，并在所得稀疏器中减少边缘。在过去的十年中，有很多研究针对这一领域。
研究人员证明，对于任何图形，他们都可以在几乎线性的时间内构造其频谱稀疏器，并且在输出稀疏器中，每个顶点只有恒定数量的顶点。就算法的时间复杂度以及频谱稀疏器中的边缘数量而言，此结果几乎是最佳的。
论文： Raphael Clifford，AllanGrønlund，Kasper Green Larsen在计算机科学基础研讨会(FOCS 2015)上提出的有关动态和在线问题的新无条件硬度结果。
论文： Yin Tat Lee和He Sun在计算机科学基础研讨会(FOCS 2015)上提出了在几乎线性的时间内构建线性大小的光谱稀疏性。他们的论文已被邀请参加SIAM Journal on Computing的特刊，该刊物专门介绍会议的最佳论文。
