|
Student Notes - SAC Newsletter |
|
|
|
Vol. III, No. 3 Table of Contents1. Introduction
|
||||||||||||||||||
| Deadlines: | |
| Call for nominations: | May 12, 2005 |
| Complete applications due: | November 30, 2005 |
| Decisions communicated: | January 31, 2006 |
All applications should be submitted in either hardcopy or electronic form (Word or PDF) to the following address:
MITACS Student Awards Program
MITACS Head Office
East Academic Annex, Room 120
Simon Fraser University
8888 University Drive
Burnaby, B.C., Canada
V5A 1S6
E-mail: awards@mitacs.ca
3. MITACS Technology Transfer Student Award Winner: Kayvan Mosharaf (Top)
Kayvan Mosharaf was born in Isfahan, Iran, in 1971. He received the B.Sc. degree in 1994 from Isfahan University of Technology, and the M.Sc. degree in 1997 from University of Tehran, both in electrical engineering. He is about to finish his Ph.D. degree in the Department of Systems and Computer Engineering at Carleton University. His research interests include optical WDM networks, wireless cellular networks, mathematical modeling and analysis, simulations and performance evaluation, traffic engineering, and Markov Decision Processes.
 |
SN: Your research involves Wavelength Division Multiplexed (WDM) networks. What do these networks look like? What problems arise when designing these networks? KM: WDM technology is an important area which promises to be the focus of ongoing and future research. It allows simultaneously transmission of multiple wavelengths within a single fiber and presents the highest data rate with the lowest bit error rate. A WDM network consists of optical wavelength routing nodes interconnected by point-to-point fiber links in an arbitrary topology. Although each wavelength can have a transmission capacity up to ten gigabit per second, some traffic streams may require lower bandwidth. To utilize the wavelengths more efficiently, traffic grooming is deployed to share the capacity of a wavelength among users with different bandwidth granularities by multiplexing the lower rate traffic onto high capacity wavelengths. Traffic Engineering and Service Differentiation are still open problems in today's applications with highly-dynamic stochastic traffic. This motivated me to focus on these issues in WDM networks. |
SN: What exactly does Service Differentiation refer to? You mention that it is still an open question: what are some common approaches, and what problems arise with these approaches?
KM: The new generation of computer and communication networks supports different types of applications and services to the users. Service differentiation algorithms are used to ensure that all users get the service they require. To do so, the service differentiation system decides to give preferential service to users with higher priorities. Most of the service differentiation schemes are based on the static information about the system. The advantage of the static approaches is that they are simple, but in most cases they are not efficient in terms of performance. In my research work, I have considered the stochastic nature of the communication systems and proposed new service differentiation schemes which take into account the dynamic behavior of the system. The performance of these dynamic approaches is more efficient than the static ones.
SN: You differentiate between static and dynamic methods of service differentiation. What do some common static methods look like? And how do dynamic methods differ?
KM: Static methods basically partition the resources among the users of different classes according to the parameters of the system. In this case, each class of user can only employ its own partition. The problem here is how to solve the optimal partitioning in a stochastic environment to meet all the service differentiation requirements. When deploying static schemes, in some instances a class of user may employ all of its own assigned resources and require more resources and at this time another class may have some free resources that will not be used in near future. The problem here is that these free resources can not be given to the class which is in need. We can note that in static allocation, although we can differentiate services in the network, the resource utilization is low. In contrast, dynamic methods allocate resources to different classes based on the parameters of the system and also based on the current situation of the system. The advantage of the dynamic methods is that they can provide service differentiation and utilize the resources more efficiently than static methods.
SN: You mentioned Traffic Engineering earlier. How does Traffic Engineering differ from Service Differentiation? What issues have you dealt with in Traffic Engineering in your research?
KM: Traffic Engineering includes traffic measurement and forecasting, capacity planning and network dimensioning, traffic control and provisioning, and performance monitoring. Service differentiation is one of the important parts of Traffic engineering which deals with traffic control and provisioning. In my research, I have studied and investigated service differentiation, capacity planning and network dimensioning in optical WDM networks.
SN: You won the prize for Best Novel Use of Mathematics in Technology Transfer. What sort of interest/feedback have you been receiving based on your work on this topic? Given the obvious commercial potential for research in this area, have you had much contact with industry as a result of your research?
KM: The first important feedback that I have received was from my supervisors, Professor Lambadaris and Professor Talim. The direction and feedback they gave me helped me a lot to find the right track in my research. We have defined the research road map to be very flexible and capable to fit for different problems. As a result, I have received lots of interests from academic community and also from industry. In terms of academic feedback, I have got nine conference papers accepted in prestigious conferences in the area of communications and networking, and also published two journal papers in very high quality journals, all in about two years. And of course this prize from MITACS is another valuable feedback from academia which gave me enough credit to present my work in industry and receive interest even from other areas of telecommunications. Recently, I have an interview with one the well-known companies working in wireless networks. Although this company, Airvana, is mainly designing and implementing the next generation high speed cellular networks, people at Airvana found my research work applicable to this area and as a result, I got an excellent position at this company. As the final word, I would like to thank MITACS for its financial support which I have received through Professor Lambadaris and Carleton University during my Ph.D., and I hope to have more collaborations with MITACS in future.
4. MITACS Student Research Award Winner: Anne Broadbent (Top)
Anne Broadbent is currently researching quantum information processing as part of the Ph.D. programme of the Université de Montréal computer science department. She holds an M.Sc. in computer science from the Université de Montréal as well as a B.Math in combinatorics and optimization (Honours, Co-op) from the University of Waterloo.
 |
