lapordge的共享空间

巴黎这地儿还真值得写写。
我这个不爱排照片的再不写写以后怕忘了。

 

在那呆了两天，从德国边境过去的，做欧洲的快线，飞快飞快，2个小时就到了。
都说法国人不爱讲英语，我也不爱讲。我爱讲法语，可惜不会讲，mercimerci，有夏狗一般的法语应该能凑合了。

旅馆在市中心，地图上离啥都挺近，所以就走着去。

先去卢孚宫，我走啊走，街上挺漂亮，瓢漂亮亮的小房子大房子。
天气特别热，街上很多馆子，外面搭的棚子，棚子底下喝点啤的。

走到一个老大房子附近，房子特别老又特别大，我觉着应该是个古迹。
可惜只认得标签上停的苍蝇。
突然闪出一对说英语的gay，对着房子指点指点，我总算听懂了人话，我说你门知道这是啥不？
两人说不知道。
我又问了一个人，滴了嘟噜一个字没听懂。

 

一阵沮丧，继续找卢浮宫。走啊走，突然闪出一对说上海话的，我说该咋走，上海话加普通话告诉我走不到，要做车做H什么什么打头的车。
我说我就想走路，就告诉我走不到。我没理，继续走，结果又走到一个大房子，比刚才那个大
雕塑也比刚才那个花，我猜应该是个古迹。
这个古迹应该比刚才那个牛b，外面有柜台，柜台里面有小本，有中文的，原来是老市政厅，
丫市长真挺奢侈，比广东佛山那个气派多了，包这个项目的估计回扣没少拿。
柜台里面还有小姑娘，我问小姑娘卢浮宫咋走，她告我得走40分钟，我mercimerci。

 

走啊走。突然闪出卢扶宫。
腿基本走断了一半。这宫那叫一个大啊，我找门花了我半个小时。
门就在那个想金子塔的地方。我想起了苏非的电影，好多小鬼飘啊飘。

人山人海啊人挤人。众。

里面实在是大，这个厅啊那个厅。
晃进非洲厅。古代非洲人好个图腾，图来图去的，鼻子上掉个环啥的，厅里面的玩意儿基本也就这个特点
好好的肉身扭曲扭曲再加点零碎，大红配大绿
咱现在老黑兄弟对古人继承的不错

晃晃又到亚洲厅，咱老中的东西没找到几件，都是三哥的。
连着几个屋子，都是三哥的墙，一面一面的都被搬运了过来。
画墙那个人要早知道就做法航飞过来画了，这一面墙一面墙的运的累的慌不。。
法国鬼子真是没少抢东西，那个国家的都有。当时我想希哥为什么没运回家几件，还是本来运回去了，项目做败了又给人运了回来。
后来知道巴黎人民保护文化遗产，知道没法阻止希哥进来，宣布该市不设防。
而希哥巨仗义，炮弹没忘文物上扔，文物没碰还给保护了起来。
yy了一下自己能不能有希哥这么厚道，也没准，不过咱老中的东西得先运回来再说。

扯到希哥，想也是一带豪杰，指点江山，一人之力改变欧洲历史，除了咱家的汗哥历史上再也找不出第二个，只可惜最后没拼过毛子，
又杀了太多老犹，搞了个身败名裂。

 

咱虽没文化，站在这个厅里也能感受到到这文化的气息，虽然不懂艺术，也为这众多美伦美奂的艺术品所折服，
虽不了解历史，但这波澜壮阔的历史留下的痕迹也让我热血沸腾。
在每件文物附近，都能感觉是一个时代一种文化的缩影，
凝视每件艺术品，都象在与它的作者进行一次默契对话。

 

 

闲言碎语不多讲，单讲俺李某人晃进了法国雕塑厅。
这里多数东西都是大理石的，所以比其他厅凉快，这是俺最爱呆的厅。
里面有很多以前初中时候画过的头像，这里面都是全身的，初中时候老师不买全身的象让我们画，我估计是因为都是naked的。
里面还真有人对着雕象画，我估计他们老师和我初中老师一样。

哎呀我写不动liao，困，留着以后写吧。

顺便做个remark/btw ： 上两个礼拜写paper，老板读完说我english has been vastly improved，我发现我中文是vastly往后退，
退到后语快搭不上前言liao。写作这玩意，练是王道ya。

I remember I said in the previous blog I was going to have a crazy summer, but I didn't expect it is this crazy..........

Just passed the SODA deadline a few minute ago.

I had two submissions: one is about a clustering problem with some new interesting constraints and the other is on an interesting generalization of the classic machine scheduling problem. Hopefully, I will get lucky results on a nonempty subset of them....

 

A few days ago, I was in Providence attending SIGMOD09. Something interesting to say about the conf.

First is the super surprising and exciting news that I got the VLDB09 best paper award.  I had never expected that before and was really surprised.

Honestly, it is a bit too much to a student like me who is sort of new in DB and I am not quite ready....Perhas it means to be an alert dictating me to learn more DB..:)

 

I really enjoyed the conference since I made a lot of friends and met quite a few famous researcher. A new discovery is there are so many prof/student graduated from Fudan are doing DB right now. It is not at all easy to find so many Fudaner outside Fudan and all are doing DB, ranging prof/ass prof/phd/lab researcher/industy ppl.....

 

It was also a good chance to meet those legendary big name in DB, e.g. micheal stonebreaker, ronald fagin..., they are true bigboss da学霸!

This is the story. When I was doing my PODS talk, fagin was sitting in the first row but I didn't know that was fagin at that time.

 I had prepared the talk a couple of times and the time should be just enough. During the talk, fagin kept interrupting and asking me questions. I was thinking "这老头谁啊。。。". Since fagin always asked question, there was an other lady, she thought maybe question was allowed during the talk and tried to ask one. Before she finished her first sentence, the session chair stopped her with "we are running out time, plz take the questions offline...". But fagin kept asking questions and the session chair responded with super smile in his face...Finally, I couldn't quite finish all the stuffs that I wished to cover and skipped a lot of details. Later on, my advisor told me that was ronald fagin.....

 

To me, this SIGMOD was not as exciting as the just-ended STOC09. A major reason is that I can only understand a limited number of talks. Hope next time things will get better.

 

