## Recursive streaming

This method is discovered by Vladimir Braverman and his adviser Rafail Ostrovsky on 2010. The paper could be found by http://arxiv.org/abs/1011.2571 .

## 高海燕教授的人生感悟

90年代初在加州理工学院的中国人就已经不少了。清华、科大、北大、复旦的人居多。那个时候，留学生们开始转到计算机和电子工程这样的专业是挺普遍的事。所以我刚到加州理工的时候，这也是我让我有些沮丧的事情。总有些中国学生会搞的聚会，碰到了新朋友，就会互相询问，你是哪个系的？我说我是物理系的，很多人的第一反应就是：“你出来了，还干吗读物理呢？”

Bob对我的影响主要有三点。第一是他对我做的研究，一直给予很大的自主权和发挥的空间。他放心大胆地让我去做。这也是我这么多年，对待自己的学生一直采用的方法。当然对于个别遇到困难的学生，我会更多的关注。一般情况下，我还是很放心大胆的让学生去做。第二点，我的导师，他的大门总是向我敞开。你遇到任何问题和他讨论，只要他不出差，不教课，随时随地我可以和他交流。把我的想法和他讨论。

Bob对我一直非常支持。我在波士顿麻省理工学院做实验时，孩子生病了，我想飞回加州照看他。Bob二话没说，就打电话让秘书给我买机票。我当时非常感激他的支持和体贴。当自己做了教授，开始管理研究经费时，这种感激是更加有过之而无不及。尤其遇到自己的经费不足的时候，我就会时常想起当年孩子生病，导师买机票的事，看起来很小，其实不是特别容易做到。另外Bob的性格也很风趣，非常开朗。

## Setup a dynamic DNS

There are many dynamic DNS service, a good example is called NO-IP.org.

One can setup a dynamic DNS host on that one, then no matter what your ip-address changes, your host name is always fixed.

## Set up Squid Proxy for Unblock-YOUKU

The following article is from:

https://github.com/zhuzhuor/Unblock-Youku/wiki/%E8%AE%A9Squid%E5%B8%A6%E6%9C%89Unblock-Youku%E5%8A%9F%E8%83%BD

I Copy it here only my convenience, if you find it inappropriate, please tell me, I’ll delete it immediately.

***************************************AUTHOR: ZHUZHUOR**************************************************************

# 让Squid带有Unblock Youku功能

## squid conf的配置

[tyw@Nerv squid] $vi youku.rules  然后把pac的rule给拷贝到这个文件里面。 不过pac的规则的正则和squid的有些区别，下面是改好的 ^http://v.youku.com/player/ ^http://api.youku.com/player/ ^http://v2.tudou.com/ ^http://www.tudou.com/a/ ^http://www.tudou.com/v/ ^http://s.plcloud.music.qq.com/fcgi-bin/p.fcg ^http://hot.vrs.sohu.com/ ^http://live.tv.sohu.com/live/player ^http://hot.vrs.letv.com/ ^http://g3.letv.cn/ ^http://data.video.qiyi.com/ ^http://220.181.61.229/ ^http://61.135.183.45/ ^http://61.135.183.46/ ^http://220.181.19.218/ ^http://220.181.61.213/ ^http://220.181.118.181/ ^http://123.126.48.47/ ^http://123.126.48.48/ ^http://vv.video.qq.com/ ^http://geo.js.kankan.xunlei.com/ ^http://web-play.pptv.com/ ^http://web-play.pplive.cn/ ^http://dyn.ugc.pps.tv/ ^http://inner.kandian.com/ ^http://ipservice.163.com/ ^http://zb.s.qq.com/ ^http://ip.kankan.xunlei.com/ ^http://music.sina.com.cn/yueku/intro/ ^http://music.sina.com.cn/radio/port/webFeatureRadioLimitList.php ^http://play.baidu.com/data/music/songlink ^http://v.iask.com/v_play.php ^http://v.iask.com/v_play_ipad.cx.php ^http://tv.weibo.com/player/ ^http://www.yinyuetai.com/insite/ ^http://www.yinyuetai.com/main/get-video-info ^http://.*.dpool.sina.com.cn/iplookup ^http://.*/vrs_flash.action ^http://.*/?prot=2&type=1 ^http://.*/?prot=2&file=/ ^http://vdn.apps.cntv.cn/api/get ^http://api.3g.youku.com/layout ^http://api.tv.sohu.com/ ^http://access.tv.sohu.com/ ^http://3g.music.qq.com/ ^http://mqqplayer.3g.qq.com/ ^http://proxy.music.qq.com/ ^http://api.3g.tudou.com/ ^http://mobi.kuwo.cn/ ^http://mobilefeedback.kugou.com/ ^http://tingapi.ting.baidu.com/v1/restserver/ting\?.*method=baidu.ting.song ^http://api.3g.youku.com/v3/play/address ^http://api.3g.youku.com/openapi-wireless/videos/.*/download ^http://api.3g.youku.com/videos/.*/download ^http://play.api.3g.tudou.com/v3_1/ ^http://iface2.iqiyi.com/php/xyz/iface/ ^http://180.153.225.136/ ^http://118.244.244.124/ ^http://210.129.145.150/  ok, 保存退出 ZZ。 下面来到squid的conf文件。  [tyw@Nerv squid]$ vi squid.conf


