Abner's Postgraduate Days

Ref. : Tetsuo Shibuya, Computing the nxm shortest path efficiently, the ACM Journal of Experimental Algorithmics, Volume 5, Article 9, 2000.

computation of all the shortest paths between multiple sources and multiple destinations on various networks is required in many problems, such as the traveling salesperson problem (TSP) and the vehicle routing problem (VRP). This paper proposes new algorithms that compute the set of shortest paths efficiently by using the A^* algorithm. The efficiency and properties of these algorithms are examined by using the results of experiments on an actual road network.

Based on shortest paths problem, there are some methods to solve this kind of problems, i.e., Dijkstra Algorithm, A^* Algorithm, Bidirectional algorithm. The A^* Algorithm is an extension of Dijkstra Algorithm. Like other A^* algorithms, it estimate the length of shortest paths to simplify computations. The idea of Bidirectional algorithm is very simple, it compute two tables with Dijkstra Algorithm from two sides, source and destination vertices, and then find out some edges to connect shortest paths in two tables.

However the A^* and bidirectional algorithms are for 2-terminals. The author generate the problem to compute all shortest paths between two sets, source set S and destination set T. The author simply extend the two algorithms; use $h(v)=min_{i} h*(v,t_i)$ as ``dual feasible estimator'', and estimator is obtained by k-d tree [Bentley 1975].

The new bidirectional algorithm could be taken as a variation of A^* algorithm by introducing estimator $h'(v,t)= min{c, h(v,t)}$ where $c$ is a constant, and computed the estimator by their Algorithm 5. This algorithm is more complicated.

I have some questions. The first question is that I don't understand the meaning of ``dual feasible estimator.'' The other one is the new bidirectional algorithm, or named by author, bidirectional-method-based A^* algorithm. It said

Note that we here construct the network Voronoi Diagram of destination set T. The network Voronoi Diagram of T is a subdivision of V to ${V_i}$ where the shortest path length from v \in V_i to t_i is not larger than those to any other vertices in T.

I don't know if it means, after executing algorithm 5, we need to construct the network Voronoi Diagram of destination set T, or just execute bidirectional algorithm.

Ref. : Weisstein, Eric W. "Voronoi Diagram." From MathWorld--A Wolfram Web Resource.

I wrote a short summary about some interesting talks in Workshop on BioAlgorithmics and RECOMB conference. I picked five or six talks that are interesting me.

Actually, I found two kinds of approaches of researching in this workshop. One is to consider additional informations to improve the performance, and the other one is to change the metric. Of course, there are many other researches, but talks which belong to these two kinds of approaches impressed on me.

The first kind of researches might make the software more and more big and complex; the second kind of researches might lack the better criteria of performance....

1. Write a sildes for introducing talks in Workshop on BioAlgorithmics to my adviser.
2. Read section 4~ of Dr. C. M. Lee's Thesis.
3. I have read Tetsuo Shibuya's paper, but I have questions.
4. Recently I read a survey paper of computing equilibrium in game theory, but it is hard to understand. I refered to Seminar on Algorithmic Aspects of Game Theory hosted by Christos H. Papadimitriou and course Introduction to Game Theory given by Markus Mobius. Maybe I need a textbook of game theory!?

I am reading prof. Sudan's lecture notes of 2-module course of PCPs taught at the Scuola Matematica Interuniversitaria. There are some other interesting topics, VC dimension, Expander Graphs, Convex Geometry, etc, but I might without time to read them.

This semester, I got grades 97 for Compiler Construction, and 85 for Randomized Algorithms. I am happy for it, it means that I have collected 23 credits of 24 credits. I could take my plan in practices.

Just summaries some techniques, approaches, ideas, or principles in Randomized Algorithms Design.

• Sampling :
• Yao's Minimax Principle : Computational Complexity: Favorite Theorems: The Yao Principle

  The Yao principle states that the best probabilistic strategies for the players will achieve exactly the communication bounds as the best deterministic strategy over a worst-case distribution of inputs.

