Tuesday, January 29, 2008

Interesting papers

  • Justin G. Chen, Scott D. Kominers, Robert W. Sinnott: Walk versus Wait: The Lazy Mathematician Wins: arXiv.org,
    • 懶是上策?!
  • Artur Czumaj and Christian Sohler: (Draft) A survey on sublinear time algorithms.
    • 另一篇關於 subliear time algorithms 的 survey
  • Ziv Bar-Yossef, Ravi Kumar: Sampling Algorithms: Lower Bounds and Applications. STOC'01
    • 看看這篇說不定能幫助我更加深入了解 sampling algorithms
  • Rajeev Motwani, Rina Panigrahy, Ying Xu: Estimating Sum by Weighted Sampling. ICALP'07
    • 喔?!這一篇算是蠻新的吧!
關於第一篇的線上comments: http://tinyurl.com/2vudqd

第一篇 paper 主要是證明了如果步行前往目的地仍可及時到達,那麼只要決定以步行前進,中間遇到每個公車站牌最好都不要停下來,也就是說,一決定撩下去就不要三心兩意,直接一路走到底就是。 paper 裡面的最終結論之前,推論最好先原地等待公車,直到用走的都無法準時到達之前才放棄等待。

所以說標題下的結論,其實是指一開始先在第一個站牌原地等公車,因為走到前面幾站等並不會比較快到目的地。而且並不是要傻傻的等,如果用走的都快來不及了,就得認命趕快用走的。

關於第二篇, BarrosH 說他看過,所以我們經過一點討論之後,使我對於一開始的 "Basic Sublinear Algorithm for searching in a sorted list" 更加了解了。原來他的 doubly linked list 還多了一個輔助的 array 當 index 啊。

關於第三篇,不愧是 STOC 出品,還蠻難的。不過看得出作者已經寫的很仔細了。一開頭有介紹 randomized decision trees,跟傳統的 deterministic decision trees 很像,只是同一個 input 可能有很多條從 root 到 leaves 的可能路徑,每個 internal node 包含了 query 以及擲骰子的可能性。裡面重要的名詞,包括 disjoint inputs,各式各樣的 approximation concepts, Block Sensitivity 的概念。光是搞懂這些基本定義,就得花上不少時間。


No comments: