Our colleague, Luca Aceto, has just received this year's Reykjavik University Research Award. It is of course an honor for the center, ICE-TCS, to which we belong. Actually, it is the second such award for members of the center.
The nomination, signed by a large group of researchers in all four schools of the university, cites his significant publications and impact in process algebra and his stature in the research community (incl. serving on the board of EATCS).
Friday, March 23, 2012
Thursday, March 22, 2012
Papers in CISS and Infocom in this week and the next
Our papers are appearing in two conferences this month.
In CISS'12 this week in Princeton, Pradipta will talk of our paper with Eyjo Asgeirsson,
"A Fully Distributed Algorithm for Throughput Performance in Wireless Networks", see http://arxiv.org/abs/1203.3962. It exports some of our technology for analyzing algorithms (TCS-style) in the SINR model to the field of stochastic networks, where packets arrive at links with some distribution and the goal is to ensure that no link queue grows out of bounds. When the disparity in link lengths is a constant, we get a highly efficient and completely distributed algorithm with constant performance (referred to in the stochastic field as "efficiency").
At Infocom'12 next week in Orlando, he will then talk about our paper "Wireless Capacity and Admission Control in Cognitive Radio", see http://arxiv.org/abs/1111.5200. We introduce there the first LP formulation for SINR capacity problems that can yield good performance bounds. This allows for introducing various other constraints into the formulation. We use it in particular to obtain a constant-factor approximation for an admission problem related to 'cognitive radio': Suppose there is a set P of hard links that cannot be interfered with, add as many additional links from a given input set as possible.
In CISS'12 this week in Princeton, Pradipta will talk of our paper with Eyjo Asgeirsson,
"A Fully Distributed Algorithm for Throughput Performance in Wireless Networks", see http://arxiv.org/abs/1203.3962. It exports some of our technology for analyzing algorithms (TCS-style) in the SINR model to the field of stochastic networks, where packets arrive at links with some distribution and the goal is to ensure that no link queue grows out of bounds. When the disparity in link lengths is a constant, we get a highly efficient and completely distributed algorithm with constant performance (referred to in the stochastic field as "efficiency").
At Infocom'12 next week in Orlando, he will then talk about our paper "Wireless Capacity and Admission Control in Cognitive Radio", see http://arxiv.org/abs/1111.5200. We introduce there the first LP formulation for SINR capacity problems that can yield good performance bounds. This allows for introducing various other constraints into the formulation. We use it in particular to obtain a constant-factor approximation for an admission problem related to 'cognitive radio': Suppose there is a set P of hard links that cannot be interfered with, add as many additional links from a given input set as possible.
2011 Report for ICE-TCS
Our center to which we belong, ICE-TCS, has issued its annual report for 2011. The aim of the center is to further computer science research in Iceland with a theoretical bent.
Endre Szemeredi wins the Abel prize
It has recently been announced that Endre Szemeredi received the highest award in mathematics, the Abel prize.
I have good memories from Szemeredi at Rutgers CS. When I got my first result, I was honored when he asked for a presentation and he kindly complimented me. The stories of his other-wordliness were also legendary... One of the better ones is from my good collaborator, Jaikumar Radhakrishnan, who was his student at the time. When he felt desperate about lack of progress one day, he asked Szemeredi if he thought he could ever complete a Ph.D., Szemeredi answered: "Oh, don't worry, none of my students have ever failed to graduate".
It wasn't until several years later, during a post-doc in Hungary, when Jaikumar asked Szemeredi's wife about his previous students. "No, you were his first student!" was the reply.
I have good memories from Szemeredi at Rutgers CS. When I got my first result, I was honored when he asked for a presentation and he kindly complimented me. The stories of his other-wordliness were also legendary... One of the better ones is from my good collaborator, Jaikumar Radhakrishnan, who was his student at the time. When he felt desperate about lack of progress one day, he asked Szemeredi if he thought he could ever complete a Ph.D., Szemeredi answered: "Oh, don't worry, none of my students have ever failed to graduate".
It wasn't until several years later, during a post-doc in Hungary, when Jaikumar asked Szemeredi's wife about his previous students. "No, you were his first student!" was the reply.
Wednesday, March 14, 2012
New version on arXiv of an older paper: Algorithms for Wireless Capacity
We have recently posted the following paper on arXiv:
This is a full and improved version of results that were given in two papers in 2009, in Infocom and then in ICALP.
The main result is the first constant-factor approximation algorithm for the capacity problem with uniform power, as we call it; also known as maximum independent set of links and max single-shot link scheduling. This introduced a simple (but not trivial) greedy strategy that has been adapted to give effective algorithms for various variations and extensions (e.g. other power assignments in general metrics (SODA'11); power control (Kesselheim SODA'11)). It also shows that the model is robust to minor changes in the parameters.
The Infocom paper currently has 79 citations on Google Scholar and the ICALP paper 45.
- Olga Goussevskaia, Magnus M. Halldorsson and Roger Wattenhofer: Algorithms for Wireless Capacity. http://arxiv.org/abs/1203.0536
This is a full and improved version of results that were given in two papers in 2009, in Infocom and then in ICALP.
The main result is the first constant-factor approximation algorithm for the capacity problem with uniform power, as we call it; also known as maximum independent set of links and max single-shot link scheduling. This introduced a simple (but not trivial) greedy strategy that has been adapted to give effective algorithms for various variations and extensions (e.g. other power assignments in general metrics (SODA'11); power control (Kesselheim SODA'11)). It also shows that the model is robust to minor changes in the parameters.
The Infocom paper currently has 79 citations on Google Scholar and the ICALP paper 45.
Introduction
This blog is created to discuss algorithmic issues in wireless networks. The focus is on merging rigorous analysis (CS style) with realistic models (EE style).
This is the focus of the 'SINR' research group at Reykjavik University. It is a part of the ICE-TCS center within School of Computer Science.
We recently received a 'grant of excellence' from the Icelandic Research Fund; the only such grant awarded this year. It means that we are expanding, hiring Ph.D. students and post-docs.
The hope with this blog is to open up more discussions on related issues, bringing them out of the pure publication mold, and to introduce these interesting topics to more researchers.
This is the focus of the 'SINR' research group at Reykjavik University. It is a part of the ICE-TCS center within School of Computer Science.
We recently received a 'grant of excellence' from the Icelandic Research Fund; the only such grant awarded this year. It means that we are expanding, hiring Ph.D. students and post-docs.
The hope with this blog is to open up more discussions on related issues, bringing them out of the pure publication mold, and to introduce these interesting topics to more researchers.
Subscribe to:
Posts (Atom)