• Principle of Deferred Decisions : This principle uses an idea that random choices are not all made in advance but the algorithm makes random choices as it needs them. Ref. : DELIS-TR-0095 Proving conditional randomness using the Principle of Deferred Decisions, by Alexis C. Kaporis, Lefteris M. Kirousis and Yiannis C. Stamatiou.

  Notice that keeping a register unexposed is not in itself sufficient to guarantee that its contents stay random. Randomness is destroyed if one could even implicitly infer additional information about the current contents of an unexposed register from the combined knowledge of the current and previous contents of exposed registers. Therefore, in all cases, a proof is necessary that no new information about the current values of unexposed registers can be implicitly revealed.

  On the other hand, it is permissible for a given update step to implicitly reveal information about previous contents --- subsequently overwritten --- of an unexposed register. This does not destroy randomness, in that it is the updated structure that must be proven random.

  One might object that a safer way to prove conditional randomness claims is by rigorous counting arguments, rather than through the Principle of Deferred Decisions. In complicated situations, however, counting arguments are practically impossible.

• Foiling the Adversary : The idea is like Yao's Minimax Principle to avoid the worst-case instance. It seems like hashing different algorithms to different cases.
• Fingerprint : Map the complex, full, and hardly comparable description of objects to some partial descriptions which easy to compute.
• Abundance of Witnesses : It seems like the generalization of idea of Fingerprint. This approach might suit for decision problem specially. The idea is to find abundance of witnesses which are able to check whether the input has certain property. ``Abundance'' means the number of witnesses is large and constant.
• Amplification : Amplify the success probability by repeating the independent computation on the same input.(entire or partial)
• Rounding : Relaxation Linear programming with Random Rounding.

Ref. : Juraj Hormkovic, Design and Analysis of Randomized Algorithms, Springer.



Some people called a sub-field of algorithmics ``randomized algorithms,'' i.e., algorithms accessing random bits, but I don't know what the difference is between randomized algorithms and techniques with randomness?

The ideas of randomized approaches cover really wide in algorithmics, like property testing, sublinear algorithms, and cryptography.

Courses:

• NCTU CS, Randomized algorithms, Shi-Chun Tsai, 2006 Spring. (Slides in Chinese)
• NCTU CS, The Probabilistic Method, 2004 Spring, Shi-Chun Tsai. (Slides in Chinese)
• UIUC 598: Randomized Algorithms (Fall 2005), Sariel Har-Peled (Lecture Notes)
• Harvard CS 225: Pseudorandomness, Salil P. Vadhan, Spring 2004. (Scribe Notes)
• Randomized Methods in Computation, Lecture Notes [Spring 2001], Oded Goldreich
• CMU 15-859(M): Randomized Algorithms, Anupam Gupta and Shuchi Chawla. (Lecture Notes)
• CMU 15-359: Probability and Computing, Spring 2006, Mor Harchol-Balter and John Lafferty
• T-79.250 Combinatorial Models and Stochastic Algorithms (4 cr), Spring 2003, Pekka Orponen
• Berkeley CS271: RANDOMNESS & COMPUTATION, Alistair Sinclair (SCRIBE NOTES)
• RANDOMIZATION AND OPTIMIZATION, period IV (March-May), 2001, Devdatt Dubhashi (containing many readings).

Markov Chains and Monte Carlo:

• Markov Chain Monte Carlo for Computer Vision -- A tutorial at ICCV05 by Zhu, Delleart and Tu
• An Introduction to Markov Chain Monte Carlo, Prof. Carlos C. Rodriguez
• Advanced Monte Carlo Methods I & II An ETHZ/SAM Course
• Monte-Carlo Course Materials, Jonathan Goodman
• Math 8843 - Convergence of Markov Chains, Ravi Montenegro
• Mini-Course on Markov Chain Monte Carlo, Eric V. Slud

Property Testing:

• Property Testing Seminar

  This seminar deals with the relatively young but rapidly growing field of combinatorial property testing (most recent STOC conferences feature several papers on property testing and other sub-linear approximation algorithms, so the importance of this field in Computer Theory can by now be regarded as established).

• Bibliography of Property Testing, Sublinear Algorithms, Uncertainty, Streaming, Tools
• Ronitt Rubinfeld : Sublinear Time Algorithms
• Combinatorial Property Testing, Oded Goldreich

Others:

• Random Walks and Electric Networks, Doyle, Peter G.; Snell, J. Laurie.
• Derandomization: A URL collections.
• Bibliography on the random generation of combinatorial structures

Dr. Tetsuo Shibuya, assistant professor of the Laboratory of Sequence, Analysis, Human Genome Center, University of Tokyo, will visit NTHU. My adviser planned to let our senior member to learn some techniques at Dr. Tetsuo Shibuya's Lab, and we will present our researches for him.

