Abner's Postgraduate Days

I didn't blog recently, because there are many things in the last couple of weeks. The final exam of Randomized Algorithms, presentation of workshop, and final exam of Compiler Construction.

I opened my research journal this morning. The last note is written ten days ago. I don't feel good for it. I planned to attend two courses next semester, microeconomics and optimization theory. This semester I attended two courses actually, but I feel very tired. I am considering to cancel microeconomics.

Besides, I am considering the paper I would present at the LEAST seminar.

• Samorodnitsky, A. & Trevisan, L. Gowers uniformity, influence of variables, and PCPs STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, ACM Press, 2006, 11-20
• Feige, U. & Kilian, J. Zero Knowledge and the Chromatic Number Journal of Computer and System Sciences, 1998, 57, 187-199

  Helger Lipmaa: Summer 2004. Lecture course Zero-knowledge and some applications. This slides might be helpful for understanding Zero-knowledge.

• Randomization and Feedback Properties of Directed Graphs Inspired by Gene Networks, M. Cosentino Lagomarsino, B. Bassetti, P. Jona, Proceedings of the CMSB conference, Lecture Notes in Bioinformatics, Springer, 2006

Ref. : Market Based Control of Complex Computational Systems

This EPSRC funded project (in the Novel Computation call) intends to apply market-based paradigms to the design, control and evolution of complex distributed computational systems. The targetted applications include resource allocation in utility data centres, decentralised control of content delivery and multiple robotic systems. It is a collaboration between several leading UK universities, specialised in economic mechanism design, multi-agent systems and evolutionary computation.

Ref. : Michel X. Goemans , David P. Williamson, proved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995

I will report at 6/24 for Workshop on String Processing and Approximation Algorithms. My topic is "More on Randomization -- Semidefinite Programming and Derandomization". I will emphasis on SDP, since it is a extension of Linear Programming which is a systematic approach for algorithmics about approximation.

According to the introductory of this paper, they are the first one to applied SDP on the design and analysis of approximation algorithm.

Our algorithm depends on a means of randomly rounding a solution to a nonlinear relaxation of the MAX CUT problem. This relaxation can either be seen as a semidefinite program or as an eigenvalue minimization problem. To our knowledge, this is the first time that semidefinite programs have been used in the design and analysis of approximation algorithms.

I want to introduce some applications of SDP in computer science, B. Mohar and S. Poljak's ``Eigenvalues in Combinatorial Optimization'' is a very good material.

In the last decade many important applications of eigenvalues and eigenvectors of graphs in combinatorial optimization were discovered. The number and importance of these results is so fascinating that it makes sense to present this survey.

Actually I had read some parts of this paper, because I needed to report chapter 5 of the book Complexity and Approximation written by G. Ausiello et. al. at Algorithm Seminar II. However, I found some interesting things in the parts which I didn't read.

One of most interesting things is that the authors proved theorem 3.1.1 by transforming the problem to mathematical program. It is the second time that I saw the technique.

The other interesting thing is the SDP itself.

In combinatorial optimization, the importance of semidefinite programming is that it leads to tighter relaxations than the classical linear programming relaxations for many graph and combinatorial problems.

In preparation of reporting, I found that there are many works which have been done after 1995, and there are many survey papers about SDP, but I still don't know How the SDP works.

The first question is that what the tighter relaxations means? Even though the solution of relaxed program will be more close to optimal solution of original program, in design and analysis of approximation algorithms we still need to chose a specific rounding method to obtain the corresponding solution, since the analysis of performance ratio is the key role of approximation algorithms and it has important influence on performance ratio.

In this paper, the key concept should be the ``n-D sphere random rounding'', and the power of SDP is not so significant, however it is interesting that their random rounding method match the SDP so good that it is hard to say the algorithm is based on SDP or based on n-D sphere random rounding.

The second question is that the theoretical background of SDP, some concepts of SDP, like LP on Cone, are hard to understand for me. I checked out Boyd's ``convex optimization'' from library, but many ideas in it are too abstract to ``understand''. I know definitions of some terms, but I couldn't get the corresponding geometric image in mind mind.

For my personal taste, good algorithms mean efficient, elegant, and proven. However, in the real world, there are a lot of intractable problems. In practical perspective, heuristic algorithm might be the maximum amount of algorithms, especially in some fields as VLSI CAD, AI, etc. How do we compare and measure the difference of algorithms?

The course, "research method", in college of science or engineering, seems a sugar course. Nevertheless, this course in college of social science is a very important course.``The Craft of Research,'' by Wayne Booth, et. al., this well-known book seems for students of social science, although there are some advices useful, this book lacks the research method of science. However, books about scientific method like E. B. Wilson's ``An Introduction to Scientific Research,'' are more suitable for physicists and biochemists, which work on wet bench, but not for computer scientists which work on dry bench. It doesn't means that nobody cares the importance of empirical methods. In fact, there are some people dedicated in the field Algorithm Engineering and Empirical Methods for CS.

