想了解一下如果想要读理论计算机（TCS）方向的phd需要做出哪些努力？要怎样入门research？

几个tips，我自己身体力行总结的：

1. 不要直接读一本书，哪怕经典如"introduction to algorithms" "approximation algorithms" "the design of approximation algorithms" "online computation and competitive analysis"。因为人一开始总是斗志昂扬的，往往读书都会从第一章甚至Preface开始。而大量的英文段落会极快地耗尽你短暂的热情（因为你根本不知道重点），然后很大可能你就会把这些书放到一边，跟自己说太难了不想读了。等下一次你又燃起了斗志，你又会犯同样的错误：从一开始读起。这样周而复始循环往复。你的时间，热情，机会都被彻彻底底地浪费了。

我最建议的方式是看一些欧洲或者美国大牛讲课的notes，这些notes剔除了冗余的介绍，直接给出问题定义，相应的算法以及分析，简洁高效。一般一门课程13到20个notes，一个note的话4到5页（旁边空白一大堆）。也就是说，如果你一天读一个note的话，2-3个礼拜就可以大体了解一个topic的核心内容了。这可以最大程度地利用一个人的专注力去了解一门subject（你知道一个人很难专注很久的）。

我读notes有一些癖好，我喜欢用latex自己编译一遍。并且在敲latex的时候，我一定要按照我自己的方式重新编排句式。这相当于我给我自己讲了一遍原本note里介绍的内容。你要知道，如果我能逻辑通顺地把每一句话介绍地清清楚楚，这一定意味着我深刻地理解了这个问题的本质或者算法的idea。并且，这个过程也在训练一个人的写作功底。等到自己写论文的时候，这一招是有奇效的。

对了，这些课怎么找，这里介绍个方法。你可以上CSrankings（CSRankings: Computer Science Rankings），要是做算法，选algorithms & Complexity（也可以多选一个Economics & Computation）；做密码，选Crypto；做逻辑，选Logic & Verification。然后一个一个人点那些学者的主页。这些人大多会介绍他们的courses，并且这些courses的homepage上很有可能是有notes的（除非需要学生id和password）。要知道这些人讲课，除了课程的基本定义&核心内容以外，他们是很大可能会介绍自己的“私货”的，也就是他们以往论文里的核心内容。所以往往读完他的notes，你就可以大体了解这个人做什么方向了。

另外还有一种方法是基于学校的：比如，找到Max-Planck D1的网页，里面就会介绍他们开的课（https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching），这也不失为一种方法。

介绍几门课我很喜欢的：

• Algorithimic Methods: Algorithmic Methods, Yossi Azar
• Online Algorithms: On-line and Approximation algorithms , Yossi Azar
• Graph Algorithms: https://www2.cs.duke.edu/courses/fall19/compsci638/
• Parameterized Algorithms: https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/summer20/parameterized-algorithms
• Computational Game Theory: https://www.tau.ac.il/~mansour/course-games-2009-10/course-games-2009-10new.htm
• Games on Graphs: Games on Graphs 2019
• Algorithms in Actions: Algorithms in Action 2020

2. 光听课是一定会让人感到迷茫的：听了这么多课看了这么多notes，鬼知道这些人到底是怎么找到这些问题的以及怎么想到算法idea的。这怎么办？

这就需要dblp的帮助了！

你应当直接搜最关键的conferences（不要看journal），比如SODA STOC FOCS（最好最基础最难）COLT （有关learning的算法） SPAA （有关parallel的算法，像load balancing，scheduling的类似问题都在上面）PODC （有关distributed的，很多有关graph problems都在上面） EC （有关game theory的） APPROX-RANDOM ICALP ESA IPCO FSTTCS WADS ISAAC STACS（啥都包括，低于SODA STOC FOCS）差不多了，就这些。