I arrived Taiwan yesterday. The nine days long tour in Singapore ends. Actually, I don't like Singapore's food, but it is not easy that such small country could be so florescent.

I saw many excellent researchers in Workshop on BioAlgorithmics. This workshop emphasized on the invited talks, so that they invited people like Ron Shamir, Ming Li, and Tao Jiang. I guessed the organizer at least spent NT$ 1,500,000.



Since I am interested in algorithms, I mostly expect Ron Shamir and Ming Li's Talks. There is a unexpected talk given by Andreas Dress, he presented without slides, he used the whiteboard. After I came to Taiwan, I google the informations of Andreas Dress, therefore I know that Andreas Dress is a famous researcher.

Wen Lian Hsu are also invited to present his researches in machine learning, however I am not interested in machine learning.

New generation homology search, Ming Li, University of Waterloo, Canada

The similarity metric and the distance metric, Kaizhong Zhang, University of Western Ontario

Motif discovery from both ends: combinatorial and probabilistic, Mehmet M. Dalkilic, Indiana University, USA.

1. Michael Nielsen :: Introductory lecture notes on quantum information and computation. Those slides are good, but "a rough text for the lectures" is hard to understand.
2. MIT EECS 6.443J / Physics 8.371J / 18.409 / MAS.865: Quantum Information Science, Isaac Chuang & Peter Shor. (They offered scribe notes from students(?))
3. Berkeley CS294-2, Quantum Computation Fall 2004, Umesh Vazirani

   Prior coursework in quantum mechanics is not essential. This interdisciplinary subject draws on techniques from theoretical computer science, mathematics, and quantum physics. Students with a strong background in any one of these areas are welcome to attend.

4. Berkeley C/CS/Phys191, Qubits, Quantum Mechanics and Computers, Birgitta Whaley
5. MIT OpenCourseWare, 18.435J Quantum Computation, Fall 2003. Prof. Peter Shor. (They offered scribe notes from students(?))
6. CMU, Quantum Computation and Information Theory Course, Robert Griffiths. (Its handout is too concise, only one page. However, its supplementary seems not bad)
7. Caltech, Physics 219/Computer Science 219 Quantum Computation, John Phillip Preskill
8. Caltech Ph125, Quantum Mechanics, Hideo Mabuchi.
9. Michael Nielsen: Interesting problems: The Church-Turing-Deutsch Principle
10. ``An introduction to quantum computing for non-physicists,'' ELEANOR RIEFFEL and WOLFGANG POLAK, ACM Computing Surveys, Volume 32 , Issue 3, September 2000, Pages: 300 - 335.

20060721 Update: Ref.: "An introduction to quantum computing for non-physicists", ACM Computing Surveys, ELEANOR RIEFFEL, WOLFGANG POLAK.

Richard Feynman's observation that certain quantum mechanical effects cannot be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used these quantum effects. This speculation proved justified when Peter Shor described a polynomial time quantum algorithm for factoring intergers.In quantum systems, the computational space increases exponentially with the size of the system, which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new nontraditional programming techniques.The aim of this paper is to guide computer scientists through the barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to exploiting the power of quantum parallelism are explained. We conclude with a discussion of quantum error correction.

20060907 Update: Shtetl-Optimized: The quantum-complexity bathroom reader. And Bibliography on Quantum Computation

Today, the semester is over; I came to office of prof. Yang this morning for checking my grades of Compiler Construction, and fortunately I got A. Therefore it is time to stop and think.

The first thing I am considering is that should I attend only one course next semester? The last two days, I could read something in which I am interested. I really feel good about it. I would like to learn more things and attending more courses, but I will have no time to learn other things, if I attend too many courses. My interests are many and different, thus it might not suit to me to attending a lot of courses.

In the past, I thought I am a lazy man so that I should attend more courses to make myself work harder, but this approach doesn't work in practice. Now I want to change my approach to attend only one course at next semester, and keep rest time to study other fields.



Today I read two papers ``Randomization and Feedback Properties of Directed Graphs Inspired by Gene Networks'' and ``Computing Over the Reals: Where Turing Meets Newton''. And I plan to read ``An introduction to quantum computing for non-physicists''.

I would like to write a note about Complex Network at first, but I found C. R. Shalizi's notebook of Complex Network, and Panayiotis Tsaparas's courses and reading lists about Information Networks and Models and Algorithms for Complex Networks.