A couple of technical remarks: one is column store seems becoming very hot now. Another is probabilistic database, many sigmod/pods sessions are devoted for it. See also the most recent issue of the Comm ACM, there is a long artical about it. I think it should be the way we manage uncertain data in real life applications, but just not sure how far it will go, will this theory result in an indispensible commercial system? Let's see. 

 

In Aug, I will go to UIUC for a wireless network summer school and then go to Germany to visit MPI and then to France for VLDB. Crazy summer goes on an on....

 

 

    

 

 

一路奔波来到了dartmouth，整整睡了一路，到旅馆的时候已经下午2点多，饿的不行了。
东西扔到房间里，来到了旅馆里的餐厅。因为午饭时间过了，里面已经没几个人了，服务员都在那聊天。
我进来他们都不知道我要干嘛，对我做目瞪口呆状。你说来饭店能干嘛，我直接告诉他们我要吃。
领班的小姐说不确定师傅还做不，就剩点中午剩下的自助了。我剽了一眼那边的自助，有虾有蟹的，能凑合。
我问她多少钱，姑娘甜甜的告诉我sixTEEN. 我心里话，贵是贵了点，不过有虾有蟹的，而且很饿，忍了。
闲话不多讲，找了个偏僻的小角，一盘接着一盘。小姐有事没事过来问问is everything ok? 不合时宜的是每次
每次都是在我刚把食物放嘴里的那一秒。我只好每次点头加举大拇指了事。

 

时光如水，到该交钱的时候了，结果拿起单子一看 sixTY....dollar...!!税就够我吃顿卖当劳了。
心里虽然哭泣，表面还很镇定。爷走南创北，啥阵势没见过，爷能住起你的店，就能吃起你的饭，不能给咱包钢子弟丢人。
tip也是没含糊， *15%=9块 一文都没少。小姐为我的冷静所折服，必恭必敬的去结帐。

 

我本来晚上说去吃泰国菜。后来想想不划算，就买了点饼干就着白开水吃。真是难忘的一天。

 

 

Finally put an end to the crazy life of the spring semester, now let me start a new crazy summer:)

Prison Break was eventually over with a pretty sad ending (despite the overall boring season 4).

24 has been starting kidding me now with tony turned out to be a trader.

................. 

 

 

神秘马戏团(strange circus) ， 风行上有

 

又是日本片，不过这次不是毛片。

推荐下，没看过人生不完整，实在太变态了。

我也不影评了，评不了这么“艺术”的片。

 

its been a long and loose day.

a good news is one o fmy papers got accepted. a bad news is another paper got rejected.

these kind of news are like fuyun that will vanish in my heart soon, concrete in my career though.

 

here comes something deep in my heart, actually fuyun though.

came across a song which reminds an really really old song which i really really liked when i was a child. I believe i haven't heard it for at least 15 years.

i made a lot effort and finally found it out.

 

couldn't help to record it here

title: 爱不释手

“沉鱼落雁，闭月羞花，美的没处藏；人在身旁，如沐春光，宁死也无憾。国色天香，任由纠缠，哪怕人生短；你情我愿，你来我往，何等有幸配成双。啊哈，待我拱手河山讨你欢，万众齐声高歌千古传。你看远山含笑水流长，生生世世海枯石烂。啊哈，今朝有你今朝醉呀，爱不释手你的美，莫等闲白了发才后悔；啊哈，今朝有你今朝醉呀，爱不释手你的美，让我抱得美人归……”

admittedly, it was not that good, just a normal one among many straightforward and shallow ones that ever attracted me.

I've never been proud of my taste, but also never regret for anyting i loved.

its been a different feeling. it is like an old friend of mine, the lyric and melody seemed to attempt to remind me something.

It was a theme song of a TV series. I certainly remember that the first time when i heard this song, i was totally captured.

 

rivers and mountains, hero and beauties, lofty sentiments,.....

i am recalling these boy dreams,

 like so remote from the real life,

but still so deep in the boy's heart like he never stops chasing.

 

Probly one day, the boy became old,

he got a chance to hear the song

that he ever loved 50 years ago,

he knew the boy dream never came true but he never regretted. 

 

btw:

hardly got a chance to be sentimental, hehe. Don't mock at me, my friends, leave me some space for 磨唧，寡 and YY :-)

if you never heard this song, don't be misled, it is not a good song from modern's perspective. You may love it only if you actually loved it.

 

 

写在深秋。
深秋，本该是个浪漫而又忧郁的时节。

 

天气已经转凉，一开门就能感受到让人一颤的冷风。
脚下的沙沙的落叶让人感到无尽的凄凉。
傍晚天就已经黑下来。
一个人漫无目的的开着车，随车流涌动。
车灯闪烁，街两边异国的万家灯火。

 

回家来漫不经心的打着键盘，

忆起那如那霓虹般的往事，

却在我眼中变的黑白和模糊。
曾经的欢笑和泪水再难掀起今日心中的波澜，

生活的剧本无法避免的变的平庸，
我别无选择而随波逐流。
这个时候，我更愿意成为我生活的观众，去嘲笑这导演拙劣的安排。
生活就是充满哭笑不得的无奈，我却不得不打着哈切勉强去看完。

 

请别笑话我的矫情，也许曾几何时，你也踌躇满志，意气风发，
可如今忙碌之余却发现自己两手空空，而激情却消磨怠尽。
你可曾某一刻心里空虚和失望，想要发泄却又找不到放肆的理由。
你可曾觉得现在的生活的琐碎与平庸，而后悔当初如果不这样选择。
你是否有拷问过自己的内心，这是否就是或将实现你最初的追求。
无奈的现实并不给我们留许多选择的机会，更多的时候我们需要一点坚韧和毅力，
更多的需要执着的面对这时光的流逝。

 

“我们是如此力不从心，我们却又将激情隐藏，一再地掩埋，

一再地扼杀，一面还期待，一面还仰望，可笑地祈祷着幸福.

我们已经让外在的目标将自己折磨的遍体鳞伤，

但请让我们心力交瘁地跟随，让想象突破翱翔，让灵魂艰难起舞。”

今天十五。

老娘msn发消息过来，让我吃两个月饼。

我就没听她话，只吃了一个。

天特黑，知了啊没完没了的叫，眼前一杯茶喝的就剩了个袋。

