Theory, meet Practice

Introduction to Algorithms, Cormen et al. (first edition, 1990, page 229-230):

If a malicious adversary chooses the keys to be hashed, then he can choose n keys that all hash to the same slot, yielding and average retrieval time of Θ(n). Any fixed hash function is vulnerable to this sort of worst-case behavior; the only effective way to improve the situation is to choose the hash function randomly in a way that is independent of the keys that are actually going to be stored. This approach, called universal hashing, yields good performance on the average, no matter what keys are chosen by the adversary.

ArsTechnica: Huge portions of the Web vulnerable to hashing denial-of-service attack:

Researchers have shown how a flaw that is common to most popular Web programming languages can be used to launch denial-of-service attacks by exploiting hash tables. Announced publicly on Wednesday at the Chaos Communication Congress event in Germany, the flaw affects a long list of technologies, including PHP, ASP.NET, Java, Python, Ruby, Apache Tomcat, Apache Geronimo, Jetty, and Glassfish, as well as Google's open source JavaScript engine V8. The vendors and developers behind these technologies are working to close the vulnerability, with Microsoft warning of "imminent public release of exploit code" for what is known as a hash collision attack.

Researchers Alexander Klink and Julian Wälde explained that the theory behind such attacks has been known since at least 2003, when it was described in a paper for the Usenix security conference, and influenced the developers of Perl and CRuby to "change their hash functions to include randomization."

But Klink and Wälde showed that "PHP 5, Java, ASP.NET as well as V8 are fully vulnerable to this issue and PHP 4, Python and Ruby are partially vulnerable, depending on version or whether the server running the code is a 32-bit or 64-bit machine."

"This attack is mostly independent of the underlying Web application and just relies on a common fact of how Web application servers typically work," the team wrote, noting that such attacks would force Web application servers "to use 99% of CPU for several minutes to hours for a single HTTP request."

"Hash tables are a commonly used data structure in most programming languages," they explained. "Web application servers or platforms commonly parse attacker-controlled POST form data into hash tables automatically, so that they can be accessed by application developers. If the language does not provide a randomized hash function or the application server does not recognize attacks using multi-collisions, an attacker can degenerate the hash table by sending lots of colliding keys. The algorithmic complexity of inserting n elements into the table then goes to O(n**2), making it possible to exhaust hours of CPU time using a single HTTP request."

Funny. I was just reading Introduction to Algorithms the other day and and read about this problem, then came across the second link just now on JWZ's blog.

The Chairs Are Where the People Go

Last year, a friend suggested I read Misha Glouberman's book The Chairs Are Where The People Go. Glouberman organizes events in Toronto and my friend said he thought I would enjoy it based on my experiences with minne✱.

Glouberman is one of those people you want in your city. He spends his time organizing classes and events that give people something interesting to do, at much personal financial cost (he was a computer programmer).

The book is rather unusual. It is a series of essays as dictated to and edited by his friend Sheila Heti. A short series of essays by an artist in Toronto doesn't seem promising as a book of widespread interest, and I did find many of the essays uninteresting. Glouberman's interests and mine are pretty different, so when he talks specifically about what makes a good charades class or experimental music experience, that can be a slog. But there are some real gems as well. He has a lot to say about what makes a city work, and his experience organizing good events shines through.

Below are a few of my favorite bits.

2. How to Make Friends in a New City

[A]dult life isn't like that. You may move to a new city, maybe for a job that doesn't easily put you into contact with a lot of people with whom you have much in common. So what that means is that it's work, and maybe for the first time in your life you have to actually take making friends on as a project.

7. The Chairs are Where the People Go

This is a key lesson for event organizers. This is why we split MinneDemo into two separate areas: one for listening, and one for talking. If you don't do something to prevent people from talking over the presenter, your event is going to suck.

There's a thoughtlessness in how people consider their audience that's reflected in how they set up chairs. You can see that thoughtlessness immediately....

Leaving space for people to stand in the back at a reading is ridiculous. Who wants to stand through a reading? You're pretty much intentionally designing things so that a lot of people will find the reading boring, because it's incredibly hard to not be bored when you're watching someone read from far away and you're standing. Those people at the back will talk to each other. So not only will they have a bad time, but their bad time will make it worse for everyone else.

30. Seeing my Friends Drunk for the First Time

This is an interesting observation: bars are in the boredom business, because it sells drinks.

When I first started my games night, something I thought was, So many of the things that happen in bars are such boring experiences, and I figured a games night would be a way to give people a more engaging exprience in bars....

What I didn't understand at the time was that a lot of things I viewed as problems were actually part of the business model....[W]hen you go to see a band, it usually starts later than it's scheduled to, and there's more time between sets than you feel you need, and it's boring. But all the boredom sells drinks.

