kloover.com

The RIT Athenaeum has just published a short article describing Video CAPTCHAs. You can find it in print around the RIT campus and online here: http://www.rit.edu/news/?n=47112

This week (July 15th - July 17th), Richard Zanibbi and I are attending SOUPS ‘09 in Mountain View, CA. It’s a smaller conference that’s gotten great reviews and has had some excellent CAPTCHA-related work presented in the past. On Friday morning, I’ll be presenting a paper titled Balancing Usability and Security in a Video CAPTCHA. A reporter from ZDNet.co.uk has already written a short article about it which you can find here.

Paper

The paper can be downloaded here and the slides can be downloaded here. It’s also available at the ACM Digital Library.

Bibtex Entry

@inproceedings{kak-soups09,
	Title = {Balancing Usability and Security in a Video CAPTCHA},
	Author = {Kurt Alfred Kluever and Richard Zanibbi},
	Booktitle = {Proceedings of the 5th Symposium On Usable Privacy and Security 2009},
	Address = {Mountain View, CA, USA},
	Month = {July},
	Year = {2009}
}

Richard Zanibbi and I will be presenting Balancing Usability and Security in a Video CAPTCHA at SOUPS ‘09 this summer. SOUPS is conveniently being held on Google’s Mountain View campus, so I’ll be out there for the week visiting friends, enjoying the sun, working, and attending the conference. Once our camera-ready version is finished, I’ll post a full copy of the paper here and also on my new Google Research page.

Here’s some quick info about SOUPS:

The fifth Symposium on Usable Privacy and Security (SOUPS) will be held July 15-17, 2009 at Google in Mountain View, CA. This symposium will bring together an interdisciplinary group of researchers and practitioners in human computer interaction, security, and privacy. The program features technical papers, workshops and tutorials, a poster session, panels and invited talks, and discussion sessions. SOUPS 2009 will be held in cooperation with ACM SIGCHI.

For fun, I calculated my Erdős number tonight (using the AMS Collaboration Distance Calculator).  Your Erdős number represents the number of hops between you and the famous Hungarian mathematician Paul Erdős (where a link is established between two authors when they have collaborated on an academic paper together).  It was created as a joke to approximate your importance in the mathematical community. Erdős was assigned a number of 0.  Each of Erdős’ collaborators were assigned a number of 1, their collaborators were assigned a number of 2, and so forth.  The shortest path I could find between Erdős and myself was of length 5:

1. Paul Erdős and Paul C. Kainen
2. Paul C. Kainen and Vladik Ya. Kreinovich
3. Vladik Ya. Kreinovich and Hung Trung Nguyen
4. Hung Trung Nguyen and Leonid K. Reznik
5. Leonid K. Reznik and Kurt Alfred Kluever (via IEEE Sensors 2007)
   

I also found a couple of length 6 paths with interesting researchers (bolded below) in them:

1. Paul Erdős and Dieter Kratsch
2. Dieter Kratsch and Jitender S. Deogun
3. Jitender S. Deogun and Shashank K. Mehta
4. Shashank K. Mehta and George Nagy
5. George Nagy and Richard Zanibbi
6. Richard Zanibbi and Kurt Alfred Kluever (via IEEE WNYIP 2008)
   

1. Paul Erdős and Andrew M. Odlyzko
2. Andrew M. Odlyzko and Colin L. Mallows
3. Colin L. Mallows and Henry S. Baird
4. Henry S. Baird and Dorothea Blostein
5. Dorothea Blostein and Richard Zanibbi
6. Richard Zanibbi and Kurt Alfred Kluever (via IEEE WNYIP 2008)

An interesting article here states that “the median Erdős number is 5; the mean is 4.65, and the standard deviation is 1.21.”

Here are some great links for more reading about this topic:

• http://web.aanet.com.au/image/erdos/
• http://www.oakland.edu/enp/index.html
• http://www.oakland.edu/enp/trivia.html
• http://en.wikipedia.org/wiki/Erd%C5%91s_number

