ISAAC - Day 3

Today I gave my two presentations. Both papers are about trajectories, or what is sometime called geospatial lifelines, which is the the research topic of our project in Sydney. In the first paper we consider the problem of compressing, or simplifying, trajectories such that both the spatial and temporal information is preserved. The problem has been studied earlier in the database community, however, we gave a first method that guarantees that approximate versions of standard operations such as where_at, when_at and nearest neighbour are "sound". We also showed how the simplification can be done in O(n log^3 n) time (in practice the standard Douglas-Peucker algorithm in 3D works like a charm).

The second paper considered the problem of computing a "popular place" in a set of trajectories. A popular place is just a region, in our case a square of given side length, that is "visited" by at least k different trajectories. Our main result is a quadratic time algorithm with a "matching" 3-SUM hardness proof.

Both presentations went okay and hopefully some of the participants now have an idea of the existing problems in the area.

Finally I had sushi!

Tomorrow I'm going back to Sydney and my new office which is on the top floor of the School of IT building at University of Sydney.

ISAAC - Day 2

I overslept and missed the invited talk by Robin Thomas. The rest of the day I again mostly listened to geometry papers, except a presentation on game theory by Stefan Schmid (Eidenbenz, Oswald and Wattenhofer). They considered an extended version of the prisoners'dilemma. I'm far from an expert in the area but it seems to have some relation to the concept of putting taxes on edges in a network as proposed by Cole, Dodis and Roughgarden.

Another talk that I found interesting was by Tetsuo Asano who gave a talk on triangulations with Steiner points. That is, the aim is to triangulate a polygon while optimising some criterion. However, you're allowed to add, say k, Steiner points in the interior. How will you add the Steiner points such that the criterion is optimised? They showed polynomial time algorithms for adding a constant number of Steiner points while optimising the maximum interior angle.

Today was also the day of the conference banquet. We were served a French/Italian dinner. I still haven't had any sushi since I arrived!!!

ISAAC - Day 1

After a week of diving in Thailand (Similan Islands) together with my fellow blogger Tasos, I'm now attending ISAAC in Sendai. Yesterday there was a workshop in the honour of Prof. Nishizeki's 60th birthday. Prof. Nishizeki founded ISAAC in 1990 in order to expand the research community to Asia and the Pacific. Unfortunately I missed most of the talks but during the afternoon I attended a talk by Dorothea Wagner. She talked about her favourite topic, routing in transportation networks. This is a topic that I find very appealing. Dorothea and her group use more "algorithmic engineering" than what I'm used to but I still find both the problem and the techniques used to obtain a practical solution very interesting. She covered the algorithmic engineering approaches which proves that a good theoretical understanding of a problem can give very fast and effective solutions.


The first talk at ISAAC was an invited talk by Pankaj Agarwal. He talked about I/O-efficient algorithms for analysing terrain data. As usual Pankaj gave an excellent talk that was easy to follow and still gave some insight into the problems in the area. The rest of the day I mainly attended the computational geometry sessions. It's surprising how many of the papers that are in the computational geometry field. I went through the program and concluded that almost half the papers are geometry related.

Australian rankings of theory conferences

CORE is an association of university computer science departments from Australia and New Zealand. Lately CORE and therefore Australian and NZ CS academics, have been busy preparing rankings for conferences and journals.

It is not clear (to me and most people I know) what the purpose of those rankings will be exactly, but most likely they will be used as a guideline for funding projects from the ARC, and for the RQF, the research quality framework in Australia. It is also not clear (to me and most people I know) if this is an one-off thing or there is some intention to keep these lists updated.

CORE (= the academics in australia) recently published rankings for computer science conferences. There is a description of the process that was followed and a description of the tiers.

My understanding of the process, is that it was very much ad-hoc, and involved lots of people saying their opinion about conferences ("this conference is top because i have a lot of papers in it") and then some select core committee put everything together.

My interpretation of the intended meaning of the tiers is as follows:

• tier 1: the top conferences in the field
  
• tier 2: respectable entries in your CV
• tier 3: still in your CV but it's "your student's paper" if anyone asks. no-one will ask though.
  
