I should have written this post a long time ago but for some reason I was hoping the decision would change.
I did my undergrad and PhD at the computer science department at Lund University in Sweden. Sadly it seems as the department will be closed down. The decision (Swedish) was taken by the faculty board in November 2007. As far as I can tell the decision was taken purely on a financial basis (even though the department is tiny compared the departments of biology, chemistry and physics).
The research at the department focused on algorithmics and AI and the small algorithms group was headed by Andrzej Lingas. The group, that among others also includes Thore Husfeldt and my former supervisor Christos Levcopoulos, has always been very active and produced high quality research and PhDs. When I was a PhD student there was a rather big group of successful students, for example, Andreas Björklund, Anna Pagh, Jesper Jansson, Mikael Hammar and Jesper Larsson.
From next year there will be no Computer Science education in Lund (however, there will still be a computer engineering program at the faculty of engineering). As far as I know it is unique for a large university. It will be very sad not to be able to visit my old department when I go back to Sweden.
Tuesday, November 25, 2008
Tuesday, November 11, 2008
CATS 2009 accepted papers
CATS 2009 list of accepted papers is out.
I heard rumours (Prabhu and Tasos) that CATS got roughly 50 submissions this year. This is a huge increase from recent years when we've had approximately 30 papers per year.
The conference will take place in Wellington the 20-23 of January.
I heard rumours (Prabhu and Tasos) that CATS got roughly 50 submissions this year. This is a huge increase from recent years when we've had approximately 30 papers per year.
The conference will take place in Wellington the 20-23 of January.
Sunday, November 9, 2008
Attending ACM GIS 2008
The last stop on my around the world trip is Los Angeles and ACM GIS. The conference venue is in a big hotel complex in Irvine somewhere. If I look out the window of my room I see a lot of big buildings but not a single person...scary. I arrived on Thursday afternoon but I was so jet lagged that I fell asleep and missed the last session and the banquet. I woke up at 2:30am on Friday morning and could finish my slides well before my presentation at 9am.
I attended all the talks on Friday. Not much to report, some interesting talks but nothing that stood out. Should try to remember to write a post discussing conference venues, i.e., (remote) hotels vs. universities. Looking forward to get back to Sydney after all the travelling.
I attended all the talks on Friday. Not much to report, some interesting talks but nothing that stood out. Should try to remember to write a post discussing conference venues, i.e., (remote) hotels vs. universities. Looking forward to get back to Sydney after all the travelling.
Saturday, November 8, 2008
Dagstuhl - moving objects
In Dagstuhl for a workshop on moving objects. As usual I'm enjoying myself. It's something special about spending one week (unfortunately only three days in this case since I have to fly to ACM GIS) on a remote castle with lots of smart people and working on new and interesting problems.
This workshop is very diverse with people from computational geometry, data bases, GIScience, geography, visualisation... Which is good in the sense that I learn something new from every presentation. The drawback is, of course, that it's sometimes hard to communicate across areas, but it's getting better and better.
On Wednesday we did the "compulsory" hike and as usual (except when hiking with Helmut Alt) we got lost (I'm not blaming anyone).
This workshop is very diverse with people from computational geometry, data bases, GIScience, geography, visualisation... Which is good in the sense that I learn something new from every presentation. The drawback is, of course, that it's sometimes hard to communicate across areas, but it's getting better and better.
On Wednesday we did the "compulsory" hike and as usual (except when hiking with Helmut Alt) we got lost (I'm not blaming anyone).
Tuesday, November 4, 2008
Project performance
NICTA has come up with a new great project performance indicator...the number of visitors to its project webpage. Needless to say that our project is not among the top performers. So if you want to support the algorithms people at NICTA please visit our webpage!
Friday, October 3, 2008
ARC future fellowships
The Australian Research Council has announced the ARC Future Fellowships. This is a new scheme of research funding for mid-career researchers.
the interesting bits in the announcement:
- applicant must be 5 to 15 years from PhD
- up to 140,000AUD salary
- 4 years
- 1000 fellowships available over 5 years (across all research fields)
- deadline november 26
according to the announcement one of the aims of this scheme is "to attract australian researchers currently based overseas to return to australia".
It will be interesting to see how many of these fellowships will go to computer science (and if any will go to theoretical computer science).
the assessment criteria are as follows:
- applicant 50% (that's the applicant's CV)
- strategic alignment 15% (alignment with host institution's research strengths)
- collaboration 15%
- national priorities 10%
- ... and the least significant, least important aspect: the proposed research for which you will be funded for four years, 10%
so, 90% of the weight of the assessment criteria is not related to the proposed research.
The ARC will look at the technical part of the research proposal last, if at all.
Monday, September 29, 2008
SoCG call-for-papers
SoCG 2009 will take place on the 8-10 of June in Aarhus, Denmark. I'm sure it will be a lot of fun to visit Aarhus and Lars, especially since Sweden is playing against Denmark in the football world cup qualification on the 6th of June!
Here's the CFP.
Btw, why is Århus the city spelt with an `Å' while Aarhus University is spelt with `Aa’?
Here's the CFP.
Btw, why is Århus the city spelt with an `Å' while Aarhus University is spelt with `Aa’?
Wednesday, September 10, 2008
Algoritmics in NZ
The algorithmic activities in New Zealand continues. At the 7th Australia – New Zealand Mathematics Convention in Christchurch there will be a special algoritmics session. This special session is part of the thematic programme on Algorithmics funded by the New Zealand Institute for Mathematics and its Applications (NZIMA).
Also, Bernard Chazelle will give a series of public lectures in the period 13-22 March 2009.
Also, Bernard Chazelle will give a series of public lectures in the period 13-22 March 2009.
Sunday, September 7, 2008
Clustering trajectories
Late last year I attended a (great) workshop in the Netherlands organised by Marc van Kreveld. From that workshop a few (!) papers came out. One of them was just accepted to ISAAC - "Detecting Commuting Patterns by Clustering Subtrajectories" by Kevin Buchin, Maike Buchin, Jun Luo, Maarten Löffler and me.
The problem of clustering trajectories is surprisingly hard. In the data mining/database community there are several papers on this problem that are fairly fast but not very accurate (useful?).
In the paper we focus on finding subtrajectories of a single trajectory that forms a cluster (can easily be extended to the general clustering problem). This is useful for detecting, e.g., commuting patterns or seasonal migration behaviour. Our approach builds on the Frechet distance and heavily makes use of the freespace diagram. This gives an accurate definition of a trajectory cluster (imho) but it is very costly to compute (both in time and space). The running time is roughly quadratic (for most settings) and a (non-optimised) implementation can handle 10K points in roughly 20 minutes.
The obvious open problem is: Is there an accurate definition of a trajectory cluster that would allow for a more efficient implementation?
The problem of clustering trajectories is surprisingly hard. In the data mining/database community there are several papers on this problem that are fairly fast but not very accurate (useful?).
In the paper we focus on finding subtrajectories of a single trajectory that forms a cluster (can easily be extended to the general clustering problem). This is useful for detecting, e.g., commuting patterns or seasonal migration behaviour. Our approach builds on the Frechet distance and heavily makes use of the freespace diagram. This gives an accurate definition of a trajectory cluster (imho) but it is very costly to compute (both in time and space). The running time is roughly quadratic (for most settings) and a (non-optimised) implementation can handle 10K points in roughly 20 minutes.
The obvious open problem is: Is there an accurate definition of a trajectory cluster that would allow for a more efficient implementation?
Monday, August 25, 2008
Friday, August 1, 2008
Pay to get published?
Recently I was kindly offered to become an editor for a new open access journal called ALGORITHMS published by MDPI. At first sight it looked as a great idea, and the editorial board contains some very impressive researchers. However, when I started to read the instructions for call for papers more closely I realised that the authors of an accepted paper have to pay roughly 1000 CHF (roughly the same in Australian/US dollars).
So instead of letting the readers pay for the journal the authors have to pay for their articles to get published. In the theory community we don't have the tradition of paying for our publications. On one hand this approach is much cheaper for the community but can you guarantee quality in this system? It's not obvious that one system is better than the other but personally I rather pay to read a paper than to publish it. However, I'm very curious to hear what other researchers think about this.
So instead of letting the readers pay for the journal the authors have to pay for their articles to get published. In the theory community we don't have the tradition of paying for our publications. On one hand this approach is much cheaper for the community but can you guarantee quality in this system? It's not obvious that one system is better than the other but personally I rather pay to read a paper than to publish it. However, I'm very curious to hear what other researchers think about this.
Thursday, July 24, 2008
SWAT - Day 2
I wrote this entry about two weeks ago but haven't had a chance to post it. Better late than never...
Today's highlight was definitely the invited talk by Michael Mitzenmacher on deletion channels (his talk, and a survey, is available). Again a topic that I didn't know much about, but Michael's presentation gave me a good understanding of the basic problem and the questions that are important in this area. A deletion channel is a channel where n bits are sent, but each bit is independently deleted with fixed probability p. (Different from the erasure channel where each bit can be replaced by a `?', or the symmetric channel where each bit can be flipped). The main question is to decide the capacity of the channel. Michael showed that the lower bound (which is really an upper bound) is at least (1-p)/9. However, he also stated several interesting fundamental problems during his talk. For example, how do random subsequences of random sequences behave?
The conference dinner (I, & II) was held in a beautiful location just to the south of Gothenburg looking out on the archipelago. While the sun was setting we had good food and tried to come up with a new name for SWAT (I, II & III). The local organisers did a great job finding the place and arranging a historic tram trip to the venue.
Today's highlight was definitely the invited talk by Michael Mitzenmacher on deletion channels (his talk, and a survey, is available). Again a topic that I didn't know much about, but Michael's presentation gave me a good understanding of the basic problem and the questions that are important in this area. A deletion channel is a channel where n bits are sent, but each bit is independently deleted with fixed probability p. (Different from the erasure channel where each bit can be replaced by a `?', or the symmetric channel where each bit can be flipped). The main question is to decide the capacity of the channel. Michael showed that the lower bound (which is really an upper bound) is at least (1-p)/9. However, he also stated several interesting fundamental problems during his talk. For example, how do random subsequences of random sequences behave?
The conference dinner (I, & II) was held in a beautiful location just to the south of Gothenburg looking out on the archipelago. While the sun was setting we had good food and tried to come up with a new name for SWAT (I, II & III). The local organisers did a great job finding the place and arranging a historic tram trip to the venue.
Sunday, July 13, 2008
SWAT - Day 1
A bit late but here's a short summary of SWAT day 1:
I'm in Gothenburg attending SWAT 2008. I haven't been in Gothenburg since I was a kid but it's a beautiful city this time of the year. Due to the long and warm summer evening there are heaps of people everywhere. Apart from SWAT there's also the worlds largest youth handball tournament going on with 900 teams from all around the world.
The local organisers of SWAT seem to have everything under control. I don't have to worry about anything (except a nasty cold). The first day included some very nice talks. John Hershberger gave the first talk of the conference, "Simplified planar coresets for data streams" which gives a simple way of producing coresets for computing the extent of a point set in the plane. He (and Subhash Suri) combined several known techniques with a few nice ideas to obtain an optimal size coreset.
Another talk I enjoyed was on placing wireless devices in an internet cafe such that customers inside the cafe can be distinguished from people outside the cafe. The talk was given by Tobias Christ and they show that for a simple polygon with n vertices 3n/5 devices is sometimes necessary and that 4n/5 is always sufficient.
Vijay Vazirani gave a great invited talk on the relation between Nash bargaining and flexible markets. I don't know the area very well but Vijay gave a very good survey focussing on the fact that some of these problems can be stated as a convex program which can be shown to have a rational optimal solution which can be solved in polynomial time by using primal-dual techniques.
After the technical program there was a business meeting where various issues were discussed (more on that in an upcoming post), followed by a reception at the city hall (provided by the city of Gothenburg) and the PC dinner (for details of what was discussed see Michael's post).
I'm in Gothenburg attending SWAT 2008. I haven't been in Gothenburg since I was a kid but it's a beautiful city this time of the year. Due to the long and warm summer evening there are heaps of people everywhere. Apart from SWAT there's also the worlds largest youth handball tournament going on with 900 teams from all around the world.
The local organisers of SWAT seem to have everything under control. I don't have to worry about anything (except a nasty cold). The first day included some very nice talks. John Hershberger gave the first talk of the conference, "Simplified planar coresets for data streams" which gives a simple way of producing coresets for computing the extent of a point set in the plane. He (and Subhash Suri) combined several known techniques with a few nice ideas to obtain an optimal size coreset.
Another talk I enjoyed was on placing wireless devices in an internet cafe such that customers inside the cafe can be distinguished from people outside the cafe. The talk was given by Tobias Christ and they show that for a simple polygon with n vertices 3n/5 devices is sometimes necessary and that 4n/5 is always sufficient.
Vijay Vazirani gave a great invited talk on the relation between Nash bargaining and flexible markets. I don't know the area very well but Vijay gave a very good survey focussing on the fact that some of these problems can be stated as a convex program which can be shown to have a rational optimal solution which can be solved in polynomial time by using primal-dual techniques.
After the technical program there was a business meeting where various issues were discussed (more on that in an upcoming post), followed by a reception at the city hall (provided by the city of Gothenburg) and the PC dinner (for details of what was discussed see Michael's post).
Friday, July 11, 2008
postdoc positions in USyd
University of Sydney is inviting applications for postdoc fellowships in any department/research area. The closing date for applications is september 12. if i'm reading the information on the web correctly, these postdoc fellowships provide a salary of about 70K, 25K research funding, some relocation expenses and have a max duration of 3 years.
Wednesday, June 11, 2008
The prisoners dilemma
A few weeks ago Taso (new fancy homepage), Tony and I organised the Sydney Theory Day. Among the invited speakers were Peter Bro Miltersen who gave a talk on "Names in boxes". The abstract of the talk can be found here. The short version is:
"The names of one hundred prisoners are placed in one hundred wooden boxes, one name to each box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; they may look into up to fifty of the boxes to try to find their own name but must leave the room exactly as it was. They are permitted no further communication after leaving the room. The prisoners have a chance to plot a strategy in advance and they are going to need it, because unless they all find their own names they will all be executed. There is a strategy that has a probability of success exceeding thirty percent - find it"
If each prisoner examines a random set of 50 boxes, their probability of survival is close to zero. It turns out that there is a very simple schedule that gives the prisoners a 30% chance of surviving. It sounds almost impossible but there's a simple proof that anyone can understand in "7 Puzzles You Think You Must Not Have Heard Correctly" by Peter Winkler.
This semester I've been teaching computational geometry at USyd and I find it hard to get them to properly understand the beauty of expected running times. However, this year I started the lecture by discussing the "Prisoners dilemma" for 20 minutes before I talked about the expected running time of low dimensional LP. And I really believe it had a positive effect. The students seemed to appreciate the simplicity of the arguments a bit more than usual.
Now the challenge is to find a puzzle like this for each lecture. Any tips?
"The names of one hundred prisoners are placed in one hundred wooden boxes, one name to each box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; they may look into up to fifty of the boxes to try to find their own name but must leave the room exactly as it was. They are permitted no further communication after leaving the room. The prisoners have a chance to plot a strategy in advance and they are going to need it, because unless they all find their own names they will all be executed. There is a strategy that has a probability of success exceeding thirty percent - find it"
If each prisoner examines a random set of 50 boxes, their probability of survival is close to zero. It turns out that there is a very simple schedule that gives the prisoners a 30% chance of surviving. It sounds almost impossible but there's a simple proof that anyone can understand in "7 Puzzles You Think You Must Not Have Heard Correctly" by Peter Winkler.
This semester I've been teaching computational geometry at USyd and I find it hard to get them to properly understand the beauty of expected running times. However, this year I started the lecture by discussing the "Prisoners dilemma" for 20 minutes before I talked about the expected running time of low dimensional LP. And I really believe it had a positive effect. The students seemed to appreciate the simplicity of the arguments a bit more than usual.
Now the challenge is to find a puzzle like this for each lecture. Any tips?
ESA accepted papers
I'm about two weeks late, but better late than never.
The list of accepted papers at ESA is out. I was in the PC for the applied track where we got 53 submissions out of which 16 were accepted. As a whole the papers were of high quality and even though I was pretty tired of reviewing papers I enjoyed reading many of them (well at least a few).
In the theory track there were a some papers that look interesting, for example: "Fitting a step function to a point set" by Fournier and Vigneron, "An optimal dynamic spanner for doubling metric spaces" by Gottlieb and Roditty (finally an optimal algorithm!) and "Deterministic Sampling Algorithms" by van Zuylen.
Our group also got a paper accepted, "Detecting Regular Visit Patterns" by Bojan Djordjevic, Anh Pham, Thomas Wolle and me. I quite like this paper. As the title suggests the original motivation comes from detecting regular visit patterns. However, the problem boils down to a nice little problem on bitstrings.
Given a bitstring S and a constant 0 < c < 1 find the longest substring of S containing at least a fraction c of 1's. We give a linear time algorithm and then we apply it to our original problem.
The list of accepted papers at ESA is out. I was in the PC for the applied track where we got 53 submissions out of which 16 were accepted. As a whole the papers were of high quality and even though I was pretty tired of reviewing papers I enjoyed reading many of them (well at least a few).
In the theory track there were a some papers that look interesting, for example: "Fitting a step function to a point set" by Fournier and Vigneron, "An optimal dynamic spanner for doubling metric spaces" by Gottlieb and Roditty (finally an optimal algorithm!) and "Deterministic Sampling Algorithms" by van Zuylen.
Our group also got a paper accepted, "Detecting Regular Visit Patterns" by Bojan Djordjevic, Anh Pham, Thomas Wolle and me. I quite like this paper. As the title suggests the original motivation comes from detecting regular visit patterns. However, the problem boils down to a nice little problem on bitstrings.
Given a bitstring S and a constant 0 < c < 1 find the longest substring of S containing at least a fraction c of 1's. We give a linear time algorithm and then we apply it to our original problem.
Tuesday, June 10, 2008
ISAAC deadline approaching
Call for Papers
The 19th International Symposium on Algorithms and Computation
(ISAAC 2008) December 15 - 17, 2008, Gold Coast, Australia
http://www-or.amp.i.kyoto-u.ac.jp/isaac08/
The 19th International Symposium on Algorithms and Computation (ISAAC 2008) will be held in Gold Coast, Australia, December 15-17, 2008. The symposium is intended to provide a forum for researchers working in algorithms and theory of computation. Papers presenting original research in the areas of algorithms and theory of computation are sought. Papers in relevant applied areas are also welcome.
Topics
The topics include, but are not limited to:
- Algorithms and data structures
- Approximation algorithms
- Combinatorial optimization
- Computational biology
- Computational complexity
- Computational geometry
- Cryptography
- Experimental algorithms
- Graph drawing
- Graph algorithms
- Internet algorithms
- Online algorithms
- Parallel and distributed algorithms
- Quantum computing
- Randomized algorithms
Important Dates
Submission deadline: June 25, 2008 (12pm, US Pacific Time)
Notification of acceptance: August 18, 2008
Camera-ready submission: September 15, 2008
Invited Speakers
Prof. Tetsuo Asano (JAIST, Japan)
Prof. Peter Eades (University of Sydney, Australia)
Prof. Robert Tarjan (Princeton University, HP, USA)
Paper Submission
The submission should contain a scholarly exposition of ideas, techniques, and results, including motivation and a clear comparison with related work. The length of the submission should not exceed twelve pages in LNCS style.
If the authors feel that more details are essential to substantiate the main claim of the paper, they may include a clearly marked appendix that will be read at the discretion of the program committee.
Only electronic submission (pdf) will be allowed.
Submitted papers must describe work not previously published.
They must not be submitted simultaneously to another conference with refereed proceedings or a journal. At least one of the authors of accepted papers is expected to present their work at the conference.
Publication
The symposium proceedings will be published by Springer-Verlag in Lecture Notes in Computer Science (LNCS) series. Selected papers will be invited to special issues of Algorithmica and International Journal on Computational Geometry and Applications.
Awards
The Best Paper and the Best Student Paper will be awarded.
The Best Student Paper Award will be given to the best paper written solely by one or more students. A paper is eligible if all authors are full-time students at the time of submission.
To indicate that a submission is eligible, please add the phrase "Eligible for best student paper" as the last sentence in the "Abstract" field in the web form on the submission server as well as in the paper. The program committee may decline to make the award, or may split it among several papers.
The 19th International Symposium on Algorithms and Computation
(ISAAC 2008) December 15 - 17, 2008, Gold Coast, Australia
http://www-or.amp.i.kyoto-u.ac
The 19th International Symposium on Algorithms and Computation (ISAAC 2008) will be held in Gold Coast, Australia, December 15-17, 2008. The symposium is intended to provide a forum for researchers working in algorithms and theory of computation. Papers presenting original research in the areas of algorithms and theory of computation are sought. Papers in relevant applied areas are also welcome.
Topics
The topics include, but are not limited to:
- Algorithms and data structures
- Approximation algorithms
- Combinatorial optimization
- Computational biology
- Computational complexity
- Computational geometry
- Cryptography
- Experimental algorithms
- Graph drawing
- Graph algorithms
- Internet algorithms
- Online algorithms
- Parallel and distributed algorithms
- Quantum computing
- Randomized algorithms
Important Dates
Submission deadline: June 25, 2008 (12pm, US Pacific Time)
Notification of acceptance: August 18, 2008
Camera-ready submission: September 15, 2008
Invited Speakers
Prof. Tetsuo Asano (JAIST, Japan)
Prof. Peter Eades (University of Sydney, Australia)
Prof. Robert Tarjan (Princeton University, HP, USA)
Paper Submission
The submission should contain a scholarly exposition of ideas, techniques, and results, including motivation and a clear comparison with related work. The length of the submission should not exceed twelve pages in LNCS style.
If the authors feel that more details are essential to substantiate the main claim of the paper, they may include a clearly marked appendix that will be read at the discretion of the program committee.
Only electronic submission (pdf) will be allowed.
Submitted papers must describe work not previously published.
They must not be submitted simultaneously to another conference with refereed proceedings or a journal. At least one of the authors of accepted papers is expected to present their work at the conference.
Publication
The symposium proceedings will be published by Springer-Verlag in Lecture Notes in Computer Science (LNCS) series. Selected papers will be invited to special issues of Algorithmica and International Journal on Computational Geometry and Applications.
Awards
The Best Paper and the Best Student Paper will be awarded.
The Best Student Paper Award will be given to the best paper written solely by one or more students. A paper is eligible if all authors are full-time students at the time of submission.
To indicate that a submission is eligible, please add the phrase "Eligible for best student paper" as the last sentence in the "Abstract" field in the web form on the submission server as well as in the paper. The program committee may decline to make the award, or may split it among several papers.
Friday, June 6, 2008
Sydney weather
Rain, more rain and then some more rain these days in sydney.
Here are some interesting "facts" about sydney weather:
For me the definition of good weather is simple: sun. Temperature is not very important, as long as you have sun. Having lots of sun implies that you cannot have terribly wet weather, you cannot have tropical weather etc.
The definition and most statistics for wets days comes from BBC.co.uk/weather website. For example here are some links, for the averages for sydney and here for toronto. Or you can look up other cities starting here. The source for the number of sunny days in sydney is the Australian Bureau of Meteorology.
The following is a list of cites and their average number of wet days per year:
sunniest US cities (source):
[% sunshine is the percentage of time between sunrise and sunset that sun reaches the earth's surface. Clear days is the number days a year when clouds cover less than one-third of the sky on average.]
Here are some interesting "facts" about sydney weather:
- Sydney has almost the same number of wet days per year as London UK
(152 wet days for sydney, 153 for london. a wet day has 0.25mm rain or more) - Sydney is the "wettest" city i have ever lived in
(i have lived in athens-greece, princeton-NJ, toronto and sydney) - Sydney has only 100 sunny days per year. Las vegas has over 200.
(ok my stats for sydney and las vegas are from different sources using different definitions for sunny-ness: sunny day for sydney has average cloud cover less than 25%, for las vegas it is up to 1/3 cloud cover.) - In april 2008 we had 12 continuous days of rain in sydney. plus some more (non-continuous) days of rain. feb-march were just as bad.
For me the definition of good weather is simple: sun. Temperature is not very important, as long as you have sun. Having lots of sun implies that you cannot have terribly wet weather, you cannot have tropical weather etc.
The definition and most statistics for wets days comes from BBC.co.uk/weather website. For example here are some links, for the averages for sydney and here for toronto. Or you can look up other cities starting here. The source for the number of sunny days in sydney is the Australian Bureau of Meteorology.
The following is a list of cites and their average number of wet days per year:
- phoenix arizona: 39 (source)
- athens greece: 103 (source)
- NYC: 125 (source)
- ottawa: 139 (source)
- toronto: 145 (source)
- sydney: 152 (source)
- london UK: 153 (source)
- stockholm: 164 (source)
sunniest US cities (source):
| City | % Sunshine | Clear Days |
|---|---|---|
| Phoenix, Arizona | 85 | 211 |
| Las Vegas, Nevada | 85 | 210 |
| Tucson, Arizona | 85 | 193 |
| El Paso, Texas | 84 | 193 |
| Fresno, California | 79 | 194 |
| Sacramento, California | 78 | 188 |
| Albuquerque, New Mexico | 76 | 186 |
| Los Angeles, California | 73 | 167 |
| Denver, Colorado | 69 | 115 |
| San Diego, California | 68 | 146 |
| Oklahoma City, Oklahoma | 68 | 139 |
| San Francisco, California | 66 | 160 |
[% sunshine is the percentage of time between sunrise and sunset that sun reaches the earth's surface. Clear days is the number days a year when clouds cover less than one-third of the sky on average.]
Friday, May 23, 2008
Out reviewed
Yes! I just submitted my last review for CCCG. After being in three pc's since March I'm done with all reviews! I reviewed (not counting papers I gave to subrefs) roughly 60 papers for SWAT, ESA and CCCG. Finally I can get back to a normal life, doing research, reviewing journal papers and taking looong coffee breaks!
Wednesday, May 21, 2008
Sydney theory day: the photo
Many thanks to all our speakers and all participants for making the sydney theory day a very enjoyable event.
(The photo above has about half of the workshop's participants)
(The photo above has about half of the workshop's participants)
Thursday, May 8, 2008
Sydney theory day - May 14
The sydney theory day is wednesday next week. Call for participation follows.
Theoretical computer science day in Sydney
Wednesday May 14, 2008
Darlington centre, University of Sydney
FINAL CALL FOR PARTICIPATION
The theoretical computer science day will take place in Sydney on May 14, 2008. The aim of this one-day event is to bring together researchers interested in all aspects of theoretical computer science, and discuss current trends and problems in the field, as well as future directions. The EII Network and the organizing committee would like to invite researchers in theoretical computer science to participate in this event. If you are interested in participating, please register as soon as possible through the registration webpage. Registration is open to everyone and is free.
More information is available on the theory day webpages including information about the
invited presentations, the location and registration.
The program of the theory day is as follows:
9:30-10:00 Morning coffee/tea
10:00-11:00 Sartaj Sahni University of Florida
11:00-11:30 break (refreshments)
11:30-12:30 Pat Morin, Carleton University
12:30-13:30 Lunch break (lunch provided)
13:30-14:30 Peter Bro Miltersen, University of Aarhus
14:30-15:00 break (refreshments)
15:00-15:45 Rob van Glabbeek, NICTA Kensington and UNSW
16:00-16:45 Tony Wirth, University of Melbourne
16:45-17:30 refreshments
The meeting is sponsored by the EII Network, University of Sydney and NICTA.
For any questions please contact the organizers.
ORGANISATION
Joachim Gudmundsson, NICTA, joachim.gudmundsson@nicta.com.au
Taso Viglas, University of Sydney, a.viglas@usyd.edu.au
Tony Wirth, University of Melbourne, awirth@csse.unimelb.edu.au
Theoretical computer science day in Sydney
Wednesday May 14, 2008
Darlington centre, University of Sydney
FINAL CALL FOR PARTICIPATION
The theoretical computer science day will take place in Sydney on May 14, 2008. The aim of this one-day event is to bring together researchers interested in all aspects of theoretical computer science, and discuss current trends and problems in the field, as well as future directions. The EII Network and the organizing committee would like to invite researchers in theoretical computer science to participate in this event. If you are interested in participating, please register as soon as possible through the registration webpage. Registration is open to everyone and is free.
More information is available on the theory day webpages including information about the
invited presentations, the location and registration.
The program of the theory day is as follows:
9:30-10:00 Morning coffee/tea
10:00-11:00 Sartaj Sahni University of Florida
11:00-11:30 break (refreshments)
11:30-12:30 Pat Morin, Carleton University
12:30-13:30 Lunch break (lunch provided)
13:30-14:30 Peter Bro Miltersen, University of Aarhus
14:30-15:00 break (refreshments)
15:00-15:45 Rob van Glabbeek, NICTA Kensington and UNSW
16:00-16:45 Tony Wirth, University of Melbourne
16:45-17:30 refreshments
The meeting is sponsored by the EII Network, University of Sydney and NICTA.
For any questions please contact the organizers.
ORGANISATION
Joachim Gudmundsson, NICTA, joachim.gudmundsson@nicta.com
Taso Viglas, University of Sydney, a.viglas@usyd.edu.au
Tony Wirth, University of Melbourne, awirth@csse.unimelb.edu.au
Monday, May 5, 2008
SWAT 2008 - Call for participation
Here's the call for participation for SWAT 2008. Gothenburg is a very exciting place in early July with almost 20 hours of sunlight. More information about Gothenburgh can be found here.
Call for Participation
11th Scandinavian Workshop on Algorithm Theory (SWAT)
July 2-4, 2008
Gothenburg, Sweden
http://www.dmist.net/swat2008
http://www.cse.chalmers.se/swat2008
The registration is open.
Early registartion deadline: May 31, 2008.
SWAT is a biennial international conference intended as a forum for
researchers in the area of design and analysis of algorithms and data
structures including approximation algorithms, computational biology,
computational geometry, distributed algorithms, external-memory algorithms,
graph algorithms, online algorithms, optimization algorithms, parallel
algorithms, randomized algorithms, string algorithms, algorithmic game
theory and more.
CONFERENCE PROGRAMME
http://www.cse.chalmers.se/swat2008/programme.html
INVITED TALKS
Michael Mitzenmacher, Harvard University
Title: A Survey of Results for Deletion Channels and Related
Synchronization Channels
Vijay V. Vazirani, Georgia Institute of Technology
Title: Nash Bargaining via Flexible Budget Markets
Call for Participation
11th Scandinavian Workshop on Algorithm Theory (SWAT)
July 2-4, 2008
Gothenburg, Sweden
http://www.dmist.net/swat2008
http://www.cse.chalmers.se/swat2008
The registration is open.
Early registartion deadline: May 31, 2008.
SWAT is a biennial international conference intended as a forum for
researchers in the area of design and analysis of algorithms and data
structures including approximation algorithms, computational biology,
computational geometry, distributed algorithms, external-memory algorithms,
graph algorithms, online algorithms, optimization algorithms, parallel
algorithms, randomized algorithms, string algorithms, algorithmic game
theory and more.
CONFERENCE PROGRAMME
http://www.cse.chalmers.se/swat2008/programme.html
INVITED TALKS
Michael Mitzenmacher, Harvard University
Title: A Survey of Results for Deletion Channels and Related
Synchronization Channels
Vijay V. Vazirani, Georgia Institute of Technology
Title: Nash Bargaining via Flexible Budget Markets
Friday, April 11, 2008
Congratulations Mohammad!
This week I'm in Eindhoven since my PhD student Mohammad Farshi defended his thesis on Tuesday. I've been working closely with Mohammad for the last four years and it's been a real pleasure. We had some very nice papers, among them a SoCG paper in 2005, an ESA paper in 2006 and then a SODA paper in 2007, all of them on interesting spanner problems.
In October, before he submitted his thesis, he started as a postdoc at Carleton University with Michiel Smid. I'm sure he'll be very successful.
Congratulations Mohammad!
In October, before he submitted his thesis, he started as a postdoc at Carleton University with Michiel Smid. I'm sure he'll be very successful.
Congratulations Mohammad!
Wednesday, April 9, 2008
ICALP 2008 accepted papers
The list of accepted papers for ICALP 2008 is out (track A: algorithms, automata, complexity and games).
The 10 titles that i liked the most (from my first look through the list of accepted papers):
The 10 titles that i liked the most (from my first look through the list of accepted papers):
- Andrei Bulatov. The Complexity of the Counting Constraint Satisfaction Problem
- Guy Blelloch, Virginia Vassilevska and Ryan Williams. A New Combinatorial Approach For Sparse Graph Problems
- Patrick Briest. Uniform Budgets and the Envy-Free Pricing Problem
- David Buchfuhrer and Christopher Umans. The complexity of Boolean formula minimization
- Alexandr Andoni and Robi Krauthgamer. The Smoothed Complexity of Edit Distance
- Kousha Etessami, Dominik Wojtczak and Mihalis Yannakakis. Recursive Stochastic Games with Positive Rewards
- Mehdi Mhalla and Simon Perdrix. Finding Optimal Flows Efficiently
- Yijia Chen, Marc Thurley and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms
- Angelo Fanelli, Michele Flammini and Luca Moscardelli. The Speed of Convergence in Congestion Games under Best-Response Dynamics
- Nitin Saxena. Diagonal Circuit Identity Testing and Lower Bounds
Saturday, April 5, 2008
Wednesday, March 26, 2008
The Lipton theory symposium
Richard Lipton is celebrating his 60th birthday this year, and a symposium is organized in his honor. Lipton has several fundamental contributions in complexity theory, algorithms, DNA computing and cryptography. He has a number of specific results that are especially famous, perhaps the most well-known ones are the Karp-Lipton theorem and the planar separator theorem.
Dick Lipton was my PhD supervisor at Princeton, not too long ago. Working with him was a real joy in every aspect. I remember that during our meetings, I felt like he had at least one stoc/focs-paper-idea per day. Looking back at my PhD years in princeton, i think i was fortunate enough to have an "as-good-as-it-gets" phd experience and opportunities, and lipton was a big part of that.
The lipton-symposium announcement follows:
--
Subject: A Symposium in Honor of Dick Lipton's 60th birthday
Dear friends,
On April 26-28, the Georgia Tech College of Computing is hosting a
theory symposium in honor of Richard Lipton's 60th birthday and
his many seminal contributions to Computer Science. Symposium speakers
include Richard Karp, Michael Rabin, Avi Wigderson, Sasha Razborov,
Jin-Yi Cai, Ravi Kannan, and many others.
For more information, including online registration, please visit:
http://www.cc.gatech.edu
We left room in the program for a few contributed talks. Please let us
know if you are interested in speaking at the event.
Looking forward to seeing you in April.
Sincerely,
Dan Boneh
Program Chair
dabo@cs.stanford.edu
Tuesday, March 18, 2008
Theoretical Computer Science day in Sydney
Theoretical Computer Science Day in Sydney
May 14, 2008
Darlington Centre, University of Sydney
CALL FOR PARTICIPATION
The theoretical computer science day will take place in Sydney on May 14, 2008. The aim of this one-day event is to bring together researchers interested in all aspects of theoretical computer science, and discuss current trends and problems in the field, as well as future directions. The EII Network and the organizing committee would like to invite researchers in theoretical computer science to participate in this event. If you are interested in participating, please contact one of the organizers.
The list of invited speakers includes:
Sartaj Sahni University of Florida
Pat Morin, Carleton University
Peter Bro Miltersen, University of Aarhus
The meeting is sponsored by the EII Network, University of Sydney and NICTA.
More information will be available on this page.
ORGANISATION
Joachim Gudmundsson, NICTA, joachim.gudmundsson@nicta.com.au
Taso Viglas, University of Sydney, a.viglas@usyd.edu.au
Tony Wirth, University of Melbourne, awirth@csse.unimelb.edu.au
Sunday, March 2, 2008
new: ACM Transactions on Computation Theory (ToCT)
There is a new journal from ACM, Transactions on Computation Theory (ToCT), with emphasis on computational complexity. Editor-in-chief is lance fortnow, and here is his post announcing the new journal on his blog. The journal will be available through the ACM digital library.
Friday, February 22, 2008
Set up a free journal?
For as long as I can remember our community has been complaining about the costs of "our" scientific journals. I looked up the institutional prices for the journals I usually submit to: Discrete and Computational Geometry ~1000 USD, GeoInformatica ~800 USD and SIAM Journal on Computing ~700 USD. This adds up to a lot of money for the libraries.
So instead we should all submit to cheap/free journals such as the ACM journals (ACM TALG is ~250 USD), Journal of Graph Algorithms and Applications and Chicago Journal on Theoretical Computer Science (is it still alive?). I have two questions:
1. With the exception of the ACM journals, the cheap/free journals don't seem to be doing very well. So why don't we submit to cheap/free journals?
2. Is it hard to start a new journal? If not, why don't we have heaps of new journals? There are new conferences popping up every day, why no new journals? Also, if it's easy why don't we just start one?
So instead we should all submit to cheap/free journals such as the ACM journals (ACM TALG is ~250 USD), Journal of Graph Algorithms and Applications and Chicago Journal on Theoretical Computer Science (is it still alive?). I have two questions:
1. With the exception of the ACM journals, the cheap/free journals don't seem to be doing very well. So why don't we submit to cheap/free journals?
2. Is it hard to start a new journal? If not, why don't we have heaps of new journals? There are new conferences popping up every day, why no new journals? Also, if it's easy why don't we just start one?
Wednesday, February 20, 2008
SWAT deadline passed
We've got 109 submissions to SWAT 2008. Less than expected but hopefully the quality will be higher than expected! Now the hard work of picking the ~35 most interesting papers will start.
Monday, February 18, 2008
CCC 2008 accepted papers
The list of accepted papers for the computational complexity conference was announced last week. From a quick look through the list i picked these 4 for the top of my papers-to-read stack:
NP-hard sets are exponentially dense unless coNP is contained in NP/poly
Harry Buhrman and John M. Hitchcock
Amplifying Lower Bounds by Means of Self-Reducibility
Eric Allender and Michal Koucký
Lower Bounds and Separations for Constant Depth Multilinear Circuits
Ran Raz and Amir Yehudayoff
Constraint Logic: A Uniform Framework for Modeling Computation as Games
Erik D. Demaine and Robert A. Hearn
NP-hard sets are exponentially dense unless coNP is contained in NP/poly
Harry Buhrman and John M. Hitchcock
Amplifying Lower Bounds by Means of Self-Reducibility
Eric Allender and Michal Koucký
Lower Bounds and Separations for Constant Depth Multilinear Circuits
Ran Raz and Amir Yehudayoff
Constraint Logic: A Uniform Framework for Modeling Computation as Games
Erik D. Demaine and Robert A. Hearn
Wednesday, February 13, 2008
SoCG'08 notification
The big day for the CG community is here - the sausage notification. There were 127 submissions of which 42 were accepted. I was lucky to get my paper "A Simple and Efficient Kinetic Spanner" together with Mohammad Ali Abam and Mark de Berg accepted (See previous post).
It was also good to see that some of the students that I've been working with lately had a couple of papers accepted. For example, Martin Nöllenburg had two papers accepted (one son and two SoCG paper in one week, congratulations!) and Maarten Löffler had one paper. Also, Kevin and Maike Buchin who are visiting us at the moment had a paper accepted on Polychromatic Colorings of Plane Graphs.
By only looking at the titles there are several papers that look very interesting, for example, dynamic coresets by Timothy Chan and Similarity Search for Point Sets under Translation by Minkyoung Cho and David Mount. I'm looking forward to read them.
There will probably be more on this in a future post.
It was also good to see that some of the students that I've been working with lately had a couple of papers accepted. For example, Martin Nöllenburg had two papers accepted (one son and two SoCG paper in one week, congratulations!) and Maarten Löffler had one paper. Also, Kevin and Maike Buchin who are visiting us at the moment had a paper accepted on Polychromatic Colorings of Plane Graphs.
By only looking at the titles there are several papers that look very interesting, for example, dynamic coresets by Timothy Chan and Similarity Search for Point Sets under Translation by Minkyoung Cho and David Mount. I'm looking forward to read them.
There will probably be more on this in a future post.
Sunday, February 3, 2008
Sunday, January 27, 2008
CATS'08
Since every blog with some kind of self-respect is reporting from SODA'08, I thought it would be appropriate for this blog to report from CATS'08.
+ Invited talk by Eric Allender. Eric talked about the P vs NP question, and specifically about the question of separating the classes TC0 and NC1. It is known that, for every d, there is a constant c > 1 such that the formula evaluation problem requires TC0 d circuits of size at least nc. Erik argued that it might be possible to obtain a slightly stronger lower bound, showing that there is a c > 1 such that this same set requires uniform TC0 circuits of size nc. Surprisingly this would be sufficient to prove that TC0 is properly contained in NC1.
As a whole the talk was very interesting and at a good level (at least for me). I didn't know much about these classes before and Eric explained all these classes in detail together with a motivation to why they are so important.
+ Business meeting. A few important and positive decisions were made at the business meeting.
James Harland will approach the steering committee of IWOCA to check if it's possible to co-locate IWOCA and CATS in 2010. In my opinion this would be about time. The overlap between the two small communities is too small to warrant two completely separate events.
Next years CATS will include a set of informally invited speakers. That is, a few researchers that would attend anyway will be invited to give a half hour talk about their main research area (or a tutorial). The aim of this is to improve the quality of the talks.
Finally, CATS will encourage further discussions about the accepted papers by making them available on the website and asking for comments on how to improve the papers (results or presentation). Hopefully, this will also encourage more discussion during the presentation.
+ Invited talk by Eric Allender. Eric talked about the P vs NP question, and specifically about the question of separating the classes TC0 and NC1. It is known that, for every d, there is a constant c > 1 such that the formula evaluation problem requires TC0 d circuits of size at least nc. Erik argued that it might be possible to obtain a slightly stronger lower bound, showing that there is a c > 1 such that this same set requires uniform TC0 circuits of size nc. Surprisingly this would be sufficient to prove that TC0 is properly contained in NC1.
As a whole the talk was very interesting and at a good level (at least for me). I didn't know much about these classes before and Eric explained all these classes in detail together with a motivation to why they are so important.
+ Business meeting. A few important and positive decisions were made at the business meeting.
James Harland will approach the steering committee of IWOCA to check if it's possible to co-locate IWOCA and CATS in 2010. In my opinion this would be about time. The overlap between the two small communities is too small to warrant two completely separate events.
Next years CATS will include a set of informally invited speakers. That is, a few researchers that would attend anyway will be invited to give a half hour talk about their main research area (or a tutorial). The aim of this is to improve the quality of the talks.
Finally, CATS will encourage further discussions about the accepted papers by making them available on the website and asking for comments on how to improve the papers (results or presentation). Hopefully, this will also encourage more discussion during the presentation.
Thursday, January 17, 2008
SWAT'08 invited speakers
We've been lucky to get two great invited speakers to SWAT 2008: Michael Mitzenmacher and Vijay Vazirani!
The submission deadline for SWAT is on the 17th of February. This still gives you another month - just enough time to put together a good paper!
The submission deadline for SWAT is on the 17th of February. This still gives you another month - just enough time to put together a good paper!
Filling in reporting forms
December and January seem to be the months when reports are to be written. I just got another one to fill in that is aimed to the federal government. It's not that much to fill in but I find the questions hard to answer. Here are three examples:
- What is special about our approach? (1-2 sentences)
- Relevance of research to business/community (1-2 sentences)
- Technical description of research (1-2 sentences)
I've been staring at these questions for an hour and I don't feel that I'm getting closer to producing any answers. However, I have some some good suggestions that I don't think would be appreciated by the federal government (or NICTA). Any suggestions?
- What is special about our approach? (1-2 sentences)
- Relevance of research to business/community (1-2 sentences)
- Technical description of research (1-2 sentences)
I've been staring at these questions for an hour and I don't feel that I'm getting closer to producing any answers. However, I have some some good suggestions that I don't think would be appreciated by the federal government (or NICTA). Any suggestions?
Wednesday, January 9, 2008
CATS 2008
CATS 2008 is taking place in Wollongong in two weeks. The PC chairs have been able to attract Eric Allender as the invited speaker. I heard him give a great invited talk almost ten years ago so I'm looking forward to the talk.
There will also be the usual business meeting to look forward to. An interesting question that we've discussed at every meeting I attended is how to make CATS more popular. How can we increase the number of paper submissions and the number of attendants? And where should we focus our attention: on Australia, Australasia or the whole world?
The sad truth is that not even the majority of Australian CS theory community attends CATS. What can we do to attract this community? Any ideas?
There will also be the usual business meeting to look forward to. An interesting question that we've discussed at every meeting I attended is how to make CATS more popular. How can we increase the number of paper submissions and the number of attendants? And where should we focus our attention: on Australia, Australasia or the whole world?
The sad truth is that not even the majority of Australian CS theory community attends CATS. What can we do to attract this community? Any ideas?
Tuesday, January 8, 2008
Reviewing a journal paper
I'm currently reviewing a journal paper that's interesting but the presentation is very poor. It's badly organised and the misuse of notations is terrible.
The paper is 30 pages long and I've gone through the first 10 pages (I have 4 pages of comments so far) and I'm getting more and more annoyed at the presentation and the authors sloppiness. I know I signed up to referee the paper but on the other hand I feel that I'm not the one that should clean up the paper. The authors should see to it that it's in good shape when they submit it (I know I'm throwing rocks inside a glass house...).
Can I send back a review report of the first 10 pages urging the authors to improve the writing before they resubmit or do I have to continue to review the remaining 20 pages?
This reminds me of my master thesis (30 pages) that I submitted to a journal about ten years ago. I got back two referee reports three years later containing comments up to page 15 together with the rejection letter. I remember I was terribly disappointed :-)
The paper is 30 pages long and I've gone through the first 10 pages (I have 4 pages of comments so far) and I'm getting more and more annoyed at the presentation and the authors sloppiness. I know I signed up to referee the paper but on the other hand I feel that I'm not the one that should clean up the paper. The authors should see to it that it's in good shape when they submit it (I know I'm throwing rocks inside a glass house...).
Can I send back a review report of the first 10 pages urging the authors to improve the writing before they resubmit or do I have to continue to review the remaining 20 pages?
This reminds me of my master thesis (30 pages) that I submitted to a journal about ten years ago. I got back two referee reports three years later containing comments up to page 15 together with the rejection letter. I remember I was terribly disappointed :-)
Monday, January 7, 2008
Referee request
Today I got a request to referee a paper for a conference (which will remain unnamed). Usually a request is polite and friendly. However, this request was more demanding:
"You have been assigned as a reviewer for the paper XXXXX submitted to XXXXXX'08."
Thus not even asking me if I would like to be a reviewer. Further down in the mail it says:
"The review is due by Jan 26, 2008 10:00 PM, and it is very important that the review be turned in before this deadline."
It then continues:
"If you are unable to complete this review assignment for any reason, please send an email to the TPC chairs indicating the reasons for which you are unable to do this assignment."
So if I won't accept the kind invitation I have to motivate my decision? Can it be that the TPC won't accept my motivation? If so, do I have to referee the paper? What annoys me the most is that I actually sent a polite reply containing a short explanation why I couldn't referee the paper.
"You have been assigned as a reviewer for the paper XXXXX submitted to XXXXXX'08."
Thus not even asking me if I would like to be a reviewer. Further down in the mail it says:
"The review is due by Jan 26, 2008 10:00 PM, and it is very important that the review be turned in before this deadline."
It then continues:
"If you are unable to complete this review assignment for any reason, please send an email to the TPC chairs indicating the reasons for which you are unable to do this assignment."
So if I won't accept the kind invitation I have to motivate my decision? Can it be that the TPC won't accept my motivation? If so, do I have to referee the paper? What annoys me the most is that I actually sent a polite reply containing a short explanation why I couldn't referee the paper.
Subscribe to:
Posts (Atom)