acl uyouku url_regex -i "/usr/local/squid/etc/youku.list" #这里是你youku.list的 full path
never_direct allow uyouku
cache_peer 127.0.0.1  parent 12345 0 no-query default
#cache_peer proxy_url  parent proxy_port  0 no-query default
cache_peer_access 127.0.0.1 allow uyouku
cache_peer_access 127.0.0.1  deny all


[tyw@Nerv yyy] $./ub.uku.js --port=12345 --local_only  好了这样就可以了 ## 启动squid 或者reload 这个不用我多说了吧？ ok 现在squid和 unblock 运行的很完美了 Posted in Technology | Leave a comment ## Mangrov Graph Reachability in Log Square space Polinomial Time Use the DFL method. Posted in Complexity Theory, Computer Science | Leave a comment ## JAG model: a restricted computation model JAG Stephen A. Cooks and Charles W. Rackoff proposed a restricted computational model — Jumping Automata for Graphs (JAG) — in their 1980’s paper “Space lower bound for the maze threadability on restricted machines“. JAG is basically a system consists of the following: A finite set of states with a distinguished start state $q_0$ and accepting state $q_a$, a positive integer $P$ and a set of $P$ objects called pebbles, which are numbered 1 through $P$, and a transition function $\delta$, which controls the behavior of $J$. Particularly, for a $d$-JAG, the input to $J$ is a $d$-maze $\mathcal{G} = $. The computation history is fully described by its instantaneous description (id), $$, where $Q$ is the current state of the automata, and $\Pi$ is the mapping function that maps each pebble to a node. Based on the program instruction a programer written, $\delta$ determines next move based on $Q$ the coincidence partition of pebbles. For example, there 5 pebbles, the first 4 are in node 1 and last on node 2, then the partition is {{1, 2, 3, 4}, {5}}. The next move could be either 1) a “Jump”, $(Q^\prime, P, P^\prime)$, which specifies the new state $Q^\prime$ and new $\Pi^\prime$ function with a only correction is that move $P$ from the original node to $\Pi(P^\prime)$; or 2) a walk, $(Q^\prime, P, i)$, with pebble $P$ walk through edge $i$ (yes, based on the label of the graph) to a new node and entering new state $Q^\prime$. These are the only information a JAG could read from the Graph. The space used by such a machine is defined as $P\log N + \log Q$, which is the space need in a general Turing machine to store an id. JAG is powerful enough such that one could implement a Savitch algorithm on it. The proof in Cook & Rackoff paper gives a recursive construction: $J_k$ is the JAG with $3k+3$ pebbles. It’s easy to prove that $J_0$ could move pebble $P_1$ to any of the distance $2^{k} = 1$ nodes. After that, if assuming the the claim works for $J_k$ such that it could move $P_1$ to and node within distance$2^k\$ from the starting node of $J_k$, they constructed a $J_{k+1}$ based on 8 $J_k$ and $3k+6$ pebbles. So the states needed for $Q(J_{k+1}) = 8 Q(J_{k}) + O(k)$ and hence space needed for such an algorithm is $O(\log^2N)$, which gives a space up bound for a directed graph.

However, JAG is too restricted that even for a tree, it has a lower bound $\log^2N/\log\log N$. (I didn’t read this part yet).

NNJAG

Chung Keung Poon however improved JAG to a Node-Name JAG (NNJAG) such that $\delta$ could decide next move based on $\Pi$ it self other than the coincidence partition of $\Pi$. This model is much powerful than $JAG$ is a way that it could could ge the information of the name of the node. While it’s still restricted since it could be easily fulled by the labeling scheme of a graph.