• tier 4: you wouldn't include these in a promotion or grant application (in a reasonable place) and the only acceptable excuse would be that the conference was in bora-bora or hawaii.

I am guessing that Tier 5 would be conferences of the type "dear author, your paper has been accepted, even though you haven't sent one. By the way, please consider submitting more than one papers, you only have to pay registration once"

The tiers were at some point renamed to A+, A, B, C.

I filtered out some theory conferences from the list.

• A+ conferences include: STOC, FOCS, SODA, CG
• Tier A: ALENEX, APPROX, CCC, COCOON, EC, ESA, FST&TCS, GD, ICALP, IPCO, ISAAC, RANDOM, SAT, STACS, SWAT,
• Tier B: ALEX, ANALCO, AofA, AWOCA, CATS, CCCG, COCOA, DMTCS, FCT, FUN, ICTAC, LATIN, MFCS, SIROCCO, WG
• Tier C: ACID, AWOCA, EWCG, ICTCS, WALCOM, WAW,

List with complete names follows.

Tier A+

• ACM SoCG ACM Symposium on Computational Geometry
• FOCS IEEE Symposium on Foundations of Computer Science
• SODA ACM/SIAM Symposium on Discrete Algorithms
• STOC ACM Symposium on Theory of Computing

Tier A

• ALENEX Workshop on Algorithm Engineering and Experiments
• APPROX International Workshop on Approximation Algorithms for Combinatorial Optimization Problems
• CCC IEEE Symposium on Computational Complexity
• COCOON International Conference on Computing and Combinatorics
• EC ACM Conference on Electronic Commerce
• ESA European Symposium on Algorithms
• FST&TCS Foundations of Software Technology & Theoretical Computer Science
• GD Graph Drawing
• ICALP International Colloquium on Automata, Languages and Programming
• IPCO MPS Conference on integer programming & combinatorial optimization
• ISAAC International Symposium on Algorithms and Computation
• RANDOM International Workshop on Randomization and Computation
• SAT International Conference on Theory and Applications of Satisfiability Testing
• STACS Symposium on Theoretical Aspects of Computer Science
• SWAT Scandinavian Workshop on Algorithm Theory

Tier B

• ALEX Algorithms and Experiments
• ANALCO Workshop on Analytic Algorithms and Combinatorics
• AofA Conference on Analysis of Algorithms
• AWOCA Australasian Workshop on Combinatorial Algorithms
• CATS Computing: The Australasian Theory Symposium
• CCCG Canadian Conference on Computational Geometry
• COCOA Conference on Combinatorial Optimization and Applications
• DMTCS International Conference on Discrete Mathematics and Theoretical Computer Science
• FCT Fundamentals of Computation Theory
• FUN Conference on fun with algorithms
• ICTAC International Colloquium on Theoretical Ascpects of Computing
• LATIN International Symposium on Latin American Theoretical Informatics
• MFCS Mathematical Foundations of Computer Science
  
• SIROCCO Colloquium on Structural Information and Communication Complexity
• WG Workshop on Graph Theory

Tier C

• ACID Algorithms and Complexity in Durham
• AWOCA Australasian Workshop on Combinatorial Algorithms
• EWCG European Workshop on Computational Geometry
• ICTCS Italian Conference on Theoretical Computer Science
• WALCOM Workshop on Algorithms and Computation
• WAW Workshop on Algorithms and Models for the Web-Graph

Australian journal ranking - Part II

I feel very proud of myself. I finally took time to write a couple of proposals for the Australian journal ranking. I wrote proposals for the three computational geometry journals (DCG, CGTA and IJCGA) and Algoritmica. I proposed to rank all of them as Tier A journals (categories are A+, A, B, C). This might not be entirely fair, however, if you look at the other journals ranked as Tier A+, A and B I think it's an accurate ranking. A+ only contains three journals from my field: JACM, SICOMP and ACM Transactions of Algorithms, which I think is reasonable. Tier A contains all other decent journals and Tier B and C contains the rest. There is also category U containing journals that haven't been ranked yet.

