Tag
This paper addresses open questions in the Gold-Angluin model of language identification in the limit, showing that computational traces using only a small alphabet and defined directly from the language enable identification in the limit, without requiring an underlying machine model.
Discusses a 2014 paper that refutes the 3SUM conjecture by presenting subquadratic algorithms for the 3SUM problem, with implications for computational geometry and graph algorithms.
A free open textbook 'Introduction to Theoretical Computer Science' used in Harvard courses is announced, covering foundational theory including computation, algorithms, complexity, and quantum computing.
Gödel Prize winner Ryan Williams offers a contrarian view on P vs NP, arguing that our understanding of polynomial time computation is still shallow and full of surprises, putting his confidence in P≠NP at 80%.
麻省理工学院教授、哥德尔奖得主瑞安·威廉姆斯在一期播客中深入讨论了算法优化、细粒度复杂性理论以及强指数时间假说等前沿计算机科学话题。
An article discussing obfuscation as a powerful cryptographic primitive, potentially the 'final boss' of cryptography due to its theoretical and practical challenges.
Research from the MIT Hardness Group proves that Super Mario levels can be undecidable, meaning no computer program can always determine if Mario can reach the castle, placing Super Mario in the hardest complexity class.
A paper by Chatterjee, Ghosh, Gurjar, Raj, and Thierauf claims to show that the Bipartite Matching problem is in the complexity class NC, resolving a central open problem from the 1980s in parallel algorithms and derandomization.
This paper proposes an indirect computing model and indirect formal method for optimizing cloud computing, using Chinese information data as an example to transition from data centers to knowledge centers.