十五的月亮圆，比月饼还圆，咬一口，真甜，就变成初一了。

祖国未统一，心情很郁闷，爷们我又是一夜无眠。

 

睡不着在床上打滚，被子被滚成了个球。

滚成球了也不怕，

因为俺娘用把被罩和里子缝在了一起。

 

前两天娘给我讲了个事，

邻居家一个大我几年的女娃，

跟着她家爷们来美国，有几个年头了

说要给她爹妈买房子。

说了有几个年头了，

老头老太太还住我家邻居，头发全白了。

 

俺妈白头发也多了，

我在美国遨游因特耐特，

和家们口网吧小痞子做一样事。

想起小时候混游戏厅时候叼根烟很装b，

给亲娘揪着耳朵拽回家，

却从来没抱着被子打滚。

 

我爹爱玩牌不回家，我娘总骂他。

我读屁h地不回家，我娘总夸我。

我觉的真“光荣”。

 

大秋天的外面野猫叫春，真想过去踢两脚。

 

爷们真想大喊一声：“我靠！”

怕吵到室友。

我带上耳机听了遍歌唱祖国，竟抚平了我心灵的创伤。

 

人家都说半夜思路很清楚。

清楚的象月亮上的玉兔。

我说这佳节我得鳖出篇精妙文章。

没想到如此精妙。

 

 

 

 

 

A Chinese mathematician claimed a proof of Riemann Hypothesis

his paper was posted on arxiv

 

However, the proof was found incorrect by others, see Motls's blog.

 

My homepage has been moved to

Welcome.

 