SN: Your article discusses the idea of pseudo-telepathy. Can you briefly describe what this concept means? What is the underlying problem in which this concept arises? AB: Consider two participants, Alice and Bob that are physically separated and unable to communicate. The two parties play the following game: a referee challenges them individually with a question, and they must each produce an answer. The referee then examines the answers and, based on the questions that the parties received, he determines whether or not Alice and Bob, as a team, have won the game. We say that the participants have a winning strategy if they are able to always succeed at a given game. In pseudo-telepathy, we consider such games with the following restriction: if the participants share only classical information, then there is no way for them to have a winning strategy. However, if they are allowed to share quantum entanglement---a quantum mechanical resource---then they do have a winning strategy. |
Quantum pseudo-telepathy games can, in theory, be implemented in a laboratory setting. Such experiments have the purpose of demonstrating the nonlocality of the world in which we live.
My work falls in the general area of quantum information processing, which is at the crossroads of mathematics, computer science and physics. The term "pseudo-telepathy" was coined by my supervisor, Alain Tapp, for the following reason: Suppose we introduce a witness to a pseudo-telepathy experiment who only believes in classical physics. Then, seeing that Alice and Bob always succeed at the game, the witness has no other choice than to conclude that Alice and Bob are endowed with a magic way to communicate: telepathy. Yet, we know that there is a perfectly scientific explanation for this amazing power: quantum mechanics!
SN: Regarding the games that these participants would be playing that arise in these problems, can you give us a sense of what one of these games looks like?
| AB: Sure, I'll tell you about one of my favourite pseudo-telepathy games: the magic square game. A magic square is a 3 × 3 matrix whose entries are either 0 or 1, with the property that the sum of each row is even and the sum of each column is odd. Such a square is magic because it cannot exist! Indeed, suppose we calculate the parity of the nine entries. According to the rows, the parity is even, yet according to the columns, the parity is odd. This is obviously impossible. The magic square pseudo-telepathy game involves two participants. As usual, let's call them Alice and Bob. Each time they play the game, the referee challenges Alice to give the entries of row 1, 2 or 3, and Bob to give the entries of column 1, 2, or 3. The participants win if the parity of the row (Alice's answer) is even, the parity of the column (Bob's answer) is odd and the intersection of the row and the column agree. It's easy to see that if Alice and Bob are restricted to sharing classical information, then they do not have a winning strategy. To see this, note that a (deterministic) winning strategy would have to assign definite binary values to each of the nine entries of a magic square. But this is impossible! We can also show that shared randomness doesn't help, so there cannot be a winning strategy, even probabilistic. But would you believe me if I told you that there is a way for Alice and Bob to always succeed at this game? Well, there is! Thanks to entanglement, Alice and Bob can always succeed! Without going into the details of quantum information, I think that I have been able to convince you of the amazing powers of entanglement! This is one of the very exciting features of pseudo-telepathy. |
A sample run of the magic square pseudo-telepathy game. Here, the referee has asked Alice to supply row 1 and Bob to supply column 2 of a magic square. The quantum players have a winning strategy (the intersection of their answers always agrees), yet it is easy to see that there is no winning strategy for classical players. |
SN: You mentioned that strategies are available for the magic square game using quantum entanglement that are not available using classical methods. Can you describe what these strategies look like? What properties of them make them work where classical strategies do not work?
AB: A generic quantum strategy to win a pseudo-telepathy game looks like the following: before the game starts, Alice and Bob arrange to share a resource called quantum entanglement (they can do this by getting together or by relying on a third party to send them each part of the resource). Then, depending on the challenge that they receive from the referee, they each perform some measurement on their part of the entanglement. The result of the measurement is used by each participant to determine what answer he or she will send back to the referee. The quantum entanglement actually permits the participants to produce joint correlations that are impossible to achieve if they use only a classical strategy (it does not, however, allow the participants to communicate instantly!). This is what Einstein referred to as spukhafte Fernwirkung, or spooky action at a distance.
SN: This work appeared in a paper called 'Quantum-Pseudo Telepathy'. What feedback have you received from your research community on this paper since its publication?"
AB: The paper is to appear in this November's issue of Foundations of Physics (but it has been available online for over a year). I would say that the paper was very well received by the research community. It has stimulated interest in this particular research area, as can be noted by the recent increase of publications that mention pseudo-telepathy (the use of the term "pseudo-telepathy" used to be restricted to a small group of people, mostly having some link to Université de Montréal, now it is widespread within the community).
Also, our work was featured on the front page of a December 2004 issue of the New Scientist. This makes me think that our work made a lasting impression on a wide range of people.
The contents of the paper is based on the work that I did for my Master's thesis. The MITACS prize is not the only award that I received for this work: I was awarded a prize for an talk that I gave on quantum pseudo-telepathy at the First Canadian Students Quantum Information Conference in Montréal (July 2004). I was also awarded the Governor General's Academic Gold Medal in May 2005. This distinction placed me at the top of all 2005 Master's and Ph.D. graduates at the Université de Montréal!
SN: You mentioned that the contents of the paper is for work from your Master's thesis. What directions have you been taking your research since then? Are there open problems that you have encountered in your work that you would like to solve?
AB: I have been exploring connections between pseudo-telepathy and other areas of quantum information science. So far, this has lead to new results related to non-local boxes and entanglement simulation. These results are described in a paper that I co-authored with André Méthot. As for open questions, among many things, I think that it would nice to work towards to goal of answering the following: given a fixed parameter (size of input set, of output set or of the shared entanglement), what is the best possible pseudo-telepathy game?
5. MITACS Student Research Award Winner: Maziar Salahi (Top)
Maziar Salahi was born in 1976 in a small city in the north of Iran. He did his undergraduate degree in applied math (with honors) at Gilan University, Iran from 1994 to 1998. He started his master's degree in applied math at Sharif University of Technology, Tehran, Iran in 1998, finishing in 2000. He started his Ph.D. in applied math at Sharif, but in 2002 decided to come to McMaster where he started working with Dr. Tamas Terlaky. He plans to defend his Ph.D. Thesis at the beginning of 2006.
| SN: Your work focuses on Interior-Point Methods (IPMs) in Linear Optimization. What do these methods involve? What are the benefits of IPMs versus other methods?
MS: In order to avoid the exponentiality of the number of iterations of the famous simplex method (shown by the famous Klee-Minty counter example), a new research area arose, which was later called Interior-Point Methods. The first such polynomial algorithm was developed by Kachian 1979, but it was not efficient in practice. In 1984 a new algorithm, which was a breakthrough in the field of optimization, was proposed by Karmarkar. Karmarkar's algorithm performed efficiently in practice compared to the simplex method for large scale problems, and therefore grabbed the attention of many researchers. Since then thousands of articles have been published with various applications in real world problems using IPMs. Computational experience shows how efficient IPMs dominated simplex type methods, especially for large scale optimization. |
 |
