# Constraints

## 27 April 2008

### easier authentication

Filed under: Ideas — András Salamon @ 13:01

It would be handy to have a fingerprint reader that pretended to be a USB keyboard when one puts one’s finger on it, typing a pre-stored password or username/password combination.

Even better would be one with a dial to choose which password to enter (the built-in display would show the mnemonic attached to each dial setting).

Not incredibly secure (the target computer could be running software that captured keyboard input), but a little more secure than a password crib sheet, and rather more convenient.

Who is going to build one of these?

## 14 April 2008

### ICALP 2008 accepted papers

Filed under: Commentary — András Salamon @ 14:52
Tags: ,

After wading through a torrent of submissions, the ICALP programme committee released the final list of accepted papers this week. There are 126 in total, 70 in track A (last year: 76 and 41). It looks like over 20 papers a day are going to be jostling for attention in multiple parallel sessions.

A paper I found interesting is

Marc Tedder, Derek Corneil, Michel Habib and Christophe Paul. Simple, Linear-Time Modular Decomposition

This paper claims to be the first practical implementation of linear time modular decomposition, which is used as a building block by many efficient graph algorithms. Jens Gustedt pointed out a few years ago that the Ehrenfeucht et al. algorithm from 1994 seems to have runtime $\min(n^2,m \log n)$, which is slightly worse than linear. This certainly has been implemented, although I’m unsure if the bound Jens suggested is achieved by this code; Ross McConnell also mentioned a previous implementation (lost in the mists of time). Implementing the 1994 algorithm involves some fairly nontrivial bits, mostly in reconstructing missing `obvious’ details. I am therefore looking forward to reading the paper in detail — it would be nice to have an algorithm that can be implemented, and that still achieves linear runtime.

Blog at WordPress.com.