 | | |
| | |
|
Spaces home  天天天蓝PhotosProfileFriendsMore |  Tools   |
|
天天天蓝笃志而博学 切问而近思
November 18 deadline刚赶完deadline，第一次投STOC
其实能有东西投这样的会，我就已经很知足了
这次deadline赶的非常惊心动魄，一个接着一个的发现bug
越来越痛苦的fix bug，最后一次fix把原来poly的结果变成指数了，而且第二天还发现即使这样还有bug
然后很崩溃很崩溃，一直到deadline前两天还是搞不定。。。
然后最后两天跟老板讨论半天，又换了一个metric重新搞
最后能够smooth地证出来很出乎我的意料
不过finally，done
学到的东西只有一个，做theory应该keep on thinking
虽然连续n天n星期n月想不出来解决的方法是件非常让人郁闷的事情
但是也许只有那样才能在最后的时候突然顿悟吧
一堆人都在赶deadline，发现theory的圈子还是很小的
弄完了看blog，正好看到mihai新一篇的blog，很有同感啊
他今年一篇都没投，呵呵，很少见。
http://infoweekly.blogspot.com/2008/11/stoc.html November 06 11月6日October 22 CSTCS(4)Title: Flows and Disjoint Paths in Networks
Speaker: Sanjeev Khanna Edge Disjoint Paths Problem(EDP): Given graph G and source-sink pairs, the goal is to route a maximum # of pairs using edge-disjoint paths.
Usage: can be used to solve maximum matching, Complexity result: 1. For two pairs, if G is directed, it is NP-hard. 2. If G is undirected, any constant number of pairs can be solved Approximate result: Greedy algorithm has ratio O(m^{1/2}); Multicommodity flow relaxation(LP) Allow congestion: O(1)-approximation with congestion \Theta(log n/loglog n); Hardness result Basic idea of approximation: Show fractional solution with short flow paths New idea: using well-linked set. A EDP instance can be reduced to a collection of instances of well-linked set will small-loss of optimal solution. Title: Discounted Deterministic Markov Decision Processes Speaker: Uri Zwick Tel Aviv MDP：可以看作一个图上的游戏，点属于两个游戏玩家，边上有权值，当前点的拥有者可以决定下一步往那个邻居走，走过的边上的权计入分数（按零和的方式）。
Discounted: each step has a ratio \alpha discount
Deterministic: after each step, the node arrived is deterministic, not a distribution. Main result: an O(mn)-time algorithm for finding optimal strategies for discounted, infinite-horizon, Deterministic Markov Decision Processes (DMDP), where n is the number of vertices (or states) and m is the number of edges (or actions). This improves a recent O(mn^2)-time algorithm of Andersson and Vorobyov 87'. Deterministic MDP = truck driver's problem Discounted DMDP = unreliable truck driver's problem. Open problem: 1. Equivalence of non-discounted DMDPs and discounted DMDPs. 2. Different discount factors for different edges? 3. (non-deterministic) Markov Decision Processes? CSTCS(3)Title: One Time Programs (Cryptography in presence of side channel attacks)
Speaker: Shafi Goldwasser Weizmann & MIT Basic assumption of cryptography: there exists private key and computation is "black box" based on this private key. But, it is not true. we can extract secret information by physics observation: timing, power consumer, etc (called computational side channel attacks). Two types of possible leakage: (1)computational side channel: leakage of information of secret keys as a result of performing a computation on the said data;(2)Memory Leakage: no computation has been done. Leakage is only because the data is in the memory. 这个talk主要是用来解决第一个问题的，提出了one time program，需要用hardware，并且希望尽可能减少在hardware上的计算（因为任何计算都可能泄露secret）。用的gadget叫ROK，是一个hardware，上面有两个key，读取一个key的同时会erase掉另一个。怎么做的没明白。。。 Title: Towards Universal Semantic Communication
Speaker: Madhu Sudan MIT 讲的是我们怎么能跟外星人交流（也就是交流双方都不懂对方的语言）^_^ 去年的CTW也有一个这样的talk。第一部分考虑的是：Bob is computational limited but wishes to solve hard problem, and Alice can solve the problem and helpful (try to communicate with Bob to tell him the answer). Model: Bob wants to know whether x\in S. Alice knows the answer. But they do not know the language of the other person. Different from IP: in IP, Bob does not trust Alice. Main result: If S is PSPACE-complete, then there exists a S-universal Bob. 这个topic蛮有意思的，虽然不知道有什么具体意义？网上有ppt Title: Resilient Mechanism Design
Speaker: Silvio Micali MIT 唯一一个mechanism的talk，非常fancy。但是因为很fancy，导致我lost掉了，连main result是什么都没有明白。。。 Title: Natural Algorithms
Speaker: Bernard Chazelle Princeton 这个talk很飘逸，内容和风格跟santafe那套挺像的。讲自然界现象的，比如怎么描述鸟群的运动。也是一个很fancy的talk，有很多fancy的视频:) 虽然里面也讲了一些数学方法，但是我其实不太明白为什么放在一个theory的会上面。 Title: The Truth About Quantum Computers Speaker: Umesh Vazirani Berkeley 讲了一个叫做Adiabatic quantum optimization的东西，不懂。。。不过说目前的物理实验显示Polynomial Adiabatic algorithm for 3SAT是可能的。感觉还蛮偏物理的，似乎不像很多做quantum的工作完全建立在一个well-defined的数学模型之上，跟物理没啥关系。只是感觉，总的来说不懂。。。 CSTCS(2)Title: Semidefinite Programming and Approximation Algorithms: A Survey of Recent Results Title: A Computational Theory of Clustering Title: Subconsensus task: Renaming is Weaker than Set Agreement Title: Hashing and the New Multicore Algorithmics
October 17 10月17日-CSTCS（1）先写三个
Title: The Algorithmic Lense: How the Computational Perspective Is Transforming Science 很飘逸的讲了TCS和各种各样东西之间的联系，比如数学、物理、生物、统计、经济、社会科学。。。
Title: The Art of Reduction (or Depth through Breadth)
Speaker: Avi Widgerson IAS 相对前一个没有这么飘逸@@ 从NP规约讲起，主线是3-SAT hard to approximate的结果，介绍了IP, PCP,ZKIP等与各个复杂性类之间的关系，permanent, hardness amplification。Ms还说其中的想法借用了Reingold很著名的SL=L结果中的想法。基本上就是survey，给我们讲了这个方向的发展历史。
这两个talk的slides都可以在网上找到，有兴趣的自己看吧，肯定比我写的要清楚@@
Title: Steiner Trees
Speaker: Ronald Graham, UCSD（中文说得非常非常好！） Input X: finite set of points in the plane
Minimum steiner tree of X: minimum spanning tree of set V contains X
History: 1926,1938,1951,1956,1957, ( On the history of minimum spanning tree...) 1965.Fermat, Steiner point.
Basic result: degree <=3,
Can be partitioned into subtrees which is pure steiner trees (only leaves are from X).
Euclidean Minimum Steiner Tree: NPC
Approximate: By Minimum Spanning tree. Ratio 1/2 -> 0.8, 0.8241(a root of a polynomial with degree 12...)
0.866(Du Ding Zhu)
Polynomial time approximate algorithm:
If only consider points in two parallel line, it is still NPC.
What about simplex S^3? 1995
For any finite set X in R^3, the ratio is >= 0.78419. If true, it is the best we can do.
There exists set X, no finite steiner tree can do better than it.
The rectilinear plane: also NPC, history.
Bonach-Minkowski planes, consider different metric. Large than 2/3.
Conjecture: <= \sqrt(3)/2, with equality if and only if B is ellipse.
The previous results are most discussed in math. In TCS, we consider: Graph G(V,E), weighted. Minimum Steiner Tree for vertices set X.
Do not have PTAS unless P=NP (1998) The proof involves a deep connection between NP and approximate algorithm based on PCP. Steiner trees for random weighted graph MST: phase transition (2008)
Open problem
10月17日随便写点东西，今天没心情折腾学术-_-b
过去的一个月似乎过得特别快，CTW开一周的会，接着十一到处玩，然后折腾在brown做的那点东西，试图想要搞成一篇paper的样子，过程中发现有些困难我不记得怎么绕过去了，或者也可能当时根本就没能绕过去，是我自己想错了。。。然后就是开始开CSTCS，跟brown的老板讨论，一会儿进一会儿退的progress，什么时候才能真真正正有个没有bug能说清楚的结果？昨天陪professor及其家属们去旅游，天安门故宫北海胡同国家大剧院，蛮好玩的。乱七八糟的聊天，有时候扯点学术。我还是很喜欢聊天的时候忽然有人冒出来一句theory的专用词汇/短语的笑话，有点暖暖的感觉。
这个会来了20位教授，都是理论方向顶级大牛，这点上很倾佩老板的能力，毕竟能同时请到这么多大牛可不是容易的事情。有4位jj，应该说是4对couple。。。然后不可避免地想起alvin总说的定理，我就越发觉得fz。。。谁给我举个反例出来，我bg顿饭，路费自理哈^_^
最近的心情总是因为progress的起起落落而上上下下，总觉得这样不好，不过最后还是避免不了。。。基本上已经把在brown做的那些东西推翻光了，现在处于一切重新开始的状态中-_-b 原本老板说考虑投今年11月中的STOC或者明年初的PODC，现在我觉得任务还很遥远，结果还没搞定呢，先别忙着研究怎么写paper:(
不知道是不是很多好朋友都在找工作的缘故，我最近越来越觉得当学生的日子没多久了，然后就总是想趁着现在可以随意翘班的日子出去玩@@ 北京的秋天很漂亮，但是漂亮的秋天已经没几天了，嗯，所以要抓紧玩^_^ 研究研究周末去什么的地方玩，目前想去市里西面的一个第四纪冰川擦痕遗迹。另外下周周中想找个时间去香山~~~应该都是骑车，到时候看体力状况，有没有人想同行？
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Invite as friend
Profile
Blog
Photos
Lists