It is still an open question how one can reduce the discrepancy between theory and practice. There are algorithms that enjoy better iteration complexity while performing very poorly in practice, and some that are efficient while having higher iteration complexity. This question has been studied by Dr. Jiming Peng in his Ph.D. thesis. By introducing the notion of Self-regular functions, they were able to narrow this discrepancy significantly, while preserving the the same efficiency.
The algorithms they studied are assumed to have a feasible starting point, while this is not the case in many problems arising from various real world applications. Therefore, it is interesting to analyze an infeasible variant of their algorithm. It is worth mentioning that many high performance software packages are using infeasible algorithms. At first glance it might look like a simple extension, but if one goes forward, they will observe that it seems to be impossible to analyze an infeasible variant of their algorithm without the adaptive technique that we employed in our algorithmic scheme. Therefore, the adaptive technique that we used was an exceptional tool that helps in this situation.
Our computational experiments shows that our new algorithm is competitive with some of the state-of-the-art software packages. Unfortunately, at that point we were not able to reduce the iteration complexity compared to the classical algorithms. Recently, by analyzing this algorithm more carefully and using a specific self-regular function, we were able to reduce the iteration complexity that gives the best (so far) complexity for infeasible IPMs.
SN: You mention the discrepancy between theory and practice relating to Interior-Point Methods. Can you elaborate on this? How does this discrepancy show up in practice?
MS: In practice, algorithms stop after around 50 iterations which is almost order of O(log n) or O(n^(1/4)), where n is the dimension of the problem; in theory, the algorithms that perform efficiently in practice have an O(nlog(n/epsilon)) iteration complexity. There are also algorithms that have lower iteration complexity (namely O(n^(1/2)log(n/epsilon))) which is very close to practical complexity, but they are very inefficient in practice.
SN: Having discussed the problems that arise with Interior-Point Methods, what progress have you made with your work with Self-Regular IPMs? What properties of your methods give this progress?
MS: Let me first describe the self-regular IPMs. As I already mentioned, there is a discrepancy between algorithms that are efficient in practice and enjoy O(nlog(n/epsilon)) iteration complexity, and the those that have O(n^(1/2)log(n/epsilon)) iteration complexity while not being efficient in practice. By using the self-regular functions that were introduced in Dr. Jiming Peng's Ph.D. thesis, one can reduce the discrepancy significantly. Using these functions that have many interesting properties, one can modify the Newton system that IPMs have to solve at each iteration. This itself implies that if the algorithm is not able to make a good step using the self-regular functions, one can bring it closer to the central path, and thus get a better step in the next iteration.
SN: You won the award for Best Student Paper for MITACS Related Research, based on a paper entitled "The Complexity of Self-Regular Proximity Based Infeasible IPMs". Where did this work fit in relationship to your graduate work? Have you tried other directions since it was finished?
MS: We extended the result I mentioned earlier by using another specific self-regular function that enabled us to reduce the iteration complexity for the infeasible IPMs. This work will be a chapter of my Ph.D. thesis. The adaptive technique that we used in the paper that won the prize is also used to develop a new variant of predictor-corrector algorithms that enjoy better iteration complexity compared to the existing algorithms while preserving the same efficiency. This development will also be a chapter of my thesis.
SN: Have you received other feedback from your research community as a result of this paper? How did the MITACS award help you in your career?
MS: At the first step, we had both positive and negative reactions, with the negative reactions due to not improving the iteration complexity compared to the existing algorithms. However, the elegant analysis and encouraging computational results were viewed very positively, and that enabled the paper to be accepted in a high level journal, Computational Optimization and Applications.
The MITACS award encouraged me to work harder and get new results, which actually I did since then. It is also a very positive point for my future career, which is going to be a job in academics. Finally, I have to mention that I have been applauded by many of my colleagues for such nice work.
6. MITACS Student Network Award Winner: Lindsay Anderson (Top)
Lindsay Anderson was a member of the MITACS SAC in 2002/03, and Chair of the SAC in 2003/04. She earned B.Sc.(Eng) (1994) and M.Sc. (1998) degrees in Environmental Engineering from the University of Guelph, and a Ph.D (2004) in Applied Mathematics from University of Western Ontario. Her doctoral research, entitled "A Hybrid Model for Electricity Spot Prices", was part of the MITACS Modelling, Trading and Risk in the Market project.
Lindsay is now an Assistant Professor in the Civil and Environmental Engineering at University of Western Ontario.
 |