In the same essay he argues that drinking simply increases your tolerance for boring situations:

It's not that you becoming interesting and fun when you're drunk, it's that your perception of interesting and fun is lowered to such a moronic level.

44. These Projects Don't Make Money

This essay resonated with me because how much money minne✱ costs to run, and how often Ben and I would end on the hook for the overruns in the early days. Renting space and buying food and drinks for hundreds of people is expensive. This year, we will be publishing an annual report for the first time, which will show people how the finances work.

It's really obvious to some people and not at all obvious to other people that the projects I run don't make any money at all. When people with real jobs read something about an art exhibition in a newspaper, or see a band interviewed on TV or featured on the cover of a local weekly, it's natural for them to assume tha those people are making money. I mean, they're doing something that seems really successful. They're in the paper---you're not. So surely they must be making money.

For the past several years, I've hosted the Trampoline Hall lecture series. When Trampoline Hall was doing really well, a friend of Sheila and her then husband, Carl, came up to them soon after they bought a house and said, Wow, I guess the shows must be doing really well for you to be able to afford this house. At the time, the show really was something of a little phenomenon. But it was a little phenomenon that happened once a month before a crowd of eighty people and charged five dollars at the door. And he wasn't joking! It's hard for people sometimes to understand that things that look successful or generate attention don't necessarily also generate money.

I feel it would be useful if the audience had a clearer understanding of what the economics really are. I always wanted to do a Trampoline Hall show about money, where part of the show would be to break down the budget of Trampoline Hall and explain to the audience how it came to be, and that we basically lost money doing this nominally successful show.

46. Asking a Good Question

[A] good question has to be a question. I warn them that if they take a statement and try to raise the pitch of their voices at the end of their sentences, we won't be tricked. I tell the audience that grammarians will agree that there's no such thing as a two-part question, what they really have are two questions, and that they should just pick the better of the two.

I say that one way to tell if your question is any good is to look inside yourself. I ask the audience to pay attention to what feelings they have when they feel a question coming on. It may seem obvious, but curiosity is a good feeling to have....

What I warn people against is feelings of pride.

51. Conferences Should Be an Exhilarating Experience

This is a longer essay about unconferences, which I enjoyed because I help organize one (albeit less "un" than most unconferences, but also about 10 times bigger). However, the most striking part is this simple rule for group conversation:

For the discussion part of the conference, I usually don't give too much instruction, but I have one tip that I'll give people. It's my "one over n" rule of conversation. What I tell people is: If you're in a group of five people, the natural amount of time for you to be talking is about a fifth of the time.

55. Making the City More Fun for You and Your Privileged Friends Isn't a Super-Noble Political Goal

There are a lot of people out there who advocate a specific kind of civic improvement....[T]here's a cluster of causes that go together: less corporate advertising; more cycling and walking and less car use; outdoor events and street parties and bringing art to public places. There's a lot about this work that's genuinely laudable, but what the city will end up looking like if such people achieve their goals is one that's uniquely and specifically well suited to people who are young and well educated and able-bodied, with a fair amount of free time, who are interested in culture and parties and living in a dense downtown core. In other words, people just like themselves.

57. Impostor Syndrome

One possibility I think people often overlook is that there might be people who feel this way because they are impostors. There actually are people who hold impressive jobs or high positions who don't merit them.

It's normal for us to feel insecure about our own real abilities or accomplishments, but it's also the case that we're kind of encouraged to lie about our abilities and successes. There is so much pressure on people to achieve, to become ever more accomplished and impressive, and that goes along with this encouragement to be a kind of salesman of yourself in a certain way. So what ends up happening is that a lot of people really are presenting a version of themselves that is false. In this case, the reason they have this unpleasant feeling of being an impostor is because they are one.

68. Social Capital

A lot of people I know who work in the arts think they're poor. And it's true that some of them might not have much money, but the idea that they are somehow "the poor" is, I think, and idea too ridiculous to even merit serious discussion.

Steve Yegge: The Interviewing Anti-Loop

A classic example found everywhere is: Interviewer A always asks about C++ trivia, filesystems, network protocols and discrete math. Interviewer B always asks about Java trivia, design patterns, unit testing, web frameworks, and software project management. For any given candidate with both A and B on the interview loop, A and B are likely to give very different votes. A and B would probably not even hire each other, given a chance, but they both happened to go through interviewer C, who asked them both about data structures, unix utilities, and processes versus threads, and A and B both happened to squeak by.

That's almost always what happens when you get an offer from a tech company. You just happened to squeak by. Because of the inherently flawed nature of the interviewing process, it's highly likely that someone on the loop will be unimpressed with you, even if you are Alan Turing. Especially if you're Alan Turing, in fact, since it means you obviously don't know C++.