Free registration for chairs?

I just found out that only one of the two co-chairs for each conference at ACSW'08 is allowed a free registration. I found it a bit strange, especially since the two co-chairs do all the work (except the local arrangements). Without the chairs there would be no conference.

Australian conference/journal ranking

Why do Australian CS researchers create their own conference/journal ranking? If it is so important to rank conferences/journals why don't they use existing international rankings? Instead we are all allowed to suggest how a specific conference/journal should be ranked. With such a small set of CS researchers publishing in good conferences/journals the result is bound to be skewed to "personal favourites".

I actually took the time to try to re-rank some of the more obvious mistakes in the conference ranking a few months ago, but I never took the time to go through the journal ranking - big mistake. Today I looked at the Australian journal ranking and realised that there is not a single computational geometry journal on the list. Furthermore, Algorithmica, Journal of Combinatorial Optimization and many more theory journals are not on the list. Out of my 30 journal publications I believe 4 are published in a ranked journal! The quality of my publications is not great but still - four!!!

Of course most of us don't take this to serious...until it's time to apply for grants. It's not easy to work in CS theory here in Australia but we're not making it easier for us by ignoring the conference/journal rankings. I hope all Australian CS theory people will take a look at the ranking and propose changes to the list. Fill in the following form and submit to conference.rankings at core.edu.au (the same form/address is used for journals).

game theory related papers in SODA 2008

Below is a list of game-theory related papers, to appear in SODA 2008. Only half of them showed up on my google searches and seem to be available online.

1. Incentive Compatible Regression Learning, Ofer Dekel and Felix Fischer and Ariel D. Procaccia (pdf)
   
2. On the Value of Coordination in Network Design, Susanne Albers
3. Designing Networks with Good Equilibria, Ho-Lin Chen and Tim Roughgarden and Gregory Valiant (pdf)
   
4. Fast Load Balancing via Bounded Best Response, Baruch Awerbuch and Yossi Azar and Rohit Khandekar
   
5. Fast Algorithms for Finding Proper Strategies in Game Trees, Peter Bro Miltersen and Troels Bjerre Sorensen (pdf)
   
6. Succinct Approximate Convex Pareto Curves, Ilias Diakonikolas and Mihalis Yannakakis
7. (Almost) Optimal Coordination Mechanisms for Unrelated Machine Scheduling, Yossi Azar and Kamal Jain and Vahab Mirrokni
8. The complexity of game dynamics: BGP oscillations, sink equlibria, and beyond, Alex Fabrikant and Christos H. Papadimitriou (ps)
   
9. Charity Auctions on Social Networks, Arpita Ghosh and Mohammad Mahdian
10. Minimizing average latency in oblivious routing, Prahladh Harsha and Thomas Hayes and Hariharan Narayanan and Harald Raecke and Jaikumar Radhakrishnan
11. On Allocations that Maximize Fairness, Uriel Feige (pdf)
    

Algorithmics activities in NZ

In February there will be a 5-day algorithmics meeting in Napier, New Zealand. They got five great speakers, Steve Linton, Dominic Welsh, Michael Mitzenmacher, Michael Langston and Brendan McKay, so I'm sure it will be a very interesting week.

ACSW 2008 registration fee

After writing several posts complaining about the registration fees of ACSW (CATS) and IWOCA I just found out that the (late) full fee for ACSW is A$ 750 and only A$ 275 for students. It's not cheap but it is at least a step in the right direction (last year's fee was A$900). Go ACSW!

SWAT 2008

SWAT 2008 (Scandinavian Workshop on Algorithm Theory) will take place on the 2-4th of July 2008 in Gothenburg. Sweden (and especially Gothenburg) is well worth a visit. In July the days are long, sunset around 11pm and sunrise around 3:30am (in the north the sun never sets), and the weather is usually perfect. The submission deadline is on the 17th of February, so it's time to start the research and plan your summer vacation.

Advertisers study quantum computing?

A recent Australian TV ad for Ricoh turned out to be plagiarising Scott Aaronson's quantum mechanics lecture. More in the the Sydney Morning Herald.