SN: You were a founding member of the MITACS Student Advisory Committee (SAC). How did you first get involved? What did the SAC look like in its early days?
LA: I joined the SAC when it was just being formed, in late 2002 or early 2003, I think. At that time, Clive Glover (from UBC) was the chair - he was a great leader! We all loved working with Clive. There was also Jarett Hailes from U of A, who was very enthusiastic. There were two people from Ottawa for a short time, but both of them went elsewhere before we got to know them really well. Then we added Irina [Hole] from Dalhousie and JP [Côté] from U of Montreal. |
The great thing was that we were from different regions, different academic backgrounds/research areas, and were all different personalities, so we had some lively discussions. It was a fun time with the SAC because everything was new and even MITACS was unsure what they wanted us to do. We had a lot of free reign to generate ideas and implement programs, and MITACS had the resources to back it up. Also, Jo-Anne Rockwood worked with us on most things -- she always joked that she was the SAC "den mother".
SN: You started as a SAC member, and eventually became the SAC Chair. How did the two positions differ for you?
LA: Being a member was easier, because Clive was so organized, and he kept track of everything. Once I was Chair, the sense of responsibility was more significant. Then it was not just doing my tasks, but making sure everything was getting done. However, the committee members were so dedicated that it was pretty easy to get things done. Jarett Hailes was the Chair after me, and he had also been on the committee since before I joined. He was a HUGE help to me when I was swamped with finishing up my dissertation and interviewing for jobs.
SN: You were present during the NCE site visit at Simon Fraser University. What was that like?
LA: The NCE site visit was quite an experience! I really was honoured to be invited to take part. It was a really good experience for me. I met a lot of people who I would not have met otherwise. It was interesting to see the many facets of MITACS, and the NCE people who were evaluating the proposal.
SN: You have now completed your Ph.D., and are a faculty member at the University of Western Ontario. Looking back on your involvement in MITACS as a student, what sticks out in your memories?"
LA: I think being involved with MITACS opened up a lot of opportunities for me. It brought me into contact with a larger scope of research and people. It was good experience, lots of fun, and something different from the research that can be so overwhelming during your Ph.D. There are lots of fun people doing lots of cool research in MITACS projects. It's hard to say what sticks out the most though -- MITACS is just so student oriented, it is a real resource that should not be overlooked.
7. MITACS SAC Seminar Series and Sponsorship Initiative (Top)
- Would you like the SAC to help you organize a seminar at your university?
- Would you like the SAC to help sponsor an existing event at your university?
The Student Advisory Committee created the Seminar Series and Sponsorship initiative to help promote mathematical sciences at the undergraduate and graduate levels and to provide a learning opportunity for all students. We want to help you organize talks at your university for students in fields related to mathematics or computer sciences.
Up to $400 in sponsorship funds are available for each project. To submit seminar or sponsorship proposals or to obtain more details about this SAC initiative do not hesitate to contact sac_chair@mitacs.ca.
8. MITACS Student Council (Top)
Once again it is the MITACS Annual Conference, and once again MITACS is looking for representatives from each University across Canada to make up the MITACS Student Council. The purpose of the Student Council is to promote communication of MITACS events and information to students in the mathematical sciences. The following is a list of the responsibilities and benefits of taking part.
Student Council Responsibilities:
- Act as a contact and information source about MITACS events and programs to other students at your University
- Organize a MITACS information session for students at your University; (MITACS will cover expenses and provide the slides and presentation notes)
- Provide input and suggestions for student sessions at MITACS conferences and Interchanges. For example, suggestions for speakers or topics that students would like to see
- Act as a liaison to the Student Advisory Committee (SAC)
- Participate in Student Council email list
- Attend a Student Council meeting to be held annually at the Annual Conference – (MITACS will assist with travel and accommodation expenses)
Benefits to Student Council Members:
- Waive registration fees for MITACS conferences
- Guaranteed travel subsidies to attend conferences; no need to worry
about cut-off dates - Make valuable contacts with other students and faculty across the country and in different fields.
- Learn about MITACS events and news firsthand.
- Have input and contribute to the MITACS events in your region
If you think you might be interested in acting as a representative of your University, please email SAC_Chair@mitacs.ca.
9. Call for Submissions (Top)
The MITACS Student Newsletter is prepared by the Student Advisory Committee to announce upcoming events, report on past events and on MITACS research, to acknowledge student achievement, and to advertise resources for students. The newsletter is distributed quarterly, and the SAC is thrilled to receive student submissions. To submit comments, suggestions or materials to the newsletter, contact Michel Couillard through the feedback form.