Develata's Space

Appearance

2026-06-23 ​

新工作将固定s时对角Ramsey数R(s,k)下界改进至Ω(k^{s-1}/(log k)^{2s-4})，使上下界仅差poly-log，是Ramsey理论的重要进展。 新论文声称证明了二分图匹配问题属于并行复杂度类NC，这是计算复杂性理论的重要进展。 近期Abhranil Chatterjee等人证明二分图匹配属于NC，解决长期开放问题，推动并行算法与匹配…

The New Result on Off-diagonal Ramsey Numbers 86 ​

  • Tags: 组合数学 Ramsey理论 极值图论

  • Source: Computational Complexity Blog | 阅读原文

[摘要]
新工作将固定s时对角Ramsey数R(s,k)下界改进至Ω(k^{s-1}/(log k)^{2s-4})，使上下界仅差poly-log，是Ramsey理论的重要进展。

Bipartite matching is in NC! 85 ​

  • Tags: 理论计算机 计算复杂性 并行算法 二分图匹配

  • Source: Shtetl-Optimized | 阅读原文

[摘要]
新论文声称证明了二分图匹配问题属于并行复杂度类NC，这是计算复杂性理论的重要进展。

Matching in NC and Local Events 85 ​

  • Tags: 理论计算机 组合优化 并行计算 匹配理论

  • Source: Gil Kalai | 阅读原文

[摘要]
近期Abhranil Chatterjee等人证明二分图匹配属于NC，解决长期开放问题，推动并行算法与匹配理论发展。