I was asked the following question: Design a data structure that supports 2 operations:

• insert(element, weight)
• sample()

When you insert an element into the data structure, you specify a weight. This weight divided by the total of the other weights in the data structure, is the probability that the item is returned when sample() is invoked. You should design your data structure with both speed and space in mind.

Here is a good solution. The insert() operation requires O(1) constant amortized time and the sample() operation requires O(lg n) time due to binary search. The space requirements is O(n) as well.

public final class BinarySearchWeightedSampler<E> {
  private final List<E> elements;
  private final List<Double> weights;

  public BinarySearchWeightedSampler() {
    this.elements = new ArrayList<E>();
    this.weights = new ArrayList<Double>();
  }

  public void insert(E element, double weight) {
      elements.add(element);
      if (weights.isEmpty()) weights.add(weight);
      else weights.add(weight + weights.get(weights.size() - 1));
  }

  public E sample() {
    return elements.get(
        binarySearch(Math.random(), 0, weights.size() - 1,
                     weights.get(weights.size() - 1)));
  }

  private int binarySearch(double val, int low, int high,
      double totalWeight) {
    if (high < low) return low;
    int mid = low + ((high - low) / 2);
    int midValue = weights.get(mid) / totalWeight;
    if (midValue > val)
      return binarySearch(val, low, mid - 1, totalWeight);
    else if (midValue < val)
      return binarySearch(val, mid + 1, high, totalWeight);
    else
      return mid;
  }
}

If we ignore the space requirements and assume the weights have finite precision (I chose integers for clarity, but any finite precision number can be made to work), we can sample in O(1) constant time:

public final class DiscreteWeightedSampler<E> {
  private final List<E> elements;

  public DiscreteWeightedSampler() {
    this.elements = new ArrayList<E>();
  }

  public void insert(E element, int weight) {
    for (int i = 0; i < weight; ++i) {
      elements.add(element);
    }
  }

  public E sample() {
    return elements.get((int) (Math.random() * elements.size()));
  }
}

You knew you were headed for a career in Computer Science when…
I witnessed the thrill and the excitement of the dot com boom in the late 90’s.

What is your favorite class and why?
Theory of Computer Algorithms. This course is the first formal, in-depth course on algorithms, complexity, and data structures. These three components are the foundations of Computer Science and I highly recommend that everyone take this course (although it is a very difficult course).

One piece of advice I have for 1^st year students is…
Establish a relationship with your professors by asking questions in class and utilizing office hours when you are confused.

If you could have dinner with a famous computer scientist, living or dead, who would you choose?
Luis von Ahn. His work on CAPTCHAs and human computation has inspired me to pursue it as my thesis topic.

What is the most interesting project you have worked on, either in a course or on the job?
The most interesting project I’ve worked on has been my thesis. Reading all of the existing research has helped me develop a brand new idea that nobody else in the world has worked on.

Where do you see yourself in ten years?
Hopefully back in school earning my PhD in Computer Science.

Original post: http://www.cs.rit.edu/about/profiles/Kurt_Kluever
PDF version: http://www.cs.rit.edu/five_minutes/pdf/Kurt_Kluever.pdf

Also check out 5 Minutes with Richard Zanibbi (my thesis advisor) and 5 Minutes with Brian Renzenbrink (a good friend).

On January 28th, 2009, my thesis advisor (Richard Zanibbi) presented a talk on Video CAPTCHAs at the RIT Center for Imaging Science. An abstract of the talk can be download here. A video of his talk (with slides) can be watched here using Adobe Acrobat Connect.

My thesis is now available in a bounded hard-copy at the RIT library on the 3rd floor (Call No. Q341 .K58 2008) and online through the RIT Digital Media Library.

Since beginning my new job as a Software Engineer in Test for Google at their Manhattan office, a lot has changed in my life. Here’s a quick rundown:

My Job (Google)

