Via Lifehacker, I learned about Furoshiki, a traditional Japanese cloth wrapping. You’re less likely to get paper cuts than with origami, but you still get the fun schematic diagrams.
Apparently the Japanese Environment minister (they have an environment minister? Is that essentially the Dept. of the Interior?) wants to promote the use of them. Although you can buy them from vendors, it’s the sort of thing that screams “DIY.”
Author Archives: Anand Sarwate
Berkeley EECS makes TA-ing more cushy
At the end of last semester I got a memo from our department trying to make TA-ing a more attractive prospect. In reality, a grad student in EECS is a TA here (or Graduate Student Instructor (GSI)) for one of three reasons : they’re a first-year and don’t have an advisor (yet), their advisor is low on funds or doesn’t have funds for their particular project, or they are fulfilling their teaching requirement to graduate (one semester only). The difference between being paid as a TA and as a research assistant (Grad Student Researcher (GSR)) is significant — the union negotiates the pay scale for GSIs, and the University is not going to let salaries rise if they can help it. In some instances a student’s advisor can bump up their salary to the GSR level. So now the department recommends:
- If you are doing research the same semester you’re teaching, your advisor should give you a partial GSR to help out.
- You can be appointing as a 100% GSR during winter break if you are around.
- If your advisor can’t afford to pay you and you are GSI-ing to fulfill the graduation requirement, then the department will give you a unconstrained fellowship.
All in all, it’s seems like a much more pleasant deal — how this will end up changing the dynamics of TAing is unclear though. It also makes things much much nicer in EECS than in other departments, which seems somehow unfair in the end. Why can’t all GSIs get better pay?
paper a day : The Byzantine Generals Problem
It’s more like “paper when I feel like it,” but whatever. This is a classic systems paper on decentralized agreement. Because the result is pretty general, I think there is something that could be done to connect it to information-theoretic studies of multi-way communication or maybe key agreement. That’s a bit hand-waving though.
The Byzantine Generals Problem
Leslie Lamport, Robert Shostak, and Marshall Pease
ACM Transactions on Programming Languages and Systems
Vol. 4 No. 3, July 1982, pp. 382–401.
The basic problem is pretty simple. There are n total generals, some of whom may be disloyal. A commanding general must send an order to n-1 lieutenant generals such that (a) all loyal lieutenants follow the same order and (b) if the commander is loyal then all loyal lieutenants follow the order sent by the commander. The paper looks a oral messages, which are unsigned messages such that a disloyal general can send any possible message, as well as signed messages. I’ll just talk about the former. A protocol for solving this problem is an algorithm for each general to execute, at the end of which all generals make a decision based on the information they have received.
The first result is that satisfying both conditions is impossible with m traitors unless n > 3m. This is easiest to see in the case of three generals, where you can go through all the cases. To extend it to general n the insight is that if n = 3m then m disloyal generals can collude to force indecision at m other generals. It’s kind of like having a devil on one shoulder and an angel on the other. If they are equally strong you will not be able to make the right choice. This result can be extended to show that approximate agreement (in a certain sense) is also impossible.
On the more side, for n > 3m there is a spreading/flooding algorithm that satisfies the conditions. The commander sends a message, and then each lieutenant general acts as the commander in a smaller instance of the algorithm to send the command to the remaining generals. This rebroadcasting protocol, while wasteful, guarantees that the loyal generals will all do the same thing. This algorithm can be extended to the case where the communication structure is a graph with certain “nice” structural properties.
To me, the interesting part really is the converse, since it says something about symmetrizing the distribution. The same phenomenon occurs in the arbitrarily varying channel, where the capacity is zero if a jammer can simulate a valid codeword. In this analogy, the encoder is one group of m generals, the decoder another group of m, and the jammer is a coalition of m disloyal generals.
There’s also a nice bit where they lay the smack down: “This argument may appear convincing, but we strongly advise the reader to be very suspicious of such nonrigorous reasoning. Although this result is indeed correct, we have seen equally plausible “proofs” of invalid results. We know of no area in computer science or mathematics in which informal reasoning is more likely to lead to errors than in the study of this type of algorithm.”
blogging to resume soon
In the meantime, here is a pictorial description of my mood.
Argonautika
I saw Argonautika with Alex on Thursday at the Berkeley Rep. It was quite the visual treat, but I expect no less from Mary Zimmerman. Alex, being Greek, was confused by the Latinization of some of the names (he thinks Pollux should have been Polydefkis or something), and upon further reflection it seemed the naming was inconsistent — Aphrodite, not Venus, but then Hercules, not Herakles. I’m sure others reading this had a similar reaction (Darcy, I’m looking at you).
In the end, however, I was a little unsatisfied by the play — perhaps because the tale is so familiar the tension went out of the storytelling. However, the strength of the play is in how Zimmerman tells the story and brings out parts of the story that resonate with contemporary society. The first act’s main event was Hylas’ death at the spring and Hercules’ madness at losing his lover. Zimmerman makes explicit their relationship and how Hercules really needs Hylas. One of the more powerful moments is Heracles breaking down and crying, holding the pitcher Hylas had before his death, and Hera’s gleeful reaction.
Another thing that Zimmerman did bring out was the way in which Medea’s betrayal of her family is coerced (by the gods and then by Jason, who knowingly takes advantage of her). She is a teenager, and her desire for Jason is like that of a high school crush or obsession. Jason, who is not left off the hook in modern stagings of Euripides’s play, is depicted in Argonautika as a bit more human than his demigod crew. After Eros shoots Medea with his arrow, she appears on stage pierced by it, her white dress becoming more and more blood-soaked in each scene. Her passion is a disease which slowly overwhelms her. This arresting visual image was almost enough to carry the whole play, but it didn’t show up until the second act.
One thing I thought about the next day was how Medea’s impulsive behavior at the beginning of this story and her killing of her own children at the end of the story could be used together as a commentary on our times — in Euripides the Greeks might argue that Jason is the tragic hero and Medea is merely the agent of his undoing, but since contemporary performance puts the focus back on her, we can also ask to what degree society (and by extension the gods) are implicated in her actions? There’s another play lurking in there, somewhere…
a note to Web of Science
Dear Web of Science,
When one is doing a citation search and actually looking at the papers that are turned up, having your search engine decide your session times out after 5 minutes is pretty inconvenient, especially since it means starting the whole search process over again each time. Saying “oh you can save a search” is pretty ridiculous too, since it requires your little cookies to infest my system.
Sincerely yours,
A Frustrated Graduate Student
tracks [End of Semester Survival Kit Edition]
This one’s for Liz, slogging her way through the semester’s end.
- Work Song (Oscar Brown, Jr.)
- Big River (Johnny Cash)
- Harem In Tuscany (Gogol Bordello)
- Turkish Mambo (Lennie Tristano)
- Temptation (Tom Waits)
- Just squeeze me (Ella Fitzgerald)
- History Repeating (Propellerheads feat. Shirley Bassey)
- Tank! (Yoko Kanno)
- This Year’s Kisses (Billie Holiday and Lester Young)
- Barbes-Brooklyn (Stephane Wrembel)
- I Am The Walrus (The Beatles)
- P.P. (Ornette Coleman)
- Alala (Cansei de Ser Sexy)
- North American Scum (LCD Soundsystem)
- Money, Money, Money (ABBA)
- D’yer Mak’er (Led Zeppelin)
- Love Potion Number 9 (The Searchers)
- The Dull Flame Of Desire (Bj:0uml;rk feat. Antony)
- Boys Don’t Cry (The Cure)
- Hallelujah, I Love Her So (Ray Charles)
tracks [Hell to Heaven and Places Between]
For Rhode’s birthday and quite late, for which I apologize.
- Everybody Smokes In Hell (Paul Kotheimer)
- Been To Hell (comp. Phil Kline, from texts by Vietnam vets)
- Devil’s Haircut (Beck)
- Between The Devil And The Deep Blue Sea (Ella Fitzgerald)
- Reckless Night on Board An Ocean Liner (Raymond Scott)
- On Peanuts Playground (Wynton & Ellis Marsalis)
- Me, Myself And I (Billie Holiday)
- Red Hill Mining Town (U2)
- Big Rock Candy Mountain (from the O Brother soundtrack)
- Young At Heart (Tom Waits)
- Fairytale Of New York (The Pogues)
- A Christmas Carol (comp. Charles Ives, perf. Jan Degaetani)
- Air (comp. J.S. Bach, perf. Yo-Yo Ma & Bobby McFerrin)
- Seven Steps to Heaven (perf. Cassandra Wilson)
- Knockin’ On Heaven’s Door (Bob Dylan)
- Seven Steps To Heaven (Miles Davis)
- Monkey Gone to Heaven (The Pixies)
Yes, “Seven Steps” is meant to be on there twice! I love that song…
Leopold… Leopold…
On KALX this morning I heard the audio from Long-Haired Hare. I think it says something about my upbringing that I could visualize the entire cartoon as I listened to the track, right down to the orchestra members whispering “Leopold!” when Bugs takes the podium to conduct. What a great way to start the day!
The link should work until someone wises up and removes the video:
George and the NIE : the argument from information theory
George makes the following argument: let X be a binary random variable that equals 1 if Iran has an active nuclear weapons program and 0 if not. Suppose that last month we knew that P(X = 1) = p > 1/2. Then we can measure our uncertainty about X via its entropy:
H(X) = hb(p) = – p log p – (1-p) log (1-p)
Here hb(p) is the binary entropy function. Now let Y be a random variable representing the NIE. We know that conditioning reduces entropy:
H(X | Y) ≤ H(X)
Let p’ be our new probability that X = 1 conditioned on the evidence Y. We cannot have p’ < p, because then hb(p’) > hb(p), which is a contradiction. Therefore p’ ≥ p and therefore the NIE shows that the chance Iran has an active nuclear program is even higher than before.
Exercise: Explain the error(s) in George’s argument.
Extra Credit: Write a short essay explaining why one should not abuse information theory for political ends.
An Ergodic Walk 