old one( http://homepage.fudan.edu.cn/~lijian )

真好看◎！

 

洋人一见我都说“nice haircut!"

 

例外就是系里中国女生假装不认识我了

还有一中国男生还悄悄说“也不带个帽子”？

 

不过爷们就是自己感觉美，爱咋咋地，呵呵

zz from eppstein's blog

http://11011110.livejournal.com/108036.html

Cute problem related to integer sorting
Find the max gap among n integers, in linear time and space.

The problem is stated in an ambiguous way that could be interpreted as asking for the largest difference between successive elements of the unsorted sequence, but regardless of what the original questioner wanted, what I want is the largest gap in the sequence formed by sorting the input.

Of course, since max gap has an n log n lower bound in certain real-number computation models, one has to use the fact that the inputs are integers and assume a reasonable set of binary integer operations. On the other hand, I haven't said how much precision the inputs have, which makes the obvious linear-time integer sorting solution problematic. But the precision doesn't matter! After subtracting the minimum value from all the inputs, and determining the highest nonzero bit of any remaining value, to normalize the range, one can bucket-sort the inputs by their first log₂ n + O(1) bits, and the max gap will be between the max of some bucket and the min of the next nonempty bucket.

===============

复旦计算机系楼223室原来是理论教研室.

 

理论组教研室里有很多回忆,

 

教研室分成2个屋,外面自习教室,有个不大的书架,一块大白板,里面是机房.

朱老师搬去了逸夫楼,以后教研室就很少有人打扫.

 

教研室有本TAOCP,里面夹着Knuth用铅笔给朱老师写的信.

 

刚来时我从书架时抽下一本大书就从第一页开始看,我说怎么一上来就看不懂,后来知道是STOC的Proceeding.

 

一般师兄师弟都不来,就我一个人,大白板就我一个人乱写乱花,一般是一堆图和公式, 兴致来了就画上一幅. 有一次速写了一个窈窕淑女,忘了擦掉,赵一鸣的密码小组来上讨论班,都说我画的好看.

 

教研室里夏天很多蚊子,有一次我在那里通宵打英雄无敌被咬了无数个包.

 

又是某天师兄师弟都不来,我找来3个人来机房里打Starcraft 2v2, 我同学都说教研室比较象网吧.

 

我曾经在教研室的书架上翻出不下5篇寄给朱老师的声称证明了P=NP的论文,短的十几页,长的上百页.

...........

摘录出我毕业论文里致谢的一段话,总结一下学习TCS的感受:

"难忘在复旦的三年光阴。我从一个城乡规划专业的本科毕业生，踏入我并不了解的理论计算机领域，这个令人不断感受到惊奇与美丽的领域。仍能回忆起钻研白皮书时的痛苦，和同门为一个问题面红耳赤的争论，长时间冥想而毫无进展的烦闷，灵感偶得时的兴奋和漂亮的证明给我的惊喜。这研究中探索的痛苦与艰辛交织着成功的兴奋与喜悦伴着我度过了这难忘而美好的时光。"

 

我想说说我的研究的感受.

 

客观的来讲,以国际的水准来衡量,我的研究连优良都不算,但在国内却可以说是不错的.

 

对于一个初学者来说首要条件是打一个相对好的基础,而最重要的事情就是找到可以入手的问题.这个问题既要有意义,又不能太简单,但又不能难的做不出. 问题的选择可以依赖于导师, 但是有时根据自己现有的知识,评感觉和尝试会有更好的效果. 我导师朱洪老师经常提出一些巨大的Open Problem, 大部分是那种解决了可以直接发STOC或者Journal of ACM的, 有些是那种重要的解决了就可以拿哥德尔奖甚至图灵奖的问题, 说实话我也认真尝试过, 无奈天资实在有限只得作罢, 而另一个导师Rudolf一开始给了我不少他擅长的online algorithm的问题, 无奈我对online algorithm也找不到感觉, 专研了很久也没有成果. 最后在看了很多书,了解了很多方法后,我的研究开始集中于图论的近似算法.
我以前学过美术,对图形有着很好的直觉,所以我很喜欢图论.我这个人做事不认真,不追求完美, 近似算法正好符合了我的天性.

我觉得对我影响最大的是第一篇基本上全部由我自己完成的paper. 这篇paper是研究最小生成树的,只不过权值是边权的和和所有内点(非叶子结点)的权和. 这个问题是我的一个师兄在讨论班上提出的,并且给出了一些算法. 那个时候我正在看Vazirani近似算法的书, 并且在研究一些facility location问题的paper. 我开始试着用目前掌握的方法去研究这个问题, 结合了不少技巧,最后得到了改进的结果,为了完善这篇paper,我又考虑了很多情况,分别给出了几个适用不同情况的算法, 最后形成了一篇比较完整的paper. 我很幸运的是我正在学习的技术正好应用在了这个问题之上, 最后导致了这个问题的解决.这给了我一个好的习惯,就是脑子里永远记着几个没解决的问题, 在每学习一个新方法时, 都试着去联系这些问题看看是否有帮助, 恰当的方法往往直接导致了问题的解决.

 

第一篇国际会议文章的发表对建立自信有很强的作用, 我上面说的第一篇paper, 最初结果不完善的时候投到了Approx, 一个很不错的会议,后来被拒了, 做理论的人在好的会议上给的评语非常的直接,就是你这篇paper不够创新或不够重要或不interesting, 很容易给初学者很大的打击.后来我们改进了这篇文章,最后中了一个比较差的会议,但是就只是这个,也给了我很大的安慰,让我知道付出是有成果的.

 

我来说说交流的作用,交流的直接作用是增加知识面,另外交流的作用是使得研究变的活跃,使研究不是那么孤独和枯燥,交流有很多形式,比如听讲座,讨论版,或者是几个人一起闲聊或者想问题. 另外一个交流的重要作用就是找到当然的热点和可以着手的问题, 而这些问题多处于前沿且尚未结局, 不会出现在经典的教科书里, 如果交流时你发现一个和自己背景相近的人在研究某一问题, 那么首先这个问题是让人感兴趣的,另外很大可能是这个问题是有希望解决或改进的,那么你不妨花些时间来考虑一下这个问题.我的几篇文章都是通过这种办法得到的问题. 另外,很多人在做完报告后会提出一些他尚未解决的open problem或者further research, 也是可以试试的.能够用一个人熟悉的知识解决他自己不熟悉领域的问题是令人兴奋的,也是交流的魅力所在. 我在港科大有一次听报告,是关于Game Theory的,我不是很熟悉,报告人最后提出了一个Open Problem,他把game theory的问题转化成了一个图论问题,但不能解决这个问题,报告人在game theory有很好的工作, 但可能并不太熟悉图论, 而我正好对图论有一些研究, 报告的当天晚上我就做出了一个猜想并给了证明解决了这个问题,尽管后来发现当时的这个证明有漏洞,不过猜想是正确的,我很快弥补了这个漏洞,就这样很愉快轻松的与报告人合作了一篇paper.

当有几篇文章已经发表,并且同时有若干问题在自己的研究计划中时,研究就可以说走上了正轨,就已经有了自己的研究感受,知道该如何继续了.

 

数学家Holmas的一篇文章<<怎样做数学研究>>让我很有体会.他说"我喜欢做研究，我想做研究，我也得做研究，我却不愿做下来开始做研究—我是能拖则拖迟迟不肯动手." 他把除了集中注意力思考问题外的事情全部比喻成"削铅笔",他总是希望把铅笔削好再集中精力思考问题,并且把"削铅笔"当成是很好的休闲.我不是一个懒惰的人, 在我最努力的第一年,我也只不过每周集中精力学习不到25小时,到了三年级我更是每周连10个小时都不到.我花费了大量的时间在削铅笔上,比如Starcraft, Warcraft, DotaA,和哥们喝酒腐败,泡bbs农民版和睡觉,甚至花20分钟看Proof from the BOOK上的一个精彩证明都是很好的消铅笔活动. 我不得不承认我的铅笔很多,压力又很小,花了太多时间在削铅笔这上面,我希望以后到了压力大点的地方会有改观.

 

在最初的阶段,我把大部分精力都放在打基础上面,我把算法导论上不懂的章节都看了一遍,并做了很多习题,并且看计算理论和复杂性白皮书.后来第2个学期,就开始看一些进阶的书比如approximation algorithm和randomized algorithm等等,这个时候我就开始分配一些时间看paper和想具体的研究问题上来,我的第一篇文章就是在这个时候完成的.而到研2的时候因为有不少会议要开,就变的浮躁了不少,不过我仍然将学习和自己研究的时间分成50/50, 再以后我都始终保持学习新的知识, 除非有时在突破某个问题, 一段时间的思考集中到顶点的时候我才将全部时间用来研究.我觉得孔子的那句话很好"学而不思则罔,思而不学则殆".

 

说说TCS的的强校和强人吧,这可能对想出国深造TCS的同学的选校和陶瓷比较有帮助.我又不得不申明下我的观点可能会片面,只希望能有帮助

.

先说说美国.

我在这里就不介绍美国计算机的四大强校CMU MIT Berkeley Stanford了,我想任何人拿了这里的offer都不会犹豫的接受的,如果有人犹豫那么可能就是跟超牛的导师了,这样肯定也不需要往下看了...不过这4个里面感觉Stanford的TCS相对弱些,因为Knuth退休中,Motwani主要精力现在在Data Mining上,不过加州的阳光一样吸引着无数的人.

 

不得不提Cornell了,是我的dream school,不过无情的把我拒掉了,里面很多的大师级人物,这里的系头是Eva Tardos,女中豪杰,不让任何须眉,拥有很多可以让一个名不见经传的人一夜成名的工作. John Kleinberg, TCS里的"当红小生", 美国天才奖得主,有很多富有创造性的工作,他研究热门的社会和信息网络,这些工作有组于在现在的internet上寻找规律和设计算法. 而且Tardos和Kleiberg合写了一本<<Algorithm Design>>,是本科生的教材,好像也开始流行起来,中国大陆有影印版,我没看过.还有Shmoys和Williamson,这两个人主要方向是组合优化和近似算法,Shmoys最有名气的工作应该是在Facility Location问题上,他用Rounding and Filtering的办法给出了metric space上的第一个有常数近似的算法(with tardos and Aardal), 被引用无数.Williamson最著名的当属他的将semidefinite programming应用于近似算法了(with Goemans),这个方法写入了这之后几乎所有的近似算法教科书和lecture notes. 这里的Phd毕业生最后到美国Top的学校教书,比如Tardos的学生 Tim Roughgarden好像现在在Stanford做Assoc Prof.

 

其中Princeton理论组拥有无限豪华的阵容, TCS家喻户晓的Arora,新秀Moses Charikar,做计算几何的Bernard Chazelle,图灵奖得主Robert Tarjan. 再加上Princeton显赫的名声,具有无穷的吸引力,我认识的一个MPI的德国学生拿到了基本所有Top学校的Offer,最后选择了Princeton.

以上这6个可以算顶级的TCS理论组.
我下面介绍些理论比较强的学校,这些组在美国计算机系里就叫Theory Group.

 

我首先想到了Rutgers University, 这个学校是DIMACS(center for Discrete Mathematics and TCS)的中心,这个中心里笼络了新泽西州(包括princeton)很多的大牛. 这个学校的理论组更是拥有十多个Faculty, 说几个我听说过的. Endre Szemeredi, 应该是这个组里最出名的人,不过严格来说他是的数学家,搞图论的,有著名的Szemeredi Regularity Lemma,搞图论的每个人都知道,而且这个Lemma在TCS里也有广泛的应用. Mario Szegedy, PCP定理的证明者之一,哥德尔奖得主(因为PCP定理),不过他现在搞什么我也不太清楚. Muthukrishnan,一个搞数据流很出色的新秀, 他在SODA上做的一个数据流的Talk被很多做数据流的人(很多不是TCS的人)学习和引用. 不过好像没怎么听说他的cs要过中国人..

 

Yale是个不错的选择, 比如D.Spielman, smooth analysis的创立者(和一个著名的TCS中国教授 Teng Shanghua,现在在Boston College),并且有很多Planar Separator 和Mesh Generation等方面的其他著名工作. 还有Ravi Kannan, 也非常的牛(TCS还有两个出名的Kannan, 在U penn),
还有Joan Feigenbaum, 是Andrew Yao的学生, 她收了很多中国学生, 可惜在我这年她不招生...

 

Upenn理论组有三个强悍的老印,Khanna Sanjeev, Guha Sudipto, Kannan Sampath,发STOC/FOCS像灌水一样.

我去香港科大交流的时候,我给Mordecai Golin(HKUST的一个assoc prof, Princeton的Phd)看过我最初的申请学校的list, 他把我准备申请的Top list里去掉了Princeton, 说这里虽然老师牛,但不管学生,当然我也知道我申princeton是浪费钱, 把 2nd class list里去掉了Yale,说这里也是老师牛,但不管学生的.然后他在2nd class里给我加上了 University of Maryland-College Park和 New York University.

 

下面就吹吹我要去的UMCP, 严格来说有3个正经做算法的, 一个是Samir Khuller, Cornell毕业的, 近似算法里很出名的人, Ausiello那本书参考文献里(前面提到的)连着2页纸都是他的文章. David Mount,做计算几何的, 比较出名的工作是关于 nearest neighbor和range search的,现在兴趣好像在Kinetic data structure. Aravind Srinivasan好像也是Cornell毕业的,什么都做,不过却都做的不错.  理论组里还有Jonathan Katz, 密码学和复杂性理论新秀, Uzi Vishkin并行算法的大牛. 另外我选择这里是感觉这里的研究生教育比较扎实,导师和学生有很好的合作关系,如果学生天资有限,那么去到顶级名校可能是件痛苦的事情,但在这里却不会被抛弃,而且最后毕业时也能达到一定的高度,这也是我选择这里的原因之一.

 

NYU里TCS最大的优势就是NYU里的Courant数学中心, NYU的应用数学在全美应该是前5, 而他的TCS理论组是属于这个中心的, Richard J. Cole是Courant的副头,是做算法的, 他早年做Dynamic Range minimum query等数据结构,现在好像兴趣到Game Theory了,就是这个人热情洋溢的回复了我的陶瓷信,最后无声的据了我...还有Joel H. Spencer,就是前面写了probabilistic method的那个. 还有Chee K. Yap,也是相当牛的.

 

说说两个常春藤里排最后两个的学校, Dartmouth和Brown.

Dartmouth的cs排名不高,因为它实在太小了,好像就16个faculty,但是却几乎有一半是TCS相关的, Peter Winkler是其中最出名的(也是Mordecai告诉我的),他严格来说是个组合数学家,我读过他的一个工作, 但就这个简单但精致的证明就足够让我们崇拜他的智慧的了. 组里还有
Lisa Fleischer,女的,也是Cornell毕业的,Tardos的学生, 解决过一个著名的问题,就是用组合方法在多项式时间内minimize submodular function, 另外也有很多近似算法方面的扎实工作, 今年又开始对Game Theory感兴趣(好像和 Richard Cole合拿了一个关于Game Theory的NSF的funding), 另外Amit是princeton毕业的一个新秀,做复杂性的, 组里还有Cormen, 就是算法导论的作者CLRS里那个C.

 

Brown是朱老师去美国时带的学校,里面有一个我特别喜欢的教授 P.Klein, 做图算法的,著名的工作有线性复杂度的最小生成树的随机算法, 带权平面图旅行商问题的最优近似算法等等. Franco P. Preparata是计算几何的创世人之一, 是真正的牛导, 台湾中研院资讯所长D.T.Lee就是他的学生. 还有另外一个就是写了我上面说的的probability and Computing的Eli Upfal.

 

最后说说三个UC的学校, berkeley就不说了.
UCSD, 是Graham夫妇呆的地方, 丈夫就是那个Concrete Math的作者之一, 著名的计算几何里的求凸包的Graham算法好像也是他的.他老

婆是中国人,金芳容, Fun Chung Graham, 著名女数学家, 研究图论, 主要是谱图论和复杂网络, 他的很多学生就因为研究复杂网络去了Yahoo, Google, 不过我偷偷告诉你,她是女权主义者,就喜欢女学生.

 

UC-Irvine, 有著名的Eppstein和Goodrich, Eppstein算是计算几何界里人人皆知的人物了,异常的多产,我读过他不少paper, idea经常如天外来客. 他好像学生时代做过AI,第一篇文章发在IJCAI,立刻觉得没了追求,就去做理论了.不过他貌似没带出过什么出色的学生, 可能因为UCI的计算机招不到什么好学生, 我审他家的申请材料给我搞丢了, 我又寄了一份, 又没寄到, 打电话询问,小秘态度及其恶劣...

 

UC-riverside, 这个学校的综合排名的cs排名相对不高,但却有很好的理论组, 比如Chrobak,做在线算法的大牛,在K-server问题上有一系列著名工作, N.Young (Mordecai在princeton的同学) 和Tao Jiang. 有八卦说Tao Jiang ex-wife是复旦某系系花. 这个Tao Jiang本人也玉树临风,他现在主要兴趣是做算法相关的生物信息. 这个系好像对复旦的学生很友好, 我的材料晚到了很久, 它还是态度很好.
 
其他还有很多非常不错的地方, 比如Georgia Tech,有超级大牛V.V.Vazirani, 他是那种可以让人放弃CMU的牛导,我觉得他带的博士中好几个我觉得是TCS中最成功的博士, 再比如Duke, 有著名的P.K.Agarwal, 等等,很难一一列举.

 

说几个美国以外的地方吧.

 

世界上能和美国顶级名校比如MIT抗衡的可能也就是以色列的weizmann研究所和Tel-viv大学了,里面无数的各个学科的领军任务和顶级牛人.

而且这里的研究生教育非常的扎实,毕业生都是同行的皎皎者.不过好像很少的人去那里留学,可能是有关于安全方面的考虑....

 

加拿大的学校里TCS应该首推Waterloo,这里一度是CS北美第一强校,如今有点没落,不过仍然瘦死的骆驼比马大,这里的理论组人数众多,开设的课程十分全面,研究生在这里可以得到很好的教育, 上文提到的Erik Demaine就是这里的Phd.
UToronto里有著名的图灵奖得主,NPC理论的缔造者Cook, Cook对组合优化也有着巨大的贡献, 也是那种可以让人放弃CMU的牛导.

 

欧州里面的学校我知道2个,一个是德国的Saarland University, 这个学校里面有Max-Pluck institute-informatik(MPI) 可以说是欧洲学计算机最好的地方, 我的德国老板Rudolf就是这里毕业的, 我去过这里, MPI是一栋很大的楼,其中Theory Group占了整个2楼, 至少30-40多号人, 这里是一个TCS人才的集散中心,有很多人来这里做visit和做postdoc,在丰富了自己的研究后到其他地方去拿职位. 因此里面研究气氛很活跃, 能接触到各种不同的领域, 这里postdoc都要教课,内容根据自己喜好, 因此能有很多有趣的课程,我去的时候就听了combinatorial geometry的课程,这个课程在一般的大学里是不多见的. 不过这里你也没有自己严格的advisor, 所以可能需要个人比较活跃去融入这个活跃的研究气氛中.

 

另外一个是瑞士的ETH, 理论组也是很大,牛人很多, 绝对是学习TCS的好地方,Rudolf原来就劝过我申请这里,不过我最后没有申请,不过听说这里不能移民,可能很多人因为这个不会愿意来这里.

我没听说过英国有搞算法的人,法国不少,但是对学校了解不多....

===============

先说说读书.

记得当年学习算法小有心得的时候,曾经嘲笑过很多网上的bbs上文章,什么算法的四书五经,葵花宝典等等,其中的不少上有着指点江山的气概,下用着教化民心的口吻,激励并误导着无数的有志青年. 是不是这里就有很多的读者,连算法导论都没好好读过就开始每天2页的专研Knuth的the art of computer programming? 有多少连大O小o都不清楚,就准备决心开始通读Concrete mathematics?又有多少连NPC的概念都不知道,在一遍遍思索着哈密顿路的多项式算法. 如果有,那么我们有很多共同语言,因为其实这3件事情我都做过.

 

如果你正在阅读the art of computer programming(TAOCP),如果你还能勉强读懂,你将毫无疑问的感受到其中组合结构和算法分析的艺术性美感.Knuth以其唯美主义大师风范穷毕生精力的经典著作,目前单在计算机领域我想无它能出其右.
这本书的普及可以说从某种程度来说让更多人认识到了理论计算机科学已经不再是应用数学的一个小小分支,而已经形成了有着其自身魅力的一门独立学科.该书为knuth大爷赢得了Turing奖和无数的赞誉.在中文影印版书皮的背面,有Bill Gates的一句话书评"如果你读懂了TAOCP,请给我投一份简历".在如此多的光环下,人们于是把这个stanford的退休老头子当成神一样来膜拜,把他的书当成圣经一样来阅读. Bill Gate的评论把本该是算法分析研究者应用的字典变成了学习计算机人手一册的手册.很多人把对该书的通读速度和程度变成了衡量自己智力水平的标准.
但是作为21世纪学习TCS的学生,我只想说,这本40年前的书实在是太老了,而且它的难度使得他并不适合做入门和打基础的树,最重要的是它里面讨论的内容已经不再是TCS研究的热点,现在已经很少有人再去分析一下Shell排序的时间到底是多少,也很少人再去算一下3阶无穷小量小o前面的系数.不过无论如何,这本书都是本闲来无事陶冶情操的好书.

 

打基础,国外有很多优秀的教材,我看过的也觉得最好的就是<<算法导论>>吧,我觉得这是不二选择,我个人觉得这本书的地位就是<<心理学与生活>>在心理学的地位,萨缪尔森的<<经济学>>在经济学的地位一样,是及其经典全面的入门教材.有人说内容多了点,但是如果真想搞的话就都读了,全都是基础,我没见过写的更详细更透彻的书,全部算法都有伪代码,都有例子,翻来覆去的解释,无数的插图,还有网上MIT的视频课程.最精妙的是上面的题目,每章后面的problem,不太难,但是却很有启发性,实在是很推荐.

 

算法导论出现前有本流行很广泛的书, Aho,Hopcroft和Ullman的<<the design and analysis of computer algorithms>>,是老一辈人心中的经典,如果算法导论出现后就吧这本书取代了,这本也有影印版,可以参考看看.

 

上来就说了2本好书,就随便再多推荐几本.有了本科高数,线代和概率的基础,再加上算法导论,基本上就可以应付大多数TCS中的高级教材了,事实上这些书也是国外大学研究生的教学用书.我按着不同的小方向来说,我所能说到的基本都是我看过或听说过的.当然限于我的知识面,我也不可能列举的全面.

 

先说说近似算法Approximation algorithm,近似算法和不可近似性这个方向恐怕是目前20多年在TCS中发展最迅速和最活跃方向了,看看这些年主流的理论的国际会议,基本上近似算法和不可近似性占到最大的比例.近似算法说白了也就是用少的时间求出接近最优的解,因为这个世界上太多NPC问题,因此对这么多NPC问题设计多项式时间近似算法显然有重要的理论和现实意义.现在用最多的恐怕就是V.V.Vazirani的那本Approximatino Algorithms了,国外大部分学校上这个课都用这本.这本里每一章讲一个问题,前半本书都用的是combinatorial的方法,後半本用的是mathematical programming的方法.系统讨论不可近似性就是Ausiello等写的这本Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties.这本里面比较详细的介绍了PCP定理和不可近似性的关系.(PCP定理是近年来复杂性理论最重要的突破之一,这个证明被号称是复杂性理论建立以来最复杂的证明,今年出现了PCP的新的证明,不过仍然很复杂..)
更重要的是这本书后面有一个list,里面有几百个NPC问题的近似性与不可近似性的结果,这个list也有网上的版本,这对于查一个问题是否是NPC问题和这个问题的近似性十分的重要: http://www.nada.kth.se/~viggo/problemlist/compendium.html .另外你如果想知道近似算法解谁比较牛比较活跃,看看这本书参考文献,看看谁的名字出现次数多就一个大致的概念了.
兴界出版社影印了一本挺老的书,Hochbaum编的Approximation Algorithms for NP-hard Problems, 也还不错,不过很贵,要90多块.不过这个领域发展太快,有很多重大的突破,很多结果已经都被改进,比如arora和michelle的Euclidean空间的TSP问题的PTAS,再比如Feige的Set Cover问题被证明不能(1-\epsilon)lnn近似等等,在这本书发行的时候还没有.不过这本里面也收录了一些其他书里不常见的,比如schedule问题,度数最小生成树,比如online algorithm,再比如堵丁柱的那个成名作品,就是证明平面上最小Steiner树和最小生成树的比率最小取\sqr{3}/2.

现在很多讨论组合优化的书也开始写很多有关近似算法的内容,因为本质上来讲,近似算法研究的问题都是组合问题,也都是优化问题,其中A.Schrijiver的那3本砖头<<combinatorial optimization>>就是最好的例子,这3本就像TAOCP一样,太厚了,我只是当字典来查查.近似算法还有不少的书,我没仔细看过,没什么给我留下太多印象.

 

这些年对随机数在算法的应用(也就是随机算法randomized algorithm),以及其对计算效率影响的本质,和应用概率方法(probabilistic method)分析组合问题也是TCS热点之一. 最著名的书就是Motwani和Raghavan那本<<Randomized Algorithm>>了,内容比较全,讲了随机算法在各个不同领域的应用,比如数论算法,数据结构,图论算法,online算法等等,这本书是我读过的比较累的书之一.
还有一本是<<Probability and Computing: Randomized Algorithms and Probabilistic Analysis.>>by M. Mitzenmacher and E. Upfal. 也挺出名的.张勤曾象我推荐过mit的David Karger的博士论文,这位同学用随机算法改进了很多基本图论问题的算法,比如min-cut,比如最小生成树的随机线性算法.

 

probabilistic method应该说是P.Erdos大师发扬广大的,用来漂亮的解决了无数的问题.
本质上来讲probabilistic method并不是讨论概率问题,而只是用概率方法来解决问题或证明定理,其中大多数是确定性的问题.
比如我们想证明事件a是存在的, 这是个确定性的问题,没有任何随机性在里面. 但我们可以认为的加入概率, 我们假设每个事件都有一定概率出现,如果时间a的出现概率不为0,那么自然就说明了a是存在的.关于这个有本很经典的书,就是Alon和Spencer的<<probabilistic method>>,写的很容易懂,很多小章节,都是这个方法比较漂亮的应用,是比较好的消遣读物.

写到这里八卦两句erdos,这位老兄以天才多产和合作者众多闻名于数学界和理论计算机界,他一生和同时代的大概500个左右在不同的领域的人内进行过合作,包括数学家,工人,农民和火车上邂逅的妙龄女郎，发表了大约1,500篇论文。我们估算了一下,这需要他平均一个星期左右写一篇文章.并且流行起了一个著名的Erdos Number,意思就是在co-author关系下到Erdos的最短距离.那么直接和Erdos一起写过paper的co-author的Erdos Number就是1。那么Erdos的co-author的co-author的Erdos Number就是2, 以此类推。Erdos Number越小，说明此人和Erdos的学术关系越近。据说，当今世界90%的还活跃的数学家的Erdos Number小于8。搞数学和TCS的人们还会互相炫耀一下自己的Erdos Number。我小炫耀一下,我的Erdos Number是3(Me-F.Rudolf-N.Alon-Erdos):)

