Tag search: "compsci"

RSS feed for this tag:

Matthew Skala's academic publications

Bibliographic information and links. (31 December 2009)

Constraint satisfaction in string spaces

Informal talk from the 2009 BIRS Workshop on Mathematics of String Spaces and Algorithmic Applications (5 February 2009)

Counting Distance Permutations (JDA version)

Resources and links on the extended journal version of my paper Counting Distance Permutations. (23 September 2008)

On constructivism

I think that actually building things that work is often an underrated activity in computer science. Recently I had the experience, and it has happened to me many times before, of telling someone about work I'd done and getting the response, "Well, that's just engineering..." It's application of known principles; it doesn't help us learn new things; it's not capital-S Science; it's not valuable; it's just engineering.

(14 July 2008)

Unofficial University of Waterloo Thesis Template

Here's a template (ZIP format) created by stripping most of the content out of my PhD thesis source code to leave just the formatting. If you're using LaTeX to typeset a thesis for the University of Waterloo, especially in computer science, you might find this helpful. No warranties, but as far as I know it meets the current GSO formatting requirements. My thesis made with it passed their review on the first try. It's also supposed to look good, to the extent possible within the requirements. I got some favourable comments from my committee members on the formatting of my thesis, so I think I was at least sort of successful on that score. It comes with documentation on how to use it. You will need at least an intermediate level of LaTeX knowledge, because it uses a bunch of external packages for fonts and so on. I'm releasing it to public domain.

(24 June 2008)

On the Complexity of Reverse Similarity Search

Resources and links on my paper On the Complexity of Reverse Similarity Search, which appeared in SISAP '08. (26 April 2008)

Counting Distance Permutations (SISAP version)

Resources and links on my paper Counting Distance Permutations, which appeared in SISAP '08. (26 April 2008)

Simplified file holography

I did some more thinking about my holographic filesystem ideas and some reading on coding theory and I realized that most of the complexity of the system actually comes from the desire to make it work for read-write.  If we design it more narrowly for read-only media like DVD-R discs, and tie less closely to the operating system's filesystem code, the result can be much more compatible and keep most of the advantages.  The new idea is that instead of being a full filesystem, it would come as two utilities:  one that appends extra redundant blocks to an existing filesystem image so that it will be more recoverable in the future, and another that performs the recovery.  If no blocks in the main image are lost, then the filesystem can be read normally by software that doesn't know about the recovery scheme, just ignoring the extra data at the end. (21 March 2008)

Holographic Filesystem

In preparation for the end of this phase of my life and the start of the next, I've been digging through the files on the computer I mothballed several years ago when I bought my present one - looking at organizing them and archiving so that my old projects won't be lost.  I've found that the hard drive on that machine has developed some bad blocks, and that reminded me of an idea I once had for an holographic filesystem.  I've also been painfully reminded that I used to do a lot of cool things and I haven't done very many lately, so that it's time to start some interesting new projects, and this might be a good start for one. (18 March 2008)

The Sultan's daughters

Today when I was supposed to be working on my thesis, I got sidetracked thinking about the Sultan and his daughters. I took a look around the Net and didn't immediately find anything about this in the literature, so there's some possibility it may even be an original research problem. I'm posting it here because I think it's interesting and to see if any readers have ideas on it. Let me know if you're aware of anything published about it or if you think there isn't any and want to be in on trying to actually do some real research. Posting in "software" because I don't really have a "math" category... but maybe I should. If it appears to be an open problem, I might even post a bounty on it. (20 October 2007)

Buried in bits

Almost ten years ago, I read a fascinating essay by George Gilder in Computer Underground Digest, reprinted from Forbes.  He predicted that in The Future, technologies like the erbium doped fiber amplifier would cause bandwidth to grow faster than CPU power, and that that would eventually have drastic effects on how we do computing and networking.  I'm not sure that prediction has really come true, but supposing it did, what would be the effect on the copyright wars? (16 January 2007)

Measuring the Difficulty of Distance-Based Indexing

Resources and links on my paper Measuring the Difficulty of Distance-Based Indexing, which appeared in SPIRE'05. (3 November 2005)

Colour, social beings, and undecidability

Okay, it's been about two months since I posted my piece about colourful bits, and I really should have posted a follow-up before now, but better late than never.  First of all, here are ten other places that carried the story, in no particular order: (9 August 2004)

What Colour are your bits?

There's a classic adventure game called Paranoia which is set in an extremely repressive Utopian futuristic world run by The Computer, who is Your Friend.  Looking at a recent LawMeme posting and related discussion, it occurred to me that the concept of colour-coded security clearances in Paranoia provides a good metaphor for a lot of copyright and intellectual freedom issues, and it may illuminate why we sometimes have difficulty communicating and understanding the ideologies in these areas. (10 June 2004)

A Limited-Diffusion Algorithm for Blind Substring Search

Resources and links on my paper A Limited-Diffusion Algorithm for Blind Substring Search, from CITSS'98; Best Student Paper award winner. (1 June 1998)