Archive for the ‘Computer Science’ Category

AAIM 2009

Thursday, April 23rd, 2009

sanf

International Conference on Algorithmic Aspects in Information and Management (AAIM) is intended to provide a forum for researchers working in design and analysis of algorithms, game theory, and combinatorial optimization to present their newest results.
In AAIM 2009 conference which is being held in San Francisco, on of my co-authors will be presenting our paper in the game theory session. The title of the paper is “Power indices of spanning connectivity games” and is joint work with O. Lachish, M. Paterson and R. Savani.

In the paper, we study the problem of computing the influence of edges in a network. Game theorists have studied notions of efficiency, fairness and stability extensively. Therefore, it is only natural that when applications in computer science and multiagent systems require fair and stable allocations, social choice theory and cooperative game theory provide appropriate foundations. For example, a network administrator with limited resources to maintain the links in the network may decide to commit resources to links according to their connecting ability. A surveillance network comprises communication channels. In order to intercept messages on the channels, resources may be utilized according to the ability of a channel to connect all groups. In a social network, we may be interested in checking which connections are more important in maintaining connectivity and hence contribute more to social welfare. The paper is in the line of recent work where economic paradigms are used in computer science applications where there are multiple agents with with their own strategic motives.

Turing Award 2008

Friday, April 3rd, 2009

Alan Turing was one of the greatest computer scientists of the twentieth century. He formalized the idea of a universal abstract computer called the Turing Machine. He is also well known for the Turing Test (to check if a computer can fool humans to think they are communicating with a human). The Turing Award is the biggest award in the foundations of computer science: (more…)

Algorithms

Tuesday, March 10th, 2009

The algorithm has been termed the idiom of modern science by famous computer scientist Bernard Chazelle. Chazelle is of the view that algorithmic perspective is essential to cope with complex models and complex problems:

No math formula will ever model whole biological organisms, economies, ecologies, or large, live networks. Will the Algorithm come to the rescue? This is the next great hope. The algorithmic lens on science is full of promise—and pitfalls.

The main concern in algorithms research is how to do something correctly and optimally. An ‘algorithmic mindset’ is not only essential in problem solving but also helpful in daily life in organization, logical thought process and time planning. The importance of algorithms is well understood within computer science and operations research. What is good news is that this is now being noticed in the media. The Guardian features an article on the pervasiveness of algorithms and ‘how mathematical recipes dictate how we lead our lives’:

In fact, large bits of modern lives are secretly underpinned by complex algorithms – the mathematical equivalent of cookery recipes, which take a piece of information and turn it into an action or decision. Algorithms are like computer programs or flowcharts – a sequence of steps that examines what is happening and comes to a conclusion. Take traffic lights: the computer controlling them asks a series of related questions. What time of day is it? When did the lights last go red? Has a pedestrian pushed the button at the crossing? The algorithm guides the computer, step by step, to change the lights.

The article goes on to show how algorithms come into play in air-traffic control, online purchasing, supermarket operations and almost every part of our daily life.You may read the whole article here. Interestingly, the same theme was covered in the Economist.

The Power of Graphs

Friday, February 27th, 2009

Graphs are mathematical structures that model pairwise relations between objects.  They are represented by vertices and edges where the edges may be directed or undirected. Whenever I am working on some research problem using graphs, my friends who are unfamiliar with graph theory question why I am thinking about graphs and not writing programs. Although I try my best to give an easily understandable reason, OxDE has  explained it really well: (more…)

Good Mathematics

Tuesday, February 17th, 2009

Arxiv is where you normally expect preprints of technical papers in mathematics, physics and computer science. However, it was a surprise to run into a general essay on ‘good mathematics’ by Terrance Tao. Tao has considered more that_taon 21 dimensions of what good mathematics can mean. The following is the list from the essay: (more…)