Thus it seems meaningless for spending time in digging on Internet....:)

1. Complex Networks: An old post about Theoretical Computer Science, Volume 355, Issue 1, Complex Networks (6 April 2006)
2. The Structure and Function of Complex Networks, M. E. J. Newman, SIREV, Volume 45 Issue 2, pages 167--256,2003.
3. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D.-U. Hwang, Complex networks: Structure and dynamics, Physics Reports, Volume 424, Issues 4-5, , February 2006, Pages 175-308.

The third and second papers are very long. I had read a lecture note of Mark Newman, i.e., Statistical Physics, Mark Newman, Budapest, 17 to 20 July 2001. I pretty like his writings. His handout about power-law is on-line available.

Update 2006-09-24:

I found webpages of complex network on AMS. And prof. Ricard V. Sole's homepage, he maintain many useful links, he is research professor of The Complex Systems Lab, located at the Universitat Pompeu Fabra.

I am in Lab. Although it is 03:18 AM now, it is not worth posting an entry for it. The reason I want to post an entry is that two senior members of our Lab discussed a new project with several professors (including prof. Tang) on-line via Skype at 02:00 AM.

They are really industrious....ORZ

However, I want to go to bed now. I am tired, but I feel good.

I finish some papers and ``Criminal Minds'' Season 1 tonight. To spend time on the those things is great!

Ref.: Philip Ball, Econophysics: Culture Crash, Nature 441, 686-688 (8 June 2006).

I had heard the term Econophysics, and I were told that it will get hotter and hotter, but this article told us that things changed. One of troubles seems uneven quality,

The literature is often littered with garbage. We can find gauge-field theories of finance, quantum options and so on. In short, anything goes.

Another problem might be the concept of modeling. The author told the story of Brian Arthur, an economist worked at the Sante Fe Institute.

"The economy is out of kilter most of the time," says Arthur. That, he says, accounts for one of the virtues of econophysics. "The core of economic theory is still built around equilibrium models, but most models in econophysics are non-equilibrium ones."

However, like other fields about complex systems, those seems couldn't explain anything about the underlying idea, besides results of computer simulation.(?)

Ref.: Garry Hamilton, Virology: The gene weavers, Nature 441, 683-685 (8 June 2006)

It said that the viruses might influence the evolution directly. It might transmit the informations of DNA, or create.

Hatfull and Hendrix now argue and many others concur that viruses are continually and randomly recombining with whatever DNA they might encounter while infecting a cell, be it phage or host DNA. Thus cells are stewing pots where viruses are continually reinventing themselves thanks to a blind but highly creative process that is not only spitting out novel combinations of genes, but is also generating brand new genes possibly never before seen in nature.

Ref. : Korber B, LaBute M, Yusim K (2006) Immunoinformatics Comes of Age. PLoS Comput Biol 2(6): e71

This paper contains a lot of terminologies of bio-science like B lymphocytes, T lymphocytes, MHC, HLA, TCR, etc. I am totally unable to understand, however I tried to got some informations form it.

With the burgeoning immunological data in the scientific literature, scientists must increasingly rely on Internet resources to inform and enhance their work. Here we provide a brief overview of the adaptive immune response and summaries of immunoinformatics resources, emphasizing those with Web interfaces.

This is a review paper about tools.

This review summarizes a sampling of particularly useful and user-friendly Web-based computational tools and search-able databases. The computational methods and databases are described and referenced in the text, and Web links are provided in summary tables.

Although I don't know anything about immunology, but it seems like the bioinformatics which developed from demands of tools for analysis the massive data and literature.

P.S. What is different between biology and immunology? Why do we need a new name for it?

Another related article: Dominik Wodarz, Ecological and evolutionary principles in immunology, Ecology Letters, Volume 9 Page 694, June 2006

Experimental immunology has given rise to detailed insights into how immune cells react to infectious agents and fight pathogens. At the same time, however, the interplay between infectious agents and immune responses can be viewed as an ecological system in vivo. This is characterized by complex interactions between species of immune cells and populations of pathogens. This review discusses how an understanding of the immune system can be aided by the application of ecological and evolutionary principles: competition, predation, and the evolution of viruses in vivo. These concepts can shed light onto important immunological concepts such as the correlates of efficient virus control, immunodominance, the relationship between viral evolution and the development of pathology, as well as the ability of the immune system to control immunosuppressive infections.