VC-dimension?

Do you know anything about computing VC-dimension? Or about the Sauer-Shelah lemma?

Both Wikipedia and the CC blog state the lemma in a way that I do not understand. Namely, they define the VC-dimension as, at some point, determined by the cardinality of the intersection of the set {x₁,…,x_k} with some other set. And both sources upper bound this number by 2^k, which seems absurd: how can it possibly be more than k? We have indexed the set; it has exactly k elements; set intersection is a strictly nonincreasing function in terms of set size.

It also seems unlikely to me that both these sources would have typos. So I must be misunderstanding something.

If you know something about VC-dimension, the Sauer-Shelah lemma, or related combinatorics, please send me an email and I shall grill you with my questions (seasoned with confusion... and paprika, if you like).

Update: I figured it out with the help of these lecture notes. It was an issue of misunderstood notation. (My bad, as usual.)


This post's theme word: curtilage, "an area of land encompassing a dwelling and its surrounding yard, considered as enclosed whether fenced or not." In my present frame of mind, it relates to set theory.

Medieval Times

We sallied forth to Medieval Times this evening, and were duly apportioned to quaff our meals whilst championing the blue knight (Don Alberto del Mau).

Later in the evening, he was hit with a sword to the gut. Yowch. This must have hurt less than his overly expressive body language suggested, since a mere 10 minutes later, he was up on his horse again and waving his blue flag.

V. took photos of the fracas.

This post's theme word: mortmain, "the often stifling influence of the past on the present and the living," or "the perpetual ownership of property by institutions such as churches."

Building Turing machines

Two recent items of internews (internet+news = stories that are popular for a few hours) regarding Turing machines, my second-favorite type of machine.*

Massive in-game Turing machine built inside a mechanical game (via BoingBoing).

Actual real-life Turing machine built inside this universe (via BoingBoing, HackADay, Slashdot, Gizmodo).


This post's theme word: sedulous, "involving great care, effort, and persistence." Any Turing machine construction, whether engineering or mathematical, is of necessity quite sedulous.

*Printing presses. Nothing can beat 'em.

Taxes

I'm working on my Canadian taxes (I have an automatic extension on my US taxes, so I'll do them second).

I was amused by this sarcastic art commentary (NYTimes) on tax forms and the idea of "self-employment." Or whatever it's a commentary on. I like the redesign, anyway. And I love the footnote.


This post's theme word: quango, "a semipublic administrative body outside the civil service but with financial support from and senior appointments made by the government," originally from QUasi-Autonomous Non-Governmental Organization.

A. is my hero

We recently had lease negotiations with the landlord. I noticed that he was paying more heed to A.'s comments than to my own... even though we had agreed beforehand on what to say and were reading from the same set of notes. It was apparently subtle; A. did not notice. Nonetheless, in the interests of optimally negotiating, I let A. do most of the talking.

This turned out quite well.

For use of his testicle-granted Man Voice in negotiations with the landlord, A. is hereby awarded a Zinc Star of Honor.


This post's theme word: novation, "the replacing of an obligation, a contract, or a party to an agreement with a new one."

Happy e day!

Happy e day!

Remember pi day, back on March 14 (3.14)? Well, allowing for some creative calendrical interpretation, today is e day, the 71st day of February (2.71). I suppose that if you were to round instead of truncating, e day would properly be tomorrow, the 72nd day of February.

"But it's April!" you protest.

That is true. However, it snowed last week. It still feels like February psychically. Why should we discriminate in favor of the small elite of constants with fewer than 32 hundredths?* You constant bigot.

"What should be done to celebrate?" you query.

I don't know of any e-themed foods, games, or ceremonies. So please, just take a moment today (or tomorrow, if you are a rounder) and think of how lovely e is. For some light introductory reading, here's the Wikipedia article and many ways to represent e.

*For that matter, why do we limit ourselves to celebrating constants <13, based on our 12-month calendar?


This post's featured comic comes from Three Panel Soul:

Clash of the Titans

I watched Clash of the Titans, against my better judgement.

Oh, it was wretched. They took Greek mythology -- no, just some assorted stories -- no, just the approximate names of some people in assorted stories loosely related to Greek mythology. I haven't seen the first movie (of which this is a remake), but the only justification for this abomination of a film is that the first movie was actually just residual scarring left on film strips by cosmic radiation. The story goes nowhere and everywhere, grabbing bits and pieces I recognized from other thrilling summer blockbusters (a kraken? battling giant CG beasts in the desert?) and amalgamating them in one enormous, mind-meltingly-terrible transgression against the very concept of "plot."

Don't see this movie.


This post's theme word: bowdlerize, "to remove or change parts (of a book, play, movie, etc.) considered objectionable." As in, "Lila's bowdlerized Clash of the Titans was 10 seconds long and consisted entirely of shots of the ocean."

Hugo nominees 2010

Yet again I attempt to read and consider (and maybe blog some thoughts about) the Hugo nominees. This year's another doozie of a great-looking list.

Best novel:

• Boneshaker, Cherie Priest
• The City & The City, China Miéville
• Julian Comstock: A Story of 22nd-Century America, Robert Charles Wilson
• Palimpsest, Catherynne M. Valente
• Wake, Robert J. Sawyer
• The Windup Girl, Paolo Bacigalupi

Best novella:

• “Act One”, Nancy Kress
• The God Engines, John Scalzi
• “Palimpsest”, Charles Stross
• Shambling Towards Hiroshima, James Morrow
• “Vishnu at the Cat Circus”, Ian McDonald
• The Women of Nell Gwynne’s, Kage Baker

Best novelette:

• “Eros, Philia, Agape”, Rachel Swirsky
• The Island”, Peter Watts
• “It Takes Two”, Nicola Griffith
• “One of Our Bastards is Missing”, Paul Cornell
• “Overtime”, Charles Stross
• “Sinner, Baker, Fabulist, Priest; Red Mask, Black Mask, Gentleman, Beast”, Eugie Foster

Best short story:

• “The Bride of Frankenstein”, Mike Resnick
• “Bridesicle”, Will McIntosh
• “The Moment”, Lawrence M. Schoen
• “Non-Zero Probabilities”, N.K. Jemisin
• “Spar”, Kij Johnson

This post's theme word is losel, "one that is worthless." I hope this list contains no losels... though it will probably contain losers, unless there is an n-way tie in every category.

Spam spam spam!

I just got my first spam in maybe 6 months. How interesting! I couldn't find anything particularly strange about it to indicate how it had snuck through my several filters.


This post's theme word: wildcatter, "one who drills for oil speculatively," or "one who promotes an unsafe or fraudulent enterprise," or "a worker who takes part in a wildcat strike: a sudden strike not authorized by the labor union. "

Bureaucracy sucks

Bureaucracy sucks, and yet we give it much power over us. That is all. I got jerked around this week by some terrible bureaucracy.


This post's theme word: barratry, "The practice of stirring up of groundless lawsuits," or "an unlawful act by a ship's master or crew that harms the owner of the ship," or "the buying or selling of positions in church or state."