## Sunday, December 23, 2007

### ISAAC - Day 3

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

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!!!

## Friday, December 21, 2007

### ISAAC - Day 1

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.

## Wednesday, November 21, 2007

### Australian rankings of theory conferences

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.

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,

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

- 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

- 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

- 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

## Thursday, November 15, 2007

### Australian journal ranking - Part II

## Tuesday, November 6, 2007

### Free registration for chairs?

## Thursday, October 25, 2007

### Australian conference/journal ranking

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).

## Tuesday, October 23, 2007

### game theory related papers in SODA 2008

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

## Thursday, October 18, 2007

### Algorithmics activities in NZ

## Monday, October 15, 2007

### ACSW 2008 registration fee

## Wednesday, October 10, 2007

### SWAT 2008

### Advertisers study quantum computing?

## Tuesday, October 9, 2007

### Workshop in the Netherlands

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!

## Friday, September 28, 2007

### Kinetic spanners

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

## Monday, September 24, 2007

### A Swedish PhD 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.

## Wednesday, September 19, 2007

### CATS vs. IWOCA

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

## Monday, September 17, 2007

### Thesis types

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?

## Tuesday, September 11, 2007

### Dagstuhl - a meeting place

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?

## Monday, September 10, 2007

### SODA 2008 accepted papers

### lists 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.

## Friday, August 31, 2007

### ARC funding for theory projects

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:

- 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
- 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
- Information security and digital watermarking with Latin squares, Monash University, Dr TE Hall; Dr IM Wanless; Dr AZ Tirkel, $223K in 3 years
- 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:

- Early detection of component incompatibility in time-dependent computer architectures, University of Adelaide, DG Hemer, $157K in 3 years
- Fast, practical and effective algorithms for clustering with advice, University of Melbourne, Dr AI Wirth, $153K in 3 years
- 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
- 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

- 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
- Coarse Grained Parallel Algorithms, Griffith University, Prof FK Dehne, $206K in 3 years
- Algebraic reasoning for serialisability in probabilistic transaction systems, Macquarie University, Dr AK McIver; Dr CC Morgan; Prof T Nipkow, $147K in 3 years
- 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
- 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
- Advanced computational techniques for micro/nano multiscale systems of NEMS/BioMEMS, The University of Sydney, Dr Y Gu, $222K in 3 years
- Optimum design of controlled drug delivery systems, The University of Western Australia, A/Prof S Wang; Dr X Lou, $231K in 3 years
- 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
- Timeless digital signature for self-organising groups, University of Wollongong, Prof R Safavi-Naini; Prof PR Wild, $278K in 3 years
- 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

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

- 2800 INFORMATION, COMPUTING AND COMMUNICATION SCIENCES
- 280100 Information Systems
- 280200 Artificial Intelligence and Signal and Image Processing
- 280300 Computer Software
- 280400 Computation Theory and Mathematics
- 280401 Analysis of Algorithms and Complexity
- 280402 Mathematical Logic and Formal Languages
- 280403 Logics and Meanings of Programs
- 280404 Numerical Analysis
- 280405 Discrete Mathematics
- 280406 Mathematical Software
- 280499 Computation Theory and Mathematics not elsewhere classified

- 280401 Analysis of Algorithms and Complexity
- 280500 Data Format
- 289900 Other Information, Computing and Communication Sciences

- 280100 Information Systems

## Thursday, August 30, 2007

### on CATS

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?

## Thursday, August 23, 2007

### Australian CS Theory Conferences

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.

## Sunday, July 29, 2007

### Minimum dilation trees- Part II

## Tuesday, July 24, 2007

This week I'm attending the Korean Workshop on Computational Geometry at Dagstuhl in

## Thursday, July 19, 2007

### 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.