November 2005 Archives
2005-11-26 18:39:59
Study Group: Approximation Algorithms, by Vijay V. Vazirani
In fact, this semester, all activities of theoretical group are stopped,
because the leader of our group is too busy. Therefore all frist-year graduate
student of theoretical group in our lab
doesn't start meeting until now.
Nevertheless, prof .Tang asked us the direction of master thesis of us at last lab. meeting, and remind us that the topic of master's thesis should be decided at the second semester of first-year.
After discussing, we went to ask for the opnion of leader of our group, and he gave us some suggestions. Actually, he thought that we should start from reading conference paper, but our adviosr is too busy to attend this meeting; the formal theoretical meeting might be impossible this semester.
On the other hand, we don't what we should read.
Personally, I am insterested in the optimization and other techniques for optimization like approximation and heuristic. (I don't know which class the randaom algorithm is in). But, the optimiztion is the basic goal of algorithm (the other side of decision problem), so that I do not say anything.
(According to my observation in the LEAST seminar, professor R.C.T. Lee seems to think the heuristic not cool, and professor Biing-Feng Wang call it stupid algorithm.....:) )
However, I start to browse the conferences, collect the infomations of it, and I find that almost all important proceedings of conferences are published by Springer. The strange thing is that library of NTHU does not buy the access accounts for SpringerLink.....XD
It means, the proceedings I can read are only SToC, SoDA, FoCS.
I find out some conferences, about the combinatorics and algorithms, which tend to math not CS, e.g., British Combinatorial Conference, EIDMA symposium, but I can't find out the publication of conference. (Does Annual reports be publication of conference?) It seems different world.....
Nevertheless, prof .Tang asked us the direction of master thesis of us at last lab. meeting, and remind us that the topic of master's thesis should be decided at the second semester of first-year.
After discussing, we went to ask for the opnion of leader of our group, and he gave us some suggestions. Actually, he thought that we should start from reading conference paper, but our adviosr is too busy to attend this meeting; the formal theoretical meeting might be impossible this semester.
On the other hand, we don't what we should read.
Personally, I am insterested in the optimization and other techniques for optimization like approximation and heuristic. (I don't know which class the randaom algorithm is in). But, the optimiztion is the basic goal of algorithm (the other side of decision problem), so that I do not say anything.
(According to my observation in the LEAST seminar, professor R.C.T. Lee seems to think the heuristic not cool, and professor Biing-Feng Wang call it stupid algorithm.....:) )
However, I start to browse the conferences, collect the infomations of it, and I find that almost all important proceedings of conferences are published by Springer. The strange thing is that library of NTHU does not buy the access accounts for SpringerLink.....XD
It means, the proceedings I can read are only SToC, SoDA, FoCS.
I find out some conferences, about the combinatorics and algorithms, which tend to math not CS, e.g., British Combinatorial Conference, EIDMA symposium, but I can't find out the publication of conference. (Does Annual reports be publication of conference?) It seems different world.....
2005-11-26 08:02:54
Recent Topic: Crisis of CS
Several days ago, I read the CACM ( Volume 48 , Issue 11); there were three
articles which caught my eyes, i.e., Recentering computer
science
The recent decreases of enrollment in computer science programs signal a chasm between our historical emphasis on programming and the contemporary concerns of those choosing careers.
Crisis and opportunity in computer scienceThe future of the field depends on winning back student enrollment, public interest in technology, and government research funding.
Assessing the relative influence of journals in a citation networkSome journals are perceived as sources of knowledge; others serve as storers of knowledge. Learning the strengths and persuasions of journals is of value to academia, scholars, and publishers.
Then, only few days, Computing Research Policy Blog gave an another bad news, "Foreign Enrollments in CS Plunge".2005-11-26 07:54:26
Note on clique-like algorithm
Couple of months ago, my advisor told me to think about the cilque-like
algorithm, i.e., on the gerneal graph, find out all subgraphs that are not
maximal cliques but look like maximal cliques by adding some edges. Actually,
this problem, finding the maximal clique problem on general graph, is NPC, so
that it might be need approximation or heuristic algorithms.
One of practical usage is on the network biology(or system biology), the new and hot (maybe) field in which NTHU (i.e., our lab.) want to join.
At that time, I surveyed for the key words, and found that there was no paper about this topic. Nevertheless, yesterday, I found two papers about this topics unexpectedly.
They use the differnt key words....:)
One of practical usage is on the network biology(or system biology), the new and hot (maybe) field in which NTHU (i.e., our lab.) want to join.
At that time, I surveyed for the key words, and found that there was no paper about this topic. Nevertheless, yesterday, I found two papers about this topics unexpectedly.
They use the differnt key words....:)
-
Massive Quasi-Clique Detection, James Abello and Mauricio G. C. Resende
and Sandra Sudarsky, LATIN '02: Proceedings of the 5th Latin American
Symposium on Theoretical Informatics, 2002, pages 598--612.
On mining cross-graph quasi-cliques, Jian Pei and Daxin Jiang and Aidong
Zhang, KDD '05: Proceeding of the eleventh ACM SIGKDD international conference
on Knowledge discovery in data mining, 2005, pages 228--238
2005-11-25 08:37:00
What's good research?
Half semester passed. I read some papers about the project of prof. Yen.
One of questions is what good research is? Like Robert Tarjan's explanation of "elegant", the definition of good research might be not so clear; it consists of several different elements which might conflict.
The taste might be one of those criterion. In my current topic, some problem seems easy, however, I didn't find any simple solution of it; the only one which I know, is based on the variant of linear programming. I tried various ideas to solve it, but no one was good; those looks too complex. What I want is to find an algorithm as simple as the problem. The word "simple" is for the meaning of concept not for time complexity, however the existent algorithm proved the problem in $P$ (actually, in linear time).
That's why I asked at the beginning. I dare not to ask what kind of problems are important, but I want to ask what kind of problems are meaningful or at least not meaningless. If certain problem was researched long time ago and no new related publications for several years, then how to evaluate this problem?
The foci of the same problem are different between computer scientist, combinatorists and mathematicians. What is the correct or proper attitude to treat such problems?
In fact, I have a little doubt on the my work. Essentially, there are two thoughts in my mind. First, I started to blame myself for the drought of results. Second, I doubt that spending more time on this problem is worthful.
One of questions is what good research is? Like Robert Tarjan's explanation of "elegant", the definition of good research might be not so clear; it consists of several different elements which might conflict.
The taste might be one of those criterion. In my current topic, some problem seems easy, however, I didn't find any simple solution of it; the only one which I know, is based on the variant of linear programming. I tried various ideas to solve it, but no one was good; those looks too complex. What I want is to find an algorithm as simple as the problem. The word "simple" is for the meaning of concept not for time complexity, however the existent algorithm proved the problem in $P$ (actually, in linear time).
That's why I asked at the beginning. I dare not to ask what kind of problems are important, but I want to ask what kind of problems are meaningful or at least not meaningless. If certain problem was researched long time ago and no new related publications for several years, then how to evaluate this problem?
The foci of the same problem are different between computer scientist, combinatorists and mathematicians. What is the correct or proper attitude to treat such problems?
In fact, I have a little doubt on the my work. Essentially, there are two thoughts in my mind. First, I started to blame myself for the drought of results. Second, I doubt that spending more time on this problem is worthful.
2005-11-23 16:55:24
Note on GSRC Bookshelf
One of final projects of the course, VLSI physical design automation, which I
attended is to write a placer, and to write a report including results of
benchmarks of ISPD2005.
The formats of data structures of benchmarks is GSRC Bookshelf's formats which are designed to be simple and easily human readable, as well as conveniently parsable respect to industry standard file formats. (Ref.: Placement Formats, rev. 1.2 )
There are much uselful information and tools in GSRC Bookshelf, but I don't know how to use it; its orgnization of website confused me. Some URLs broke and some documentations seemed out of date.
Anyway, the frist thing is to understand the formats and wirte a parser.
The formats of data structures of benchmarks is GSRC Bookshelf's formats which are designed to be simple and easily human readable, as well as conveniently parsable respect to industry standard file formats. (Ref.: Placement Formats, rev. 1.2 )
There are much uselful information and tools in GSRC Bookshelf, but I don't know how to use it; its orgnization of website confused me. Some URLs broke and some documentations seemed out of date.
Anyway, the frist thing is to understand the formats and wirte a parser.
-
Availability
Status of New Data Formats For VLSI CAD
Wirelength-driven
Standard-cell Placement
Placement
Formats, rev. 1.2, AUX file format
1.0
Executable
Placement Utilities
2005-11-16 22:26:46
Robert Tarjan
Ref.: HP Labs -
Inventor interview - Robert Tarjan : The art of the algorithm
Personally, I think the theorem prover is greater. (ref.: http://www.csie.ntu.edu.tw/~kmchao/research.html ,"理論計算機科學家(Theoretical computer scientist)通常可分為兩類型:定理證明者(Theorem prover)及問題解決者(Problem solver)。" by Kun-Mao Chao)
Btw, the figure, Artist's conception of a self-adjusting search tree, is really funny.
Some Quotations
In the interview that follows, Tarjan talks about creating an elegant algorithm, how he solves difficult problems, his passion for teaching and his views on the future of technology. The master mathematician also describes what he believes differentiates an impractical algorithm from a truly useful one.
Guru! Some scientists have very good reputation; they are really smart; the main different of guru and those outstanding scientists might be that guru's contributaion is more general and more seminal.Personally, I think the theorem prover is greater. (ref.: http://www.csie.ntu.edu.tw/~kmchao/research.html ,"理論計算機科學家(Theoretical computer scientist)通常可分為兩類型:定理證明者(Theorem prover)及問題解決者(Problem solver)。" by Kun-Mao Chao)
Btw, the figure, Artist's conception of a self-adjusting search tree, is really funny.
Some Quotations
Also, elegant solutions are much easier to generalize, to extend to other problems. My goal is to find general approaches and solutions, not ad hoc tricks.
I try various ideas and keep thinking about it until I’m sick of it. Then I stop thinking about it and come back to it later. To do mathematics you have to get used to pounding your head against the wall for a long time -- when you stop, it feels good. Ninety percent of the time your ideas don’t work, but then the right idea emerges. This can be very exciting.
2005-11-15 15:35:52
Edge of Computation Prize
Ref.: The
Geomblog: Edge of Computation Prize
Another prize of computation that I never heard.
And I have totally no idea about quantum computing. However, I congratulate David Deutsch winning this prize. The announcement is here.
Another prize of computation that I never heard.
The Prize recognizes individual achievement in scientific work that embodies extensions of the computational idea — the design space created by Turing. It is a 21st Century prize in recognition of cutting edge work — theoretical, experimental, or both — performed, published, or newly applied within the past ten years.
And I have totally no idea about quantum computing. However, I congratulate David Deutsch winning this prize. The announcement is here.
DAVID DEUTSCH is the founder of the field of quantum computation. Paul Benioff, Richard Feynman, and others had written about the possibility of quantum computation earlier, but Deutsch's 1985 paper on Quantum Turing Machines was the first full treatment of the subject, and the Deutsch-Jozsa algorithm is the first quantum algorithm.
I envy those people's gift and works. Those work not only make people think, "He/She is damn smart! I can't be as good as him/her.", but also make people esteem him/her. Because their works extend the idea of that we recongized.2005-11-12 16:10:02
NCTS Symposium on Network Biology
NCTS
Symposium on Network Biology is hosted by National Center for Theoretical
Sciences(NCTS) in Taiwan. This orgnization is devoted to the development and
research of theoretical science, i.e. math, physics, in Taiwan.
Yesterday, I attended the symposium. I thought that it will be a big symposium, because prof. Chuang said that this is the frist symposium for system biology scholars in Taiwan. (Chairman said this symposium is urged by prof. Li)
When I were in the symposium, I were surprised that it was in the small conference room of the General Building III of NTHU. The seating capacity of the room is at most 40~50 persons.
I guess that is because the area in Taiwan is beginning. It might be the reason of delightful atmosphere of whole program.
Schedule:
I am interested in prof. Huang's talk, Elucidating the essentiality of essential genes. I have no background of biology so that I have no idea about the importance of this problem in biology. However, I like this kind of research about asking the question of essential part in its discipline.
I had talked with a graduate student of Ph.D. degree in my lab. His background is biology. His impression of computer science is that computer scientists are interested in the problem more then biological meaning behind the problem. For example, our director, prof. Tang, is a computer scientist in the area of design of algorithms, so that he is interested in the biological problem which can be modeled as mathematical puzzles, not the meaning for biologist.
It might imply the low impact factor of CS, and always be queried CS not science but engineering.
I think, just like infomation theory, some theory in CS such as computational complexity theory, study some aspect or essence of this world. Those are the branches of math and physics, and its intersection. Those researchs tend to study the problem in the essence of computation and information, it should be included in the extent of science, but some areas about network and database should be included in engineering. (I know few in those theories, it just my impressions.)
Yesterday, I attended the symposium. I thought that it will be a big symposium, because prof. Chuang said that this is the frist symposium for system biology scholars in Taiwan. (Chairman said this symposium is urged by prof. Li)
When I were in the symposium, I were surprised that it was in the small conference room of the General Building III of NTHU. The seating capacity of the room is at most 40~50 persons.
I guess that is because the area in Taiwan is beginning. It might be the reason of delightful atmosphere of whole program.
Schedule:
10:00-10:40 喻秋華 (國衛院) Genomic regulatory networks underline the Mesendoderm specification and cancer formation
10:40-11:20 陳博現 (清大電機) On the molecular noise filtering of gene networks
11:40-12:10 許昭萍 (中研化學) Constructing quantitative models from qualitative experimental results
13:30-14:00 吳韋訥 (陽明醫技) Biomodular analysis of proteomics
14:00-14:30 吳家樂 (亞洲大學) Modular structures of protein-protein interaction networks
14:45-15:15 黃宣誠 (陽明生資) Elucidating the essentiality of essential genes
15:15-15:45 劉維中 (中研生醫) The importance of enzymes and their occurrences: from the perspective of a network
15:45-16:15 林仲彥 (國衛院) Deciphering protein network in systems biology approach
I am interested in prof. Huang's talk, Elucidating the essentiality of essential genes. I have no background of biology so that I have no idea about the importance of this problem in biology. However, I like this kind of research about asking the question of essential part in its discipline.
I had talked with a graduate student of Ph.D. degree in my lab. His background is biology. His impression of computer science is that computer scientists are interested in the problem more then biological meaning behind the problem. For example, our director, prof. Tang, is a computer scientist in the area of design of algorithms, so that he is interested in the biological problem which can be modeled as mathematical puzzles, not the meaning for biologist.
It might imply the low impact factor of CS, and always be queried CS not science but engineering.
I think, just like infomation theory, some theory in CS such as computational complexity theory, study some aspect or essence of this world. Those are the branches of math and physics, and its intersection. Those researchs tend to study the problem in the essence of computation and information, it should be included in the extent of science, but some areas about network and database should be included in engineering. (I know few in those theories, it just my impressions.)