Workshop in the Netherlands

I just came back from a great workshop in the Netherlands organised by Marc van Kreveld. The topic was on geometric algorithms for problems motivated from spatial data mining and spatio-temporal data mining. We were 15 researchers, mostly working in computational geometry, but also one geographer.

The first day Patrick Laube from Melbourne gave a very interesting overview of the area and proposed lots of open problems, which we spent the rest of the week trying to solve. In general I very much enjoy these kinds of workshops. It gives you the opportunity to work with new people and learn about new problems. What made this workshop special was that everyone seemed to work with everyone. There was even one problem that I think almost all of us were involved in, so if we get a paper out of it I wouldn't be surprised if it will be a 15 authors paper. It might be an annoying process to write the paper but the research was great!

Kinetic spanners

Today and tomorow I'm in Eindhoven. I spent most of the day working together with Mark de Berg and Mohammad Abam on the problem of constructing kinetic spanners. That is, given a set of moving points in the plane can we maintain a t-spanner with a small number of topological changes, for a given constant t>1.

Previous work on this problem includes a paper by Karavelas and Guibas (SODA'01) and a paper by Agarwal, Wang and Yu (SoCG'04). Agarwal et al. show that a triangulation (the Delauany triangulation is known to have small dilation) can be maintained with n^2 * 2^{\sqrt{\log n \loglog n}} topological updates, if the trajectories of the input points are algebraic curves of fixed degree. We hope to be able to prove similar results for t-spanners.

We looked at this problem before but this time we were lucky to obtain some initial results so I'm looking forward to continue the discussion tomorrow.

Congratulations Mattias

Two days ago Mattias succesfully defended his thesis on "Approximation algorithms for geometric networks" in Lund. The faculty opponent, Marc van Kreveld, gave a very nice overview of the thesis. This was followed by lots of questions from Marc and the review committee consisiting of Rolf Klein (Bonn), Pavel Winter (Copenhagen) and Bengt Nilsson (Malmo). After the decision to accept the thesis there was a big dinner for family, friends and colleageus.

A Swedish PhD defence

I'm in Sweden for a few days to attend Mattias' PhD defence. In Sweden it works as follows. The thesis is published as a book a few weeks before the actual defence. It is then sent out to the committee and the opponent (more on that later) at least three weeks before the defence.

The actual defence is completely open, anyone can attend. Your colleagues are there together with friends and family. There is one opponent, in this case Marc van Kreveld. He will present the thesis which usually takes between half an hour and an hour. After that there's a short break which is followed by a long questioning session where the opponent starts, followed by the review committee. The committee has three members which usually ask a few questions each; however, I've been to defences where this part has been very long. When this is done, usually between one and two hours, anyone is allowed to ask questions. This is the part where some entertaining questions sometimes can be heard. This concludes the defence and now the committee, the opponent and the supervisors have a meeting to discuss if the candidate deserves to pass or not (although the supervisors are only there to observe and to give additional information to the group). In the Swedish system there is only pass or fail, however, the latter decision only happens at very rare occasions. The best part is the party afterwards where everyone gets drunk.

In Australia the system is very different. When you finish the thesis you send it off to a committee consisting of three reviewers. The reviewers will (hopefully) read it and return their report within six weeks (although I heard stories that it could take several months). The decision can be accept, accept with minor revision, accept with major revision or fail.

Even though the Swedish tradition might be slightly outdated I very much enjoy it. I like it since your PhD reaches a climax at the defence. I thought it was great to have friends, family and colleagues listening to what I spent all those years on. For some reason you don't get the same feeling in the Australian system when you send off the pdf file to the university administration.

CATS vs. IWOCA

In a previous post Tasos was complaining about the CATS registration fee (900 AUD), and claimed that the registration fee for IWOCA would be much cheaper. However, I just saw on the IWOCA website that the registration fee is 800AUD (650AUD for students)! I'll probably stay at home....

How can it be so expensive? Is it the transition from AWOCA to IWOCA?

Thesis types