有人整理了Erdos很多漂亮的证明编成一本书,叫<<proof from the BOOK>>,里面大部分都是初等的但十分精彩的proof,如果你读了很多技术性很强很繁琐的paper的话,可以看这本书里的证明当成一下调剂.

 

概率论在算法的另外一个应用就是Average case analysis了,我们以前说的随机算法的随机因素是在算法中的,也就是说算法应用随机数,然后我们分析平均效果,但在average analysis中,算法可以是确定性的,我们假设输入是有一定分布的,然后来分析平均的效果.这需要大量的我们在本科概率里没有的数学知识,我知道的两本书,一本是knuth的弟子sedgwick的<<Analysis of algorithms>>, 里面不全是average analysis,还有很多一般的analysis,我没仔细看过, 张勤看过说很多错误. 我看过的一本<<average case analysisi 哦分algorithms on sequences>>,我觉得不错,里面有挺多不是很基础的,比如Matingale,Mellin Transfrom, Poissonization等等.

 

写到这里我自己都感觉TCS真是无边无际的,就算我只把我自己了解的都写出来都需要不知道多少篇幅. 随便捡点我最感兴趣的吧.

 

要说我对TCS的热爱是发源于我学习计算理论和复杂性理论的.这是门计算理论讨论计算本质的,而计算复杂性则是讨论计算资源和计算效率和具体问题间的关系的. 与算法设计需要的精妙技巧不同,计算理论和复杂性理论包含了更多的对问题本质的哲学性思考,从形式语言到图灵机,到NP理论,再到伪随机和交互证明理论,这些中都包含了研究者对问题本质的认识,同具体问题的算法设计相比,它们是在一个更抽象和概括的层次上进行演绎推理. 这些和具体问题的具体算法一起构成了整个TCS的大厦. 我认为一个学生即使有高超的算法设计技巧,如果他不懂得基本的计算理论和复杂性理论,也不能说他懂得TCS. 关于计算理论,我们学校本科用的教材是Sipser的<<Introduction to the Theory of Computation>>,我个人比较钟情与Hopcroft,Motwani和Ullman的那本<<introdcution to automata theory, language and computation>>, 这本有算法导论的风格,很多的例子,讲的非常详细,而且习题很精妙,强烈推荐. 关于复杂性理论,复旦理论组里最著名的一本书叫"白皮书",是Weizmann Institute的Oded goldreich用的网上的一个notes (http://www.wisdom.weizmann.ac.il/~oded/cc99.html). 我看的时候觉得挺不错的,内容挺全,不过很多师兄弟反应说写的一般...另外还有一本Papadimitriou写的<<computational complexity>>,也还凑合,不太全,比如#P啊,Interactive proof,commnication complexity都没有,不过这本有影印版. 堵丁柱写过本中文的,上面好像内容也挺多的,不过我没看过,而且我觉得还是看英文的好,要不会出现terminology的问题.

 

再说说图论算法(Graph algorithms)和算法图论(algorithmic graph theory),他们的区别从字面上可以看出来.我想说明的是这2个东西和目前数学上研究的纯数学图论是有一定区别的,区别就是他们更多的研究图的有关算法的性质,当然他们和纯数学图论是不可分割的.
推荐本比较经典的书 Algorithmic graph theory and perfect graphs, by Martin C. Golumbic 和waterloo用的一个课程(Graph-Theoretic Algorithms)的notes (http://www.student.cs.uwaterloo.ca/~cs762/Notes/index.php),notes写的很简单易懂,而且里面的知识很基本(比如interval graph, chordal graph, SP-graph, planar graph, treewidth等等),但是却很少有比较完整的介绍这些知识的书.
另外有一个网站 http://wwwteo.informatik.uni-rostock.de/isgci/classes.cgi 里面可以查到很多图形类之间的关系,比如interval graph是perfect graph等.

说道perfect graph,就想又八卦下近年来图论的巨大突破 strong perfect graph theorem (参见: http://users.encs.concordia.ca/~chvatal/perfect/spgt.html ) 和突破这个问题的其中2个人 Seymour和 Robertson 和他们的另一个更重大的突破,也就是Graph Minor theory, (见http://planetmath.org/encyclopedia/GraphMinorTheorem.html).该定理在证明前叫 Wagner's conjecture, 事实上连Wagner本人都不相信他本人做的这个conjecture是正确的,足见这个定理是多么令人惊奇. 这个定理的证明这个被称为20世纪最重要的数学遗产之一. 他们的证明共贯穿20几篇journal文章, 总共1000多页,(并且是densely-argued). 比如Tree-width, tree decomposion, pathwidth等图论中的重要概念,都是在graph minor theorem证明中的副产品. 这个定理在TCS中具有非凡的意义, 它直接暗示了许多问题都有固定参数的多项式算法(Fixed Parameter Tractable), 并且现在兴起了一个新的东东,叫Algorithmic graph minor theory, Eric Demaine和他的一个学生Hajiaghayi在做.

 

提到Eric Demaine就开始八卦他,这个同学是81年的,是TCS中小有名气的少年天才.此人20岁在waterloo的博士毕业,现在是MIT的assoc prof. 此人14岁开始写paper,写到现在可能写了有200-300篇了吧,合作者估计也几十上百个了,现在只要是理论的主流会议,只要一开会,就有该生的一堆文章发表. 他的paper我读过不少, 体现就两个字, 聪明. 他那个学生好像也不是省油的灯,博士没毕业也5,60篇文章了,而且全部是好的会议,不是随便发的水文.

TCS实在是包含太多的东西, 比如计算几何, 编码密码, 参数复杂性这些都是发展的非常迅速且庞大的学科,还有近些年兴起的数据流算法,计算经济学,量子计算等等,我也只是了解他们的皮毛. 做学问的深度和广度是一个矛盾体, 也是引起无穷讨论的话题. 我认为在国内这样一个相对落后的环境下(当然除了清华Andy Yao的Group),对很多类似闭门造车的学生来说,在得到指导和交流有限而自身又不是天赋奇才的情况下,一定的广度甚至是深度的基础.这个广度首先给了整个学科的一个框架性的认识,使得可以在这个框架下对某个问题的定位,重要性和难度有一个比较正确的估量,另外对现有方法的了解能够减少在解决具体问题时走的弯路. 另外很重要的一点是, 广泛的阅读可以培养兴趣,欣赏别人发现的漂亮而深刻的结果也是令人兴奋的,这比长时间被一个问题卡住无进展从而尚失研究的兴趣要好的多.

 

并且我也认为一个TCS的学生应该多读书,多懂些东西,而且并不局限于TCS,不要被人家一个manifold, 一个nash equalibrum 或者quantum entanglement这样的基本名词吓到.我花了大量的时间在这些并不属于我研究领域的书上面,当然也并不因为炫耀或用来增加谈资,只是因为我想知道,我想了解现象背后的规律.这种求知的欲望是一个研究者学习和研究的动力源泉.

 

快毕业了,百无聊赖,写点总结性的东西吧,包括不少感受,比较学术,有些专业名词,还有一些科普,一些八卦.

 

写这篇文章的目的是整理总结一个自己的思路,因为三年确实读了学了不少东西,另一个目的是也许能对背景类似的初学者有所帮助.

 

严格说来本科的时候也有接触过算法, 因为学校的程序设计比赛,没花什么精力也十分的业余,现在想想那个时候连算法导论都没听说过,连快速

排序都不能顺利写好,实在是不能称为懂得TCS. 真正全面的接触算法和TCS应该还是在研究生开始的这段时间.

 

作为学习理论计算机(Theorectical computer science, TCS)的一个研究生,我也只能说写点自娱自乐的感受和体会,不能够高屋建瓴,是因为我

学问的片面和研究的肤浅. 另外我的感受并不等同于每个人的感受.我有很多想法, 你如果不认同, 那么请你一起探讨或者一笑置之,如果你没

什么概念, 你或许能从这里找到一点感觉.