从南京回来之后稍微闲了两周, 这两周在等 THU 和 NJU 的结果 (虽然 NJU 已经优营) 以及继续手上的科研, 还有报名其他学校的夏令营, 十分焦虑, 虽然知道可能性不大, 但是还是抱着老师会给我个机会的希望; 外加五月中下旬在准备 THU 和 NJU 的营, 其他学校也没陶瓷, 弱 com (指 PKU) 可能都没机会了.

最近这两周我重新审视了一下我做手上这个理论的问题的整个过程, 我从去年十月份到十一月份正式开始做这个 -plex 的枚举, 而且寒假之前得到的结果几乎都是作废了的, 寒假之前所有的探索都是弯路, 包括但不限于

• 直接用数学归纳法, 发现很难逼近 conjecture, 而且我最开始的整个思路都是乱的, 连 measure 都没确定下来就忙着分析, 结果就是屡屡受挫
• 受 -regular induced graph 的算法的启发考虑两阶段 (active-growth) 的算法, 但是发现 worst case 的改进几乎是不可能的, 和 的 gap 实在是太大了

然后我一整个寒假包括开学后的一个月都没再想这个问题, 这个时候我就已经愈发觉得这个问题很无聊, 一点也不优美, 整个问题全都是暴力的分类讨论, 而且自己薄弱的知识储备也不足以让自己能熟练运用更高级的工具来解决整个看似是组合的问题, 几乎就没有动力再做了.

后来想着换个角度去思考, 尝试从 扩展到 , 考虑随机图的界等等, 正是尝试从 扩展到 的失败, 才让我有了为每个点定义 两个指标的 idea, 后来发现这样做很容易就扩展到一般 的情形了, 索性就不先纠结 是不是有 的 upper bound 了. 然后经过几版修改, 若干次尝试, 得到了最终算法的雏形, 并且真正意义上对任意 做出了改进, 并且是很简单的, 甚至可以说可能是 practical 的, 当然这都是后话了, 至于是否真的 practical, 就看有没有后人愿意做这件事情了.

当然是值得开心的, 这意味着已经完成了我期望的工作的 50% 了, 剩下就是证明 的 conjecture 了. 这大概就是五月初的结果了, 然后又因为夏令营中断了一个月. 比较幸运的是, 由于我联系 NJU 和 THU 都是做理论的老师, 我的这份经历起到了很大的作用, (NJU 的老师还帮我指出了汇报出现的问题), 即使 THU 的老师做的是深度学习理论, 这也就导致了我后面又不想做传统的 TCS 了, 还是和 AI 沾点边比较好, 所有之后的套磁基本上都在联系做人工智能基础理论的老师了, 除了 PKU, 而且老师也没回我.

然后现在又把这个工作给捡起来了, 到目前为止整个时间已经有 8 个月了, 虽然我的有效工作时间可能不到 20%, 但是我也乏了, 想快点结束这个工作, 写成文章赶紧投出去, 做点其他有意思的工作. 但是我低估了剩下 50% 的工作难度, 现在依然是寸步难行, 或者说人力几乎不能做到, 除非换一套理论或分析方式, 或者用机器辅助证明, 但是我已经没有太多精力和动力继续想了, 这就导致我只能再下放要求, 不去考虑所谓的 tight upper bound 了, 也许整个 conjecture 就是错的; 当然即使真正证出来了, 好像也不是很有用的样子, 都是一些脏活累活罢了, 不优美. 现在的想法就是赶紧再六月份把这个工作结束, 再拖就真不想做了.

整个过程其实是相当坎坷的, 因为五月份之前没有任何人给我提供帮助, 全都是我自己在想, 去找老师汇报也只是说一下进度, 大多数时间都在尝试, 且都是失败的尝试, 很受挫, 冥思苦想怎么想都想不出来的时候也是如坐针毡.

不管怎么样, 这份经历也快接近尾声了, 不过还没动笔, 需要等写完投出去才算真正结束, 希望有个好结果.

等八月份的 AAAI 截稿后, 再谈谈另一个科研.