At the moment three out of my four PhD students are about to finish their thesis. The thesis are all very different. Mohammad Farshi's thesis is quite technical and very foucussed on geometric spanners. Damian Merrick's is foucussed on metro map layout and maybe not as technical as Mohammad's, instead he uses several different approaches. Finally, Mattias Andersson's is much more dispersed and considers many different problems and techniques. Is any of the thesis more preferable than the others?

When I was a PhD student I remember that I was a strong advocate of Mattias' type of thesis (which was also my type of thesis). A new day, a new problem. But nowadays I would probably prefer Mohammad's type of thesis. I believe that there is an added research experience in closely focussing on one type of problems. It takes a long time to really understand a hard group of problems and the satisfaction of solving a problem that you've been working on for a looong time is hard to describe if you haven't done it yourself.

Are there many other types of thesis in CS theory? Do different countries require different types?

Dagstuhl - a meeting place

Dagstuhl is a great institution. I recently spent another week there and as usual it was pure pleasure. It is is an old castle that has been converted into a research conference centre. Almost every week for the whole year it hosts one or two workshops in various areas of computer science. The castle is quite secluded and there are no cities close by (it takes two hours to Frankfurt), thus nothing to distract you from your research. Generally the workshops includes between 15-50 researchers and the Dagstuhl personnel takes care of almost all the administration. On top of that the prize is heavily subsidised.

I know there is a similar place in Italy, although I never been there. McGill has a place in Barbados that is used for a similar purpose, but I don't think the administration is as well developed as at Dagstuhl. Are there any other places around? Is there anything like this in Australia? If not, why not?

SODA 2008 accepted papers

the list of accepted papers for SODA 2008 is out it seems.

lists of accepted papers for theory conferences

A useful webpage that keeps an updated list of accepted papers for theory conferences.
the webpage is maintained by Iftah Gazmu at tel-aviv university. There is also a list of events with upcoming deadlines and conference dates.

ARC funding for theory projects

ARC (Australian Research Council) Discovery projects are the main source of funding for theoretical computer science research in australia. ARC publishes all data about the projects that are funded including the level of funding per year. It is not too easy to figure out exactly which projects should be considered as "theory" but one way would be to use the RFCD codes that ARC uses to classify research areas.

ARC funds about 4 Discovery projects per year in the RFCD code 2804 that seems to be the closest to theoretical computer science. Projects run for 3 years. In the last 2 years the total budget awarded was about $1m to these theory projects. That's about $85K per project per year. Each project has an average of 2.6 names on it. Which means that the average funding is about $32K per project per year per person named on the proposal. It could be that about 30 theorists have an ARC discovery project running. Since it is allowed to have a maximum of 2 discovery projects at the same time, there should be between 15 and 30 theorists with an ARC discovery running at the moment.

The Computer science research area is within the RFCD code 280000-Information, computing and communication sciences. The "theory" RFCD code should be 2804-Computation theory and mathematics. The 280000 ICT area has 5 RFCD codes/sub-areas as shown in the table below. Those are the areas that actually received funding in the last 3 years.

In the past 3 years, 2005-7 (2007 means "funding awarded in 2006 for projects beginning in 2007") the ARC funded proposals as follows:

code	Area	2007	2006	2005
2801	Information systems	18	23	16
2802	AI and signal processing	24	16	20
2803	software	5	5	10
2804	comp theory	4	4	10
2805	Data format	5	8	7
2800	All ICT- total (280000)	56	56	64*

Source: ARC website. * in 2005 there was one more proposal funded in the "Other ICT" category, RFCD code 2899.

In 2007 the 4 projects in the theory RFCD code were the following:

1. Efficient Pre-Processing of Hard Problems: New Approaches, Basic Theory and Applications, Griffith University, Prof V Estivill-Castro; Dr MR Fellows; Prof MA Langston, $380K in 4 years
   
2. A Virtual Electromagnetic Compatibility (EMC) Lab Based on Advanced Computer Modeling and Simulation Techniques, Griffith University, A/Prof J Lu; Dr E Li, $275K in 3 years
   