Poon proved the lower bound of JAG based on a graph called skinny tree $G(\alpha_1, ..., \alpha_p)$, with each $\alpha_i \in \{0, 1\}^d$. $G$ is completely determined by $\alpha_1, ... \alpha_p$ in a recursive way: $G(\alpha_1, ..., \alpha_{k+1})$ is a simple skinny tree $G(\alpha_{k+1})$ with each node replaced by a copy of $G(\alpha_1, ..., \alpha_{k})$. A simple skinny tree $G(\alpha)$ is a out degree 2 tree such that the path is edges labeling by each digit of $\alpha$. An skinny tree example is given as the following figure (from Parry Husbands’s Master degree Thesis) with $\alpha_1 = 011$ and $\alpha_2 = 101$. A $G(\alpha_1, ..., \alpha_p)$ could be easily solved by a NNJAG with $p+1$ pebbles with a so called leader helper algorithm. For the simplest case, 2 pebble (a leader and a helper) NNJAG and a $G(\alpha_1)$:

1) put the two pebbles at the beginning of the tree, let the helper go through one edge;

2) then go through one edge again from the node.

3) If after the 2), the pebble is on the same node, which means the helper is on a leaf, jump it back to the leader, restart 1) through the other edge.

4) if the pebble is not on the same node, move the leader by walk through the edge as the helper did in step 1). Jump back the helper to the leader. Return to step 1).

For more complex case, the helper-leader algorithm is defined in a recursive way such that to traverse a super tree  $G(\alpha_1, ..., \alpha_{k+1})$, use one pebble as the leader, and use $k+1$ pebbles as the help to test the super node — the copy of $G(\alpha_1, ..., \alpha_{k})$.

To prove the lower bound, Poon claims that for a $p$ pebble NNJAG,  for any program (instruction set),  there exists a skinny tree $G(\alpha_1, ..., \alpha_{p})$, start from put all the pebbles in the beginning node, the NNJAG cannot move any of its pebbles to the goal node of the tree (defined as traverse the tree). Since the NNJAG model could know the name of where the pebble is, we therefore could figure out a labeling scheme such to fool it. Poon proposed a labeling scheme for the nodes and edges that satisfy 2 conditions,  in a family of skinny trees

A1: the node with a same name in all the skinny trees has the same path length from the beginning of the tree.

A2: go out through label $i$ from a node with label $j$ will always end up at node with label $k$.

Such a scheme is existed, a simple example is the labeling the nodes as a $p$ digits number with base $2d+1$$n_1n_2...n_p$. With each its digit $n_i$ indicated where the super node $G(\alpha_1, \alpha_2, ... \alpha_{i-1})$ (for $i=1$, it’s the actual node of $G(\alpha_1)$) is located in its super tree $G(\alpha_{i})$.

The main lemma says

To be continued…

Reference:

## Ford–Fulkerson Algorithm

Matrix67 today mentions a Ford–Fulkerson Algorithm, very interesting. If you cannot read Chinese, I translate a part of the Algorithm here.

Fig-1

As shown in the Fig-1, there’s a directed graph, which is used representing the network of the traffic. The number on each arrow is the maximum allowed current at a certain time. If cars are driving in this network, one condition (current conservation) must always be satisfied: the total income should equal to total output at any node except for s and t. Now the problem is what’s the maximum flow current from node s to node t? A attempting solution might be like following:

Fig-2

where the numerator is the attempting current and the denominator is the maximum allowed current of the arrow. Such a flow distribution will yield a total current of 6. However it’s definitely not the maximum current of the network. For example, if we add another path s->a->b->c->t for current 1, we’ll get current 7.

Fig-3

Mathematician Lester Ford, Jr. and Delbert Fulkerson gives a solution to this problem, the so called “Ford–Fulkerson Algorithm”:

On Fig-3, we could add another “path” s → b → a → c → t , in which b->a and a->c are along the opposite direction of the original paths. So they have negative current. Applying this path, we’ll have

Fig-4

We successfully increase the total current by 1 and still satisfied current conservation. Such a path is called “extensive path”. As long we could find additional extensive path from s to t, the maximum current is not reached. While we can prove that if no additional extensive path can add, we have the maximum total current. Fig-4 shows the maximum current solution of the above problem.

There are a lot of applications of this algorithm in Operation Research.