CS phd Algorithm and Complexity 方向

1. 求问这个方向会更适合数学本科转CS方向的学生吗？
2. 这个方向的前景怎么样，在其他学科上会有怎样的应用呢？
3. 该怎样在这个方向和运筹学方向上取舍 （如果这两个方向都接受的话？）
4. 求大神们来聊一聊这个方向或者推荐些相关的介绍资料，万分感谢！

1.如果是真的想做研究，并且以后在学术界混，对数学出身的来说这确实是一个不错的选项。数学基础扎实对这个方向确实是比较有优势，因为这个方向的研究方式基本上就是数学系的研究方式——纸、笔、黑板，基本上不做什么实质性的编程实现，即使偶尔做写一些代码主要是对模拟一些例子对猜想进行验证提供进一步证明的知觉或者辅助找到反例。数学系没怎么接触过CS的补充一些算法知识和计算理论即可。我能想到的可能劣势可能只有缺乏一些对CS背景问题的实际体会，有时候欠缺一点知觉吧。不过话要说回来，如果是想把这个方向当成转CS的终南捷径去追热点，那并不是一个好的选择。PhD出来对口的基本上只有学术圈以及少数企业的基础研究机构（比如MSR），而且理论PhD大部分时间做的研究主流CS略有脱节，也训练不了什么工程能力。
2,3.这个方向基本上就是CS里面纯数的感觉，总体比较高冷。如果你特指Complexity的小方向，基本上就是跟数论差不多，基本上没什么应用，而且大部分都是否定性结论，据我知道的唯一的应用是一些结果能支持密码学上的一些假设，因为证明了什么东西很可能计算上不可行，所以安全。如果是Algorithm或者广义的TCS，那就很宽泛了。有人说做TCS的人是"smart and greedy"，很多学科相关的理论都做，比较应用的偏优化方面的跟运筹学差不多，有些问题方法论会略不同。有一个区别是不太做连续优化和数值模拟，然后不太会自己建模。相比运筹学可能更实际一些吧。
4.没学过算法的话，先从正经的算法分析开始看起比如Kleinberg和Tardos的《Algorithm Design》，然后再看一点Theory of Computation的书，然后再去关注一下各个小方向具体什么感兴趣的。概率论一定要学好。

楼主应该指的是理论计算机科学(tcs)的track a吧。个人稍微了解过一点这个方向。首先楼主问适不适合应数本科转，我觉得现在tcs里用到的数学工具越来越多了，所以楼主本科是学数学的肯定有点优势，但具体还得看你本科学了什么。然后应用领域的话，tcs应该更接近纯数，就是在实际应用领域里中没什么用…因为tcs更多是去研究一类算法，一类问题等等的基本上下界，而不是根据一个实际的问题给出一个好的结果。楼主想了解这个方向的研究的话，可以先去搜一下比较好的大学(比如四大，还有以色列的几个学校)的理论组的主页，然后去看看这些老师上课的lecture notes，先了解一下这个领域大概是做什么的。然后可以去看看理论的几大会议(focs，stoc，soda)上面的文章，大概了解一下现在前沿的研究大概是在做什么东西，有哪些你感兴趣的方向等等。

我觉得Algorithms, Combinatorics and Optimization (ACO) 这种项目应该跟楼主说的方向非常接近。非常适合本科数学，可以在CS Department下面就读，结合了数学，CS，以及运筹学（OR）。楼主如果对就业前景感兴趣的话可以看一下CMU和我们学校的alumni page。

[1]: http://aco.math.cmu.edu/
[2]: https://www.aco.gatech.edu/

今年申请了Algorithm and Complexity方向的phd
应数感觉像是用计算机方法来解决数学问题，TCS是用数学方法来解决CS问题
要是做算法的话可能还有点应用，可以做点learning theory之类的东西
可以看看网上的lecture notes，algorithms入门推荐jeff erickson的书 他的网站上就有; Complexity入门推荐Michael Sipser

感谢回复！🙏

ybbob 发表于 2020-2-13 19:54
今年申请了Algorithm and Complexity方向的phd
应数感觉像是用计算机方法来解决数学问题，TCS是用数学方法 ...

您好！我今年也打算申请这个方向的phd,我想做non-convex optimization和machine learning theory这两个方向....btw我现在硕士，和本科，只了解过optimization的东西，这两个学校里面都没有做ml theory的老师，我该怎么准备呢？跟着老师刷书还是要做其他的？

ybbob 发表于 2020-2-13 19:54
今年申请了Algorithm and Complexity方向的phd
应数感觉像是用计算机方法来解决数学问题，TCS是用数学方法 ...

您好！我今年也打算申请这个方向的phd,我想做non-convex optimization和machine learning theory这两个方向....btw我现在硕士，和本科，只了解过optimization的东西，这两个学校里面都没有做ml theory的老师，我该怎么准备呢？跟着老师刷书还是要做其他的？