3. Information security and digital watermarking with Latin squares, Monash University, Dr TE Hall; Dr IM Wanless; Dr AZ Tirkel, $223K in 3 years
   
4. Application of novel exact combinatorial optimisation techniques and metaheuristic methods for problems in cancer research, The University of Newcastle, Dr PA Moscato; Prof RJ Scott; Dr MA Langston, $237K in 3 years
   

In 2006 ("funding begins in 2006") the 4 projects in the theory RFCD code were the following:

1. Early detection of component incompatibility in time-dependent computer architectures, University of Adelaide, DG Hemer, $157K in 3 years
2. Fast, practical and effective algorithms for clustering with advice, University of Melbourne, Dr AI Wirth, $153K in 3 years
3. A Grid-Enabled Meta-Server for Protein Threading, University of Sydney, Prof AY Zomaya; Dr B Zhou; Dr M Charleston; Dr A Viglas, $366K in 3 years
4. Foundations of Nonmonotonic Logic Programming for Complex Knowledge Systems, University of Western Syndey, A/Prof Y Zhang; Dr AC Nayak; Dr K Wang; A/Prof F Lin, $234K in 3 years

In 2005 ("funding begins in 2005") the 10 projects in the theory RFCD code appear in the list below. Note that 4 of these projects may not be directly related to computer science theory.

1. An innovative computational technique for the study and control of oscillation marks in continuous casting of steel, Curtin University of Technology, A/Prof Y Wu, $190K in 3 years
2. Coarse Grained Parallel Algorithms, Griffith University, Prof FK Dehne, $206K in 3 years
3. Algebraic reasoning for serialisability in probabilistic transaction systems, Macquarie University, Dr AK McIver; Dr CC Morgan; Prof T Nipkow, $147K in 3 years
4. Devising sophisticated computational comparative genomic analysis strategies for animal and plant genomes, Murdoch University, Prof M Bellgard; A/Prof JK Kulski; Prof R Appels; Dr RH Taplin; A/Prof RR Barrero, $160K in 3 years
5. THE DEVELOPMENT OF MECHANISTIC MODELS FOR BUBBLY FLOWS WITH HEAT AND MASS TRANSFER, RMIT University, A/Prof JY Tu; Dr GH Yeoh; Prof G Park, $178K in 3 years
6. Advanced computational techniques for micro/nano multiscale systems of NEMS/BioMEMS, The University of Sydney, Dr Y Gu, $222K in 3 years
7. Optimum design of controlled drug delivery systems, The University of Western Australia, A/Prof S Wang; Dr X Lou, $231K in 3 years
8. Knowledge Based Model Updating for the Correctness of Security Protocols, University of Western Sydney, A/Prof Y Zhang; A/Prof MA Orgun; Dr AC Nayak; Dr Y Mu; Dr F Bao, $284K in 3 years
9. Timeless digital signature for self-organising groups, University of Wollongong, Prof R Safavi-Naini; Prof PR Wild, $278K in 3 years
10. Short Signatures: Tools for Securing Digital Transactions, and Their Applications, University of Wollongong, Dr W Susilo; Dr Y Mu; Dr F Zhang, $192K in 2 years

RFCD codes

the RFCD (Research Fields, Courses and Disciplines Classification) codes for computer science are organized as follows:

• 2800 INFORMATION, COMPUTING AND COMMUNICATION SCIENCES
  
  1. 280100 Information Systems
     
  2. 280200 Artificial Intelligence and Signal and Image Processing
     
  3. 280300 Computer Software
     
  4. 280400 Computation Theory and Mathematics
     1. 280401 Analysis of Algorithms and Complexity
        
     2. 280402 Mathematical Logic and Formal Languages
        
     3. 280403 Logics and Meanings of Programs
        
     4. 280404 Numerical Analysis
        
     5. 280405 Discrete Mathematics
        
     6. 280406 Mathematical Software
        
     7. 280499 Computation Theory and Mathematics not elsewhere classified
        
  5. 280500 Data Format
     
  6. 289900 Other Information, Computing and Communication Sciences
  
  

on CATS