Ref. : Moret, B.M.E., "Towards a discipline of experimental algorithmics". Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, M.H. Goldwasser, D.S. Johnson, and C.C. McGeoch, eds, DIMACS Monographs 59, 197-213, American Mathematical Society, Providence, 2002

Natural scientists run experiments because they have no other way of learning from nature. In contrast, algorithm designers run experiments mostly because an analytical characterization is too hard to achieve in practice. (Much the same is done by computational scientists in physics, chemistry, and biology, but typically their aim is to analyze new data or to compare the predictions given by a model with the measurements made from nature, not to characterize the behavior of an algorithm.)

This paper also discuss drawbacks of current theoretical analysis of algorithm, i.e., the neglected coefficient of big-O might be too large to be impractical. It is a notorious drawback of big-O, but the author give a example, Robertson and Seymour gave a cubic-time algorithm with proportionality constants are $10^{150}$.

"Section 5. Experimental Setup" is what I really want to learn, but the author doesn't spend too much efforts on it. The author just enumerate some potential pitfalls:

• The choice of machine (caching, addressing, data movement), of language (register manipulation, built-in types), or of compiler (quality of optimization and code generation).
• The quality of the coding (consistency and sophistication of programmers).
• The selection or generation of instances (we must use sufficient size and variety to ensure significance).
• The method of analysis (many steps can be taken to improve the significance of the results as well as to bring out trends)
• Uninteresting work: comparing programming languages or specific platforms, in particular unusual ones; comparing algorithms with widely different behavior (linear and quadratic, say); etc.
• Bad setup: testing up to some fixed running time or space without verifying whether the asymptotic behavior has manifested; testing too few instances; using rough code without any attempt at optimization and measuring running times; using ``found code'' without any documentation (a temptation these days on the net); ignoring existing test suites; ignoring existing and widely used libraries; etc.
• Bad analysis or presentation: discarding data that do not fit without any explanation or even warning; presenting all of the data without analysis; using comparisons to undefined ``standards'' (e.g., to the system sort routine).

We all know that Fields Medal is the most important prize of Mathematics, but not everybody know the contributions of those winners.

I had surveyed about this and wrote a entry of this blog, entitled "Winners of math medal study combinatorics", however it is just a simple collection.

Luca Trevisan started discussed about his recent work and Gowers uniformity on his blog, hence I started note the mathematician William Timothy Gowers.(I found that Bela Bollobas is his Advisor!!!)



According to the record, he was winner of the 1998 Fields Medal for research on functional analysis and combinatorics.

His interesting article entitled "The two cultures of mathematics".