My job is going great. I really love the work environment and people at Google. Everyone is willing to take time out of their day to help you with whatever you need…which is good because the project I’m working on has a very high learning curve. It uses a ton of Google-centric infastructure pieces that all work together in a very specific way. Since I’ve had no exposure to these technologies before, work has been going a little slow (lots of reading of other’s code and documentation, not a lot of coding). It’s a bit frustrating because it’s hard to measure productivity when most of your time is spent inputting knowledge (into your own brain), not outputting knowledge (to others). However, this means I’m learning something new every day (which is exciting). I’ll also excited to report that I’ll be continuing my work on Video CAPTCHAs at Google :)

My City (Hoboken)

There are tons and tons of young professionals everywhere. According to Wikipedia, the median age here is only 30 (as a comparison, the median age in the US is 35.3). While that doesn’t seem like a big difference, you’ll quickly notice it walking around the streets. The city of Hoboken itself is actually a lot of fun. Since the young population drives the local businesses, there are tons of bars, restaurants, and coffee shops in downtown Hoboken. In fact, no matter what day it is, the streets and bars are always full of people.

My Commute (Walk, PATH Train, Walk)

Nearly everyone here takes the PATH train into NYC for work. The PATH train is a bargain: for $1.30 (if you buy in bulk), you can get to midtown Manhattan in under 15 minutes. My train (from Hoboken to 14th Street) makes 2 stops along the way (at Christopher St and 9th St) and still only takes 11 minutes. That’s a faster commute than it would be even if I lived in most places in Manhattan. The only bad part of my commute is getting to the PATH station in Hoboken. It’s a mile walk from my apartment which isn’t bad now, but once the bad weather hits it’s going to be brutal. I’m going to try to get my bike down here to speed up the commute though. Once I get to 14th St, I have another half a mile or so walk to Google. Others have recommended that I take the L subway, but I’d rather save the $2 each way and walk the two blocks. Overall, my commute into the city costs me $1.30, a few hundred calories, and about 40 minutes of my time.

My Car (A Sad S4)

One of the main reasons that I decided on the apartment that I’m in is that it came with a free garaged parking spot my for S4. However, I’ve quickly realized that having a car down here is rather pointless. I’ve only used it two times since moving down here: 1) buying furniture on move in day 2) returning an air mattress to BJs. Other than that, it sits in the garage and looks at me in anger: it wants to be driven. Next weekend I’ll be driving up to Rochester to present at the IEEE WNYIP 2008 workshop…that’ll cheer my car up :) Also, gas is really cheap (comparatively) down here: $3.30/gallon for regular.

My Eating (An Empty Fridge)

I do all my weekday eating at Google: breakfast (sometimes), lunch (always), and dinner (except on Fridays). Because of this, I have very little (read: no) food in my fridge. In fact, all I have at my apartment is 3 mini-bags of popcorn and some soda. On the weekends, I go out to eat. There’s no sense in going grocery shopping for the weekend only. I’m sure at some point I’ll stock my cabinets with non-perishables like soup, etc. Also I should note that I may end up dying of mercury poisoning due to the amount of fish I’m eating at Google every day.

On September 26th, 2008 I will be presenting some of my work on Video CAPTCHAs at the IEEE Western New York Image Processing Workshop 2008 in Rochester, NY. The workshop will be held in the Imaging Science building at RIT (registration details can be found at the above link). The paper is in the form of a 4 page “extended abstract” and can be downloaded below.

Paper

The paper can be downloaded here or from the RIT Digital Media Library.

Bibtex Entry

@inproceedings{videoCAPTCHAsUsabilityVsSecurity,
	Title = {Video CAPTCHAs: Usability vs. Security},
	Author = {Kurt Alfred Kluever and Richard Zanibbi},
	Booktitle = {Proceedings of the IEEE Western New York Image Processing Workshop 2008},
	Address = {Rochester, NY, USA},
	Month = {September},
	Year = {2008}
}