I thought that the registration fee for CATS2007 was totally ridiculous. Complaining about conference fees is very common indeed, but still...
here is a comparison of registration fees in some of the best theory conferences around:

registration fees (late registration):
FOCS 2007: 435 USD = 528 AUD
STOC 2007: 425+100(FCRC fee)=525USD = 637 AUD (516AUD when it's not in the FCRC)
SoCG 2007: 283 EUR = 468 AUD
CCC'06: 300 EUR = 496 AUD

CATS07: 900 AUD

What could be the explanation for this?
IWOCA seems to be more reasonable with a registration at 380AUD. CATS is organized as part of the ACSW multi-conference event and is overseen by Computer Research and Education Association (CORE - previously CSA).

Perhaps IWOCA should be the "local" theory conference of choice?

Australian CS Theory Conferences

There are two annual CS theory conferences in Australia - CATS and IWOCA (formerly known as AWOCA). Both seem to struggle with their identity. Should they aim to become internationally renowned conferences or should they mainly focus on bringing researchers together from the region? I know there are drawbacks with both choices, but imho they should focus on the latter.

First of all there are already too many conferences of questionable standards that claim to be prestigious, secondly I don't see anything wrong with being a regional conference whose aim is to bring Asia-Pacific researchers together. I always try to attend CATS since I think it's important for the Australian CS theory community to be active, however, I'm not keen on submitting a paper that could be accepted to a much better conference, especially not if any of my co-authors is a student.

In Europe the computational geometry community have had big success organising the European Workshop on CG (EWCG). The format allows everyone to submit a four page abstract that is reviewed for correctness. Almost all the papers are accepted but they are not published in any official proceedings, thus allowing the authors to submit their paper to more prestigious conferences. The success of the workshop shows that this is a possible (even recommendable?) format. The majority of the European CG community usually attend so it's a great place to meet all colleagues.

I heard people say that this format isn't possible because they can't get funding for it. However, I don't see this is a problem. Especially not since Australian academia seems to be all about networking and very little about doing good research.

Minimum dilation trees- Part II

On the last day of the Dagstuhl week we (Christian Knauer and Michiel Smid) finally made some small progress. We were able to prove the following: Let G=(V,E) be a metric graph that contains a minimum dilation tree with dilation D. Given any t-spanner G' of G it hold that G' contains a tree of dilation O(t^2D^2). For some special cases it seems that we can obtain slightly better bounds. For example for a Delaunay triangulation of points in the Euclidean space where the bound probably is O(tD^2). Anyway, the proof is non-constructive so the main problem still remains. How can we find such a tree?

This week I'm attending the Korean Workshop on Computational Geometry at Dagstuhl in Germany (more on this in a later post). The first day was dominated by open questions and some very nice problems were presented. Panos Giannopoulos stated the problem of approximating a minimum dilation path/tour/tree. It is known that these problems are NP-hard (see for example Cheong, Haverkort and Lee'07) but can we find good approximation algorithms? There is an algorithm by Badoiu, Indyk and Sidiropoulos from SODA 2007 that embeds a metric into a tree metric with distortion (c \log n)^{O(\sqrt{\log \delta}), where c is the best distortion that can be achieved. Using this one can obtain a (\log n)^{O(\sqrt{\log n}) approximation of a minimum dilation tree. Of course it's not very good and it should be possible to achieve a much better bound in our special case. However, our only result so far is that there exists a (1+x)-approximation of a minimum dilation tree that has O(1/x) degree, for any x>0. It's a small observation but it might help.

Why dense outliers?

Many people asked us (not really, but it's a good way to start a blog) about the name of the blog. Joachim came up with the word `outlier' since we sometime feel like we're very far from the real theory action and we're like outliers among Australia's overwhelming majority of applied cs researchers. We're often dreaming about the good times, when we were doing our PhDs or postdocs in more theory intense places. Tasos came up with the word `dense' to describe our intellectual capacity.

The aim of this blog is to have a forum for us, for other Australian cs theoreticians (we know you're out there!) and for anyone else that wants to discuss cs theory stuff that may or may not be related to Australia - this really narrows it down.