This article was for an IMU volume entitled Mathematics: Frontiers and Perspectives. It is basically a defence of combinatorics against some of the criticisms commonly made of it. Judging from some of the reaction to the article, it is perhaps worth saying that when I quote the views of `theoreticians', it is because I agree with them. My aim is not to dispute their criteria for what constitutes worthwhile mathematics, but rather to show that combinatorics meets these criteria (suitably, and I hope reasonably, interpreted).

I don't really interested in Computational Geometry, however I had considered that I might be able to transform my problem to some problem on Computational Geometry about one month ago, so that I searched for some course resources about it, but I decided to forgo this problem eventually.

The following URLs are what I found before. I just wrote it down here.

• Computational Geometry CS 497 JE: Spring 2002 Jeff Erickson
• Computational Geometry Course Materials
• Home Page for CMSC 754 (Computational Geometry) , by Samir Khuller
• CS 252 -- Spring 2005 Computational Geometry and Graph Drawing
• Spring 2003, Computational Geometry, Robert Pless
• The Geometry Junkyard: Coursework and Teaching Material

I read the sildes, that is titled by Algorithmic game theory and the Internet, of Amin Saberi.

This sides has two sub-topics, Game Theory and Algorithms, and Complex networks. However, I don't know where the interests are? Problems in first part, e.g., Market Equilibrium, seems without novelty. It looked like some new version of problems in Operations Research.

The second part of this slides is the huge size network like Internet. Both topics are interesting, but I don't know why it could be a new field? How much tastes came from game theory?

When I surveyed the game theory in ACM DL, I found that many papers are from the fields related to distributed computing. I thought it is because the invention of P2P network. However, which are the other fields we can apply the idea of game theory to?

In A DRAFT of a Proposal to Rename the Game Theory Society by Ehud Kalai, there are some sub-fields related to computer science directly, i.e.,

5. Algorithmic and artificial theory study issues of computational, informational and behavioral complexity in games played by live or by artificial players.

7. Combinatorial games deal with mathematical issues unique to games.

Now I don't know what is algorithmic game theory. However, some clues make me feel that it might suit for me as topic of master thesis.

Since I mentioned it at last post, I surveyed on this field and note following.

However, I didn't find offical definition of algorithmic game theory. It seems related to game theory, internet, mechanism design, and market model.

• Theoretical Computer Science, Volume 313, Issue 3: Algorithmic combinatorial game theory.
• Harvard EconCS Group, Algorithmic Mechanism Design

  Work in algorithmic mechanism design classically focuses on the complexity of centralized implementations of game-theoretic mechanisms for distributed optimization problems. There are many interesting open problems, that at a high-level must resolve both computational and economic constraints.

• CMSC37100 Algorithms, Games, and the WEB, by Bruno Codenotti
• CS364A: Algorithmic Game Theory, by Tim Roughgarden
• Management Science and Engineering 336: Market Models for Networked Systems, by Ramesh Johari
• CS294 Seminar on Algorithmic Aspects of Game Theory, by Christos H. Papadimitriou
• Computable-general equilibrium (CGE) models
• CS682 Algorithmic Game Theory, Fall 2005, by Eva Tardos

People: C. H. Papadimitriou(computing equilibria),Vijay V. Vazirani(Market Models?), Amin Saberi, Eva Tardos(Games in Networks).

Followings are some papers related to it.

• A coupling algorithm for computing large-scale dynamic computable general equilibrium models, Zili Yang
• How to route and tax selfish unsplittable traffic
• Selfish load balancing and atomic congestion games
• Network games
• Algorithmic mechanism design

Update: Zengjian Hu's collection.

Update: I used another term "computational" to search.

• Mehta, A. Algorithmic Game Theory
• Markakis, E. Computational Aspects of Game Theory and Microeconomics
• Empirical Game Theoretic Models: Computational Issues
• Computational Game Theory. Lecturer: Yishay Mansour. older version
• Seminar: Topics on the border of CS, Game theory, and Economics. Instructor: Noam Nisan
• Another links collection, Game Theory and Computer Science by Helger Lipmaa
• Game Theory .net - Resources for Learning and Teaching Strategy for Business and Life
• M. Kearns, Tutorial Slides on Computational Game Theory. NIPS 2002., BNAIC 2003 Tutorial, COMPUTATIONAL GAME THEORY.
• Research Resources for Graphical Models of Multiagent Game, by Jie Bao.

20060614 Update:

• CPSC455/555: Economics and Computation, Joan Feigenbaum
• CS364B: Topics in Algorithmic Game Theory, Tim Roughgarden (Gates 462) and Jason Hartline (Microsoft)

20060823 Update: I had printed the survey paper ``Computation Of Equilibria In Finite Games,'' R. McKelvey and A. McLennan. It is a chapter of ``Handbook of Computational Economics,'' 1996. This paper is hard to read because it formulate the problem in very abstract method. And they didn't concern the time complexity. However I browsed ``DBLP: Christos H. Papadimitriou'' I found prof. Papadimitriou's papers are more easier to read.

• Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra: On the complexity, of price equilibria. J. Comput. Syst. Sci. 67(2): 311-324 (2003)
• Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani: Market Equilibrium via a Primal-Dual-Type Algorithm. FOCS 2002: 389-395
• Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra: On the complexity of equilibria. STOC 2002: 67-71

Professor Xiaotie Deng is an expert on this field.

20060828 Update: Game-Theoretic Aspects of Computer Science, N. Linial, in "Handbook of Game Theory with Economic Applications", vol. II, chapter 38, (R. J. Aumann and S. Hart eds.) North Holland, 1994, pp. 1340-1395.

20061206 Update: The Geomblog: Author ordering and game theory mentioned an interesting phenomenon about author ordering of research papers. The best case is that we ordered the authors by their contributions, but the powerful people might got some benefit from this protocol. The lexicographic ordering is also not good enough, since people will assume the guys with names earlier contributed most!

This kind of problems relates to the subfield of game theory -- Automated mechanism design, i.e., designing the rules of the game (aka. mechanism) so that a desirable outcome (according to a given objective) is reached despite the fact that each agent acts in his own selfinterest.

Ref.: Sandholm, T. 2003. Automated mechanism design: A New Application Area for Search Algorithms. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP). Paper corresponding to an invited talk. (The review part is about joint research with Vincent Conitzer.)

But how could we know the results under such mechanism best!? Is it good enough only under some assumptions like selfish?

Today, NTHU Student Info. System put the courses informations on the web. This is happiest time for students. I browsed any transcribe some courses in which I am interested to here.

• NTHU::CS: Theory of Computation
• NTHU::CS: Parallel Algorithm Design
• NTHU::EE: Architectures of Pipelined and Paralleled Computers
• NTHU::EE: Optimization Methods
• NTHU::ECON: Computable General Equilibrium
• NCTU::MATH: Algebraic Combinatorics

However, I know that it is meaningless to list such courses.

A special option is Computable General Equilibrium, it might be impossible to attend this course. Actually it is not the sort of economics which I like. I put it on the list, because I am interested in the field Algorithmic Game Theory, however I am not interested in the game theory, I am interested in the topic ``New Market Models and Algorithms'' from Vijay V. Vazirani's slides about Market Equilibria.

20060606 Update: Bearman told me that NTHU::EE: Optimization Methods is not a good choice, so that I might attend the course NCTU::ICN: Optimization Theory (Mon. 15:40~16:30, Tue. 15:40~17:30) and NCTU::MATH: Algebraic Combinatorics (Tue. 8:00~8:50, Thu. 10:10~12:00)

NTHU::ECON:Microeconomic Analysis (M5M6M7) seems also interesting.