Fargo of the mind

Curious how a place unvisited can take such hold on the mind so that the very name sets up a ringing. To me, one such place was Fargo, North Dakota. Perhaps its first impact is in the name Wells-Fargo, but my interest certainly goes beyond that. If you will take a map of the United States and fold it in the middle, eastern edge against western, and crease it sharply, right in the crease will be Fargo. On double-page maps sometimes Fargo gets lost in the binding. That may not be a very scientific method for finding the east-west middle of the country, but it will do. But beyond this, Fargo to me is brother to the fabulous places of the earth, kin to those magically remote spots mentioned by Herodotus and Marco Polo and Mandeville. From my earliest memory, if it was a cold day, Fargo was the coldest place on the continent. If heat was the subject, then at that time the papers listed Fargo as hotter than any place else, or wetter, or drier, or deeper in snow.

— John Steinbeck, Travels with Charley

Uncloaking a Slumlord Conspiracy with Social Network Analysis

This is a fascinating case study of using social network analysis to uncover a conspiracy to "strip mine" equity out of an apartment building without fixing housing violations. It reminds me of the Barksdale gang's money laundering conspiracy in The Wire.

Via Hacker News.

Favorite Books of 2011

Yesterday, I posted my list of books read in 2011. What follows are a few of my favorites.

The Emperor of all Maladies, Siddharta Mukherjee

This book was recommended on Hacker News after Steve Jobs's death. I was not eager to read a book about cancer because my dad died of it, but I knew I should learn more about it. The book is fascinating and horrifying, and ultimately, hopeful. Medicine is finally beginning to understand certain cancers. "Curing" cancer will probably never be possible by treating it, but rather preventing it and delaying it until old age, and we are also making strides there.

59 Seconds: Think a Little, Change a Lot, Richard Wiseman