看近五年中的这些conferences中的papers做了些什么。自己归类，记住看关键字，比如online，scheduling，matching，metric，counting，planar graph 等等等等。找到自己感兴趣的（或者更准确点，和你导师做的方向很关联的），然后找论文原文。

读论文的话，先看abstract（重中之重，决定了你是不是感兴趣以及要不要读下去，如果里面有太多keywords看不懂的话，那么这篇文章不适合你，你需要先去看相应的课程notes来了解核心定义），再看intro（有明显特征，一般一上来会先介绍background，然后依次是problem description，previous work，results of papers，technique - 这个非常非常有用，文章里的idea一般在这儿就介绍得很清楚了，related work，organization of paper，所以读intro的时候相当于自己要做一遍语文阅读理解），如果对这个问题感兴趣，好了，直接看conclusion，作者往往会聊一下future work的。有可能作者不想把他真正打算做的写在里面，这就需要你搜这个作者的过往papers，自己捋这条线，琢磨那些方向还继续有的挖。

这里还是多说几句吧。当你第一次读一篇五年内发在以上conferences的文章时，往往百分之九十九的可能性，你会在读到abstract时就看不懂了。然后你就会疑惑：我不是刚读完相应课程的notes嘛，怎么这篇文章我还是看不懂要做啥呢？是不是我太笨了，根本就不是做tcs的这块料啊。

请千万千万不要这么想。要知道，能发在这些顶会的论文，都是那些很聪明的researchers花半年到一年才想出来的。并且，为了保证严谨性，这些文章必然挺晦涩难懂的。所以你一上来读不懂就对了，简直天经地义！但是不要怂！一方面，你可以试着找找这篇文章的slides或者videos（疫情闹的，好多会都开线上了，导致好多videos放到了Youtube上），在有slides或者videos的情况下不要读论文，一定要直接看slides或者videos。要是没有slides或者video，读第一次读不懂，OK，明天或者后天再读一次；要是再看不明白，过几天接着读。简而言之，干就完事了。等到你搞明白的那一天，你就会感觉超级有成就感。怎么说呢，这种感觉就像是过了黑魂或者血源里的大boss一样，超级爽！

3. 如果遇到看notes看不懂，做课后习题不会做。很正常！别死磕！找答案！这些题的答案一定可以在作者的论文和主页里找到些许痕迹的（用好dblp，arxiv）。有courses第一选择notes，有slides或者videos的时候看这两个，啥都没有时候看paper。永远先把更简洁的讲解先找出来看，看就看他们怎么设计算法的（尤其是他们自己介绍自己算法的idea的时候）。同样的，用latex把这个核心想法用自己的话重复一遍，你就了解地加深了一点。这样的话，来回写几遍latex，你就会把这个问题或者算法的idea彻底搞懂了（子曰，学而时习之，不亦说乎）。

4. 然后说怎么做自己的问题：如果你是博士生或者博后，你手边一定是有很具体的问题要解决的，不管是scheduling，graph problems还是什么。解决一个问题，要非常重视自己的直觉（因为直觉是你基于经验知识给出的下意识反馈）。如果根本没任何感觉的话，你就要手动得造几个例子来给自己一些感觉。有了感觉，就要把自己的感觉啊想法啊很formalized表达出来。永远不要小看这一过程，因为你始终是自己的听众，当你能逻辑通顺地把问题写出来，这就意味着你对问题必然有了更深刻的理解。当然，一个人的直觉有可能是对的，有可能是错的：对的话，你要严谨的证明出来；错的话，你要找到反例。除此以外，如果想了问题很多次并且也造了几个例子但是也没什么想法，这就意味着这个问题对于你当前而言太难了，你需要考虑的是这个问题的特例来迈出第一步。要知道，特例往往是要简单一点的，如果你能搞定特例的话，那么解决特例的方法也许能给你一些想法来解决原问题；不然的话，这说明当前的特例也很难，你要接着找特例的特例这样简化下去。

5 心态的问题：除了上面说的不要怂以外，不要靠努力来逼迫自己做theory。努力是我最讨厌的一个词，它让一个人变得很emotional而不是logical（或者rational），它让一个人错误地一厢情愿地自以为是地相信大力出奇迹（这一点也不科学）。从某种意义上，努力是虚荣，敏感，傲慢，幼稚，可笑的一种伪装。做research，一个人应当心态平和，保持logical。做不出来就是做不出来，一时半会想不出来就是想不出来，遇到这种情况人就应该放空自己，去外面走走，看看景色，吃点好吃的，买买买，玩玩PS4啥的。等到一个人精力恢复了，接着昨天没想通的继续想。一时没想出来没所谓。想的时间久了（假设一个礼拜吧）也想不明白就要搜过去的论文或者notes找想法了（怎么找上面说了，在dblp里搜keywords，找相关论文，看他们的想法）。太阳底下没有新鲜事，不要钻牛角尖，不要试图创造问题，不要担心你的想法已经被previous work搞定了，人要开放，不要活在自己的世界里像个鸵鸟，不然的话人会变得很极端。

啊，和我几乎一样的背景，除了我的本科MHC的排名大概都30+了。
文理学院没有研究院，做research会非常吃亏。不说没有TCS教授，整个CS系里做的研究不是“打打闹闹”的有几个呢。

做研究，无外两个方面的问题，1. 做什么题目 2. 用什么工具。
我自己的经历是算法相关，所以拿算法领域举例子，复杂度或者其他交叉领域可能有出入。我本科的时候实际上是没有接触特别多现在TCS正在做的的题目的，只是上课看着一些经典的题目（matching，flow，TSP之类）觉得有趣。但这种级别的题目现在想接着做新东西非常难，所以不能看着喜欢就觉得自己想做这个研究。可以去STOC/FOCS/SODA/ESA（其他领域开这个单子TCS conference）看看新的文章找找题目。能理解题目就不错，然后看看这些题目自己有没有兴趣。找点有兴趣的题目的paper真的读一读，读得慢没关系，一遍读不懂读两遍三遍（即使到phd一篇tcs文章读好几遍才理清重点也是很正常的），能读下来可能就会有更清晰的意识对这类问题和读文章本身是不是真的感兴趣。这一步重要是因为在按其他人说的学习工具和找校外的研究项目以前，你需要尽可能真实的做一个预测：如果这是我以后每天要做的事，我真的喜欢吗？如果到这一步还是觉得喜欢，下一步就是打基础。

积累理论工具很重要，除了经典问题的经典（但非本科教学内容的）算法，概率，图论，组合，Polyhedral Theory在设计和分析算法上都很有用。这里有个书单非常全：Books everyone should read in tcs. 但大部头也不能都拿着从头到尾啃，最好还是在自己学校（或者网上）上一些这些方面的grad level的课和别人的笔记（这个我没整理，随手贴个uiuc教授的随机算法方面的Notes on randomized algorithms）。这一步没有“完成时”，所以按自己的兴趣和能力来就行。惭愧地说，所谓基础，其实我自己是到phd阶段才开始打的，本科学的组合优化，图论都很简单。可能我是个例，但个例也是存在的，不用非要跟姚班竞赛金牌或者MIT CMU这些地方资源充足的人比进度。

有了一些工具之后去找暑期实习应该会容易一些。我本人没有跟不认识的教授做事的经历，就不装作有经验有看法了。这一步既是为申请积累经验，也是继续收集数据回答这个问题：如果这是我以后每天要做的事，我真的喜欢吗？


最后，日常劝退：如果在任何一步觉得和自己预期的不一样，好像不太有动力不太开心，趁早重新审视“我想读tcs phd，我想做tcs research”的大前提，不要怕沉没成本和“那我做什么呢" 的迷茫阶段。按我之前导师的话，读phd/做研究不能开自动驾驶模式，不然容易坠机。

（关于我个人更详细的申请背景+劝退可以看我的这个回答。）