I read a blog post by a guy who read 340 self-help books ("Because I am insane" was his reasoning; I can't say I disagree.). His conclusion was that 95% of all self-help books were crap, but he recommended 59 Seconds because it covered a wide range of topics, was written by a skeptic who quotes scientific literature instead of personal opinions, and was short and to the point.

I can't argue with someone who's read 340 self-help books, so I checked out 59 Seconds. Much of the research will be familiar to those who have done some reading about Positive Psychology, but Richard Wiseman does a great job of distilling it down into bite-sized chunks and providing actionable tips. Also, I loved his sense of humor -- the book is hilarious.

Missile Gap, Charles Stross

Perhaps one of the most depressing novellas I've ever read. You can read it online at Subterranean Press

The Milagro Beanfield War, John Nichols

My dad gave me this book about 15 years ago. It was always one of those books that you have lying around to read "someday". This year, Jenny and I went on a vacation to New Mexico, so I finally got around to reading it. It is said that there is a right time in one's life to read certain books. This was a perfect time for me to read this book, and I loved it. My only regret was I will not be able to discuss it with my dad. He spent time in New Mexico, so I assume he wanted me to read it due to that connection, but I'll never know for sure.

Undaunted Courage: Meriwether Lewis, Thomas Jefferson, and the Opening of the American West, Stephen Ambrose

I got this a a Friends of the Library sale for, like, $1. In school, I learned about Lewis and Clark (I lived in North Dakota, where it's basically the state's only claim to fame, so "Lewis and Clark" is on everything), but reading about their arduous journey was eye-opening. It's truly an amazing story of preservernce, and you learn how unfortunate it is that Lewis and Clark's scientific contributions were ignored for so long, due to the delay in publishing their journals. I also enjoyed this book because of Thomas Jefferson, and his connection with the federalist/anti-federalist debates at the turn of the nineteenth century, which I read about in American Aurora in 2010.

The Master and Margarita, Mikhail Bulgakov

"Manuscripts don't burn." I have trouble putting into words why I loved this novel so much. It has biting satire, humor, sadness, and amazing writing. I read it during our trip to Paris, which I thought was appropriate considering the long-standing cultural ties between France and Russia. I read Mirra Ginsburg's translation, which is apparently based on the censored version published in the 1960s, so I may have to revisit this novel with another translation.

(OK, I didn't read the version with the cover above -- I just think it looks super cool.)

Plagues and Peoples, William H. McNeill

I love history books. They can roughly be divided into "great sweep of history" and "great men" (yes, usually men) categories. I tend to favor sweep of history books, and this is one of the most interesting of that type I have read. McNeill shows how diseases have shaped human history.

Why we don't hire programmers based on puzzles, API quizzes, math riddles, or other parlor tricks

David Heinemeier Hansson provides some help for you in responding to his post about hiring programmers:

(If you need help posting a comment, feel free to use any of these samples: “You make todo lists, you don’t need real software engineers”, “Math is actually really important, you know!”, “Google is worth one gajillion dollars and they use quizzes, so there!”)

2011 Books

I read 49 books in 2011, up from 35 last year. I credit spending more time travelling and reading shorter books. The high number of Poul Anderson books is partly from going through my father-in-law's stash of trashy old SF books.

Under the Black Flag: the Romance and the Reality of Life Among the Pirates, David Cordingly

A Fire Upon the Deep, Vernor Vinge

Brain Wave, Poul Anderson

Missile Gap, Charles Stross

Soon I Will Be Invincible, Austin Grossman

A Deepness in the Sky, Vernor Vinge

The Windup Girl, Paolo Bacigalupi

The Atrocity Archives, Charles Stross

Good Calories, Bad Calories: Challenging the Conventional Wisdom on Diet, Weight Control, adn Disease, Gary Taubes

House of Suns, Alastair Reynolds

War Before Civilization: the Myth of the Peaceful Savage, Lawrence H. Kelley

Priceless: the Myth of Fair Value (and How to Take Advantage of It), William Poundstone

Skinwalkers, Tony Hillerman

The Milagro Beanfield War, John Nichols

Heavy Time, C.J. Cherryh

Hellburner, C.J. Cherryh

Undaunted Courage: Meriwether Lewis, Thomas Jefferson, and the Opening of the American West, Stephen E. Ambrose

Pushing Ice, Alastair Reynolds

"...and their memory was a bitter tree...": Queen of the Black Coast and Others, Robert E. Howard

The Peace War, Vernor Vinge

The Half-Made World, Felix Gilman

The Witling, Vernor Vinge

The Big Time, Friz Leiber

Gateway, Frederik Pohl

Flandry of Terra, Poul Anderson

Ensign Flandry, Poul Anderson

The Yiddish Policeman's Union, Michael Chabon

Agent of the Terran Empire, Poul Anderson

True Grit, Charles Portis

The Master and Margarita, Mikhail Bulgakov

Plagues and Peoples, William H. McNeill

Is Paris Burning, Larry Collins and Dominique Lapierre

One of Ours, Willa Cather

The Broken Sword, Poul Anderson

Altered Carbon, Richard K. organ

The Snow Queen, Joan D. Vinge

Where Late the Sweet Birds Sang, Kate Wilhelm

Lost in Shangri-La: A True Story of Survival, Adventure, and the Most Incredible Rescue Mission of World War II, Mitchell Zuckoff

The Fortune Cookie Chronicles: Adventures in the World of Chinese Food, Jennifer 8. Lee

Broken Angels, Richard K. Morgan

Woken Furies, Richard K. Morgan

Steal Across the Sky, Nancy Kress

Imperium, Robert Harris

The Summer Queen, Joan D. Vinge

Consider Phlebas, Iain M. Banks

Cannery Row, John Steinbeck

Accelerando, Charles Stross

The Emperor of All Maladies: a Biography of Cancer, Siddhartha Mukherjee

59 Seconds: Think a Little, Change a Lot, Richard Wiseman

Iowa Nice

Our comrades to the South have a message for you:

Incubators are a ghetto

Andrew Clay Shafer:

There has been an explosion of incubators in the last few years. Most of them suck. Some suck so bad that the net value created by the program is probably negative. I’m not going to name names. This is just about results.

Let’s start with a story. There are minor variations, but I’ve seen it played out in real time more than once in the last few years. The story goes like this. An incubator has a class of companies, they give them a little cash, they have a weekly session with a mentor or whatever, time goes by, demo day, no one gets funding, fail, fail, FAIL.

what’s wrong

They tried to copy the Y Combinator model, and by ‘copy’ I mean cargo cult. They performed the outwardly obvious ceremony, but didn’t understand and thus couldn’t replicate the mechanics of cause and effect.

Y Combinator has had impact on the dynamics of startup formation and funding not because of the exact details of a program. But the details are what cargo culters can see: three months, a dollar figure, weekly sessions, gogogo, demo day… the end , most of the companies dissipate.

To be successful an incubator has to do two things. First, create companies that are actually fundable, second, get them an audience with investors interested and able to fund. That’s it. That’s all. Connect the dots. Success.

See also Jed Christianson's Copying Y Combinator - WHY and HOW and Looking back - 1.5 years since "Copying Y Combinator". In the latter, he opines:

I am still absolutely convinced that if you’re a Y Combinator clone, just located in a different city, you will never be a top-tier program. Why? Because if you’re just doing exactly what YC does, but you provide less money and less expertise, you’ll never have the top startups wanting to work with you.

I think this is absolutely true. If you want to compete with Y Combinator, it's going to be tough, and you need to do something different.