### February 2012

Because I needed more highly stylized 20th century Austrian art, I saw the performance of Pierrot Lunaire and The Soldier’s Tale at the Chicago Symphony last night — wow! Pierre Boulez had to bow out on the advice of his ophthalmologist, but Cristian Macelaru did a great job replacing him. Pierrot is one of my favorite pieces, and Kiera Duffy gave a stellar performance — the only thing that was missing for me was more embodiment of the character of Pierrot. This was clearly a choice, and maybe in a big performance space it wouldn’t work, but one thing that makes this piece pop in the chamber setting is the singer taking on the character of Pierrot, especially in the later movements, packing tobacco into the bald pate of Cassander, or rubbing the spot on moonlight on his black coat. The other element of the production was the projections on three screens behind the performers — rather abstracted visual compositions with the English translations moving and fading in and out in a distressed Courier. The affect reminded me a bit of those mid-episode breaks in “darker” anime shows like Lain. Perhaps a bit over the top?

The second half of the program was The Soldier’s Tale, featuring John Lithgow as the narrator, Kevin Gudahl as the devil, and Adam Van Wagoner, Demetrios Troy both playing the soldier, and Lindsey Marks as the princess. This was the best performance of this piece I have seen, even though I had an obstructed seat in the second balcony. The screens were put to good use here, helping demarcate the acts and providing some great moments for silhouettes, especially as the devil played the violin at the end.

I caught a production last night of They Are Dying Out by Peter Handke at the Trap Door Theatre in Chicago. I’ve read Kaspar and Offending The Audience but hadn’t heard of this play until I saw the review/notice in Chicago Theater Beat. It’s a dark absurdist piece, meditating on the moral emptiness of business. But rather than trying to get our sympathies, to feel for Hermann Quitt and his existential angst, Handke exposes the hypocrisy of the language used by corporate power to justify itself. The resulting performance is cerebral but stylish, effectively using the space and social Gestus to lay bare the positions and relationships of the characters. The themes speak to our present situation, but it was more of a rhyme than a direct attack. The murkiness of the the lighting gave an unsettling noir element to the piece, but I felt that it didn’t quite work all the time. Recommended if you like Brecht (like I do).

One could, of course, make a longer critique about the way women are used in the play, but I’ll table that. This is definitely men’s avant garde of the 70s stuff.

Some readers of this blog may be interested in a project by Alison Weiss, a history grad student at UC Berkeley, who is working on breaking a code used in a Civil-War era diary:

I’m writing on behalf of Professors Carla Hesse and Mark Peterson in U.C Berkeley’s History Department, where I am a PhD candidate. We recently got hold of a Civil War Diary that has multiple sections written in code. No one in the Department has any idea how to decipher it…

The code appears to have been broken by Qingchun Ren. Kudos!

Do any of readers of this blog have a preferred charity to which to donate old textbooks? In particular, I do not think that electromagnetism has changed that much since 1999, so I figured I might find a better home for some old books.

There’s a new postdoc position open in a new interdisciplinary center to work on overcoming practical challenges to implementing differential privacy. Having started work in this area myself, I definitely think there are a number of interesting (and difficult) practical considerations faced by data-holders that the existing literature is just starting to touch upon.

There are some more talks to blog about, probably, but I am getting lazy, and one of them I wanted to mention was Max’s, but he already blogged a lot of it. I still don’t get what the “Herbst argument” is, though.

Vinod Prabhakaran gave a talk about indirect decoding in the 3-receiver broadcast channel. In indirect decoding, there is a “semi-private” message that is not explicitly decoded by the third receiver. However, Vinod argued that this receiver can decoded it anyway, so the indirectness is not needed, somehow. At least, that’s how I understood the talk.

Lalitha Sankar talked about two different privacy problems that could arise in “smart grid” or power monitoring situations. The first is a model of system operators (ISOs) and how to view the sharing of load information — there was a model of $K$ different “sources” or states being observed through a channel which looked like a AWGN faded interference channel, where the fading represents the relative influence of the source (or load on the network) on the receiver (or ISO). She didn’t quite have time to go into the second model, which was more at the level of individual homes, where short-time-scale monitoring of loading can reveal pretty much all the details of what’s going on in a house. The talk was a summary of some recent papers available on her website.

Negar Kiyavash talked about timing side channel attacks — an adversary can ping your router and from the delays in the round trip times can learn pretty much what websites you are surfing. Depending on the queueing policy, the adversary can learn more or less about you. Negar showed that first come first serve (FCFS) is terrible in this regard, and there is a bit of a tradeoff wherein policies with higher delay offer more privacy. This seemed reminiscent of the work Parv did on Chaum mixing…

Lav Varshney talked about security in RFID — the presence of an eavesdropper actually detunes the RFID circuit, so it may be possible for the encoder and decoder to detect if there is an eavesdropper. The main challenge is that nobody knows the transfer function, so it has to be estimated (using a periodogram energy detector). Lav proposed a protocol in which the transmitter sends a key and the receiver tries to detect if there is an eavesdropper; if not, then it sends the message.

Tsachy Weissman talked about how to estimate directed mutual information from data. He proposed a number of estimators of increasing complexity and showed that they were consistent. The basic idea was to leverage all of the results on universal probability estimation for finite alphabets. It’s unclear to me how to extend some of these results to the continuous setting, but this is an active area of research. I saw a talk recently by John Lafferty on forest density estimation, and this paper on estimating mutual information also seems relevant.

I received this email from the USPS today:

Your hold mail request has ended \$endDate

The Hold Mail Service for \$dateRangeText has ended. So we’ll be resuming your regular mail delivery. Remember to pick up your held mail at the Post Office if you’re not having it delivered to your address.

Hold Mail Details

Confirmation Number: \$holdMailDTO.confirmationNumber

Hold mail for…
\$fullName

Phone: \$phone

Hold Mail Start Date: \$startDate

End Date: \$endDate

Delivery option: \$deliveryOption

The ITA Workshop finished up today, and I know I promised some blogging, but my willpower to take notes kind of deteriorated during the week. For today I’ll put some pointers to talks I saw today which were interesting. I realize I am heavily blogging about Berkeley folks here, but you know, they were interesting talks!

Nadia Fawaz talked about differential privacy for continuous observations : in this model you see $x_1, x_2, x_3, \ldots$ causally and have to estimate the running sum. She had two modifications, one in which you only want a windowed running sum, say for $W$ past values, and one in which the privacy constraint decays and expires after a window of time $W$, so that values $W$ time steps in the past do not have to be protected at all. This yields some differences in the privacy-utility tradeoff in terms of the accuracy of computing the function.

David Tse gave an interesting talk about sequencing DNA via short reads as a communication problem. I had actually had some thoughts along these lines earlier because I am starting to collaborate with my friend Tony Chiang on some informatics problems around next generation sequencing. David wanted to know how many (noiseless) reads $N$ you need to take of a genome of of length $G$ using reads of length $L$. It turns out that the correct scaling in this model is $L/\log G$. Some scaling results were given in a qualitative way, but I guess the quantitative stuff is being written up still.

Michael Jordan talked about the “big data bootstrap” (paper here). You have $n$ data points, where $n$ is huge. The idea is to subsample a set of size $b$ and then do bootstrap estimates of size $n$ on the subsample. I have to read the paper on this but it sounds fascinating.

Anant Sahai talked about how to look at some decentralized linear control problems as implicitly doing some sort of network coding in the deterministic model. One way to view this is to identify unstable modes in the plant as communicating with each other using the controllers as relays in the network. By structurally massaging the control problem into a canonical form, they can make this translation a bit more formal and can translate results about linear stabilization from the 80s into max-flow min-cut type results for network codes. This is mostly work by Se Yong Park, who really ought to have a more complete webpage.

Paolo Minero talked about controlling a linear plant over a rate-limited communication link whose capacity evolves according to a Markov chain. What are the conditions on the rate to ensure stability? He made a connection to Markov jump linear systems that gives the answer in the scalar case, but the necessary and sufficient conditions in the vector case don’t quite match. I always like seeing these sort of communication and control results, even though I don’t work in this area at all. They’re just cool.

There were three talks on consensus in the morning, which I will only touch on briefly. Behrouz Touri gave a talk about part of his thesis work, which was on the Hegselman-Krause opinion dynamics model. It’s not possible to derive a Lyapunov function for this system, but he found a time-varying Lyapunov function, leading to an analysis of the convergence which has some nice connections to products of random stochastic matrices and other topics. Ali Jadbabaie talked about work with Pooya Molavi on non-Bayesian social learning, which combines local Bayesian updating with DeGroot consensus to do distributed learning of a parameter in a network. He had some new sufficient conditions involving disconnected networks that are similar in flavor to his preprint. José Moura talked about distributed Kalman filtering and other consensus meets sensing (consensing?) problems. The algorithms are similar to ones I’ve been looking at lately, so I will have to dig a bit deeper into the upcoming IT Transactions paper.

I am on the PC for this conference, so I figured I would advertise the CFP here for those readers who would be interested.

6th International Conference on Information-Theoretic Security
August 15–17, 2012

This is the sixth in a series of conferences that aims to bring together the leading researchers in the areas of information theory, quantum information theory, and cryptography. ICITS covers all aspects of information-theoretic security, from relevant mathematical tools to theoretical modeling to implementation. Papers on all technical aspects of these topics are solicited for submission.

Note that this year there will be two distinct tracks for submission.

Important Dates:

• Conference Track Submission: Monday, March 12, 2012
• Conference Track Notification: Friday, May 4, 2012
• Proceedings version: Tuesday, May 29, 2012
• Workshop Track Submissions: Monday, April 9, 2012
• Workshop Track Notification: Monday, May 28, 2012

Note: ICITS (Aug. 15-17, Montreal) is the week before CRYPTO 2012 (Aug. 20–23, Santa Barbara).

Two Tracks: Conference and Workshop

The goal of ICITS is to bring together researchers on all aspects of information-theoretic security. To this end, ICITS 2012 will consist of two types of contributed presentations. The conference track will act as a traditional conference (original papers with published proceedings). The workshop track will operate more like an informal workshop, with papers that have appeared elsewhere or that consist of work in progress.

1. Conference Track (with proceedings): Submissions to this track must be original papers that have not previously appeared in published form. Accepted papers will be presented at the conference and will also be published in the conference proceedings (which will appear in Springer’s Lecture Notes in Computer Science series). We note that simultaneous submission to journals is acceptable, but simultaneous submission to other conferences with published proceedings is not.
2. Workshop Track (no proceedings): To encourage presentation of work from a variety of fields (especially those where conference publication is unusual or makes journal publication difficult), the committee also solicits “workshop track” papers. Accepted papers will be presented orally at the conference but will not appear in
the proceedings. Submissions to this track that have previously appeared (or are currently submitted elsewhere) are acceptable, as long as they first appeared after January 1, 2011. Papers that describe work in progress are also welcome. We note that the same standards of quality will apply to conference and workshop papers.

Conference Organization:

Program Chair: Adam Smith (Pennsylvania State University)
Program Committee:

• Anne Broadbent (University of Waterloo)
• Thomas Holenstein (ETH Zurich)
• Yuval Ishai (Technion)
• Sidharth Jaggi (CU Hong Kong)
• Bhavana Kanukurthi (UCLA)
• Ashish Khisti (University of Toronto)
• Yingbin Liang (Syracuse University)
• Prakash Narayan (University of Maryland)
• Louis Salvail (Universite de Montreal)
• Anand Sarwate (TTI Chicago)
• Christian Schaffner (University of Amsterdam)
• Adam Smith (Pennsylvania State University)
• Stephanie Wehner (National University of Singapore)
• Daniel Wichs (IBM Research)
• Juerg Wullschleger (Universite de Montreal)
• Aylin Yener (Pennsylvania State University)

General Chair: Juerg Wullschleger (Universite de Montreal)
Local Co-Chairs: Claude Crepeau (McGill University) and Alain Tapp
(Universite de Montreal)

Detailed instructions for authors can be found in the full CFP, available on the website.

The ITA Workshop is here! Blogging will happen, I hope, but probably not as extensively as before.

An important look at 6th Street in San Francisco (h/t Celeste).

Werner Herzog is sometimes off-puttingly weird, but this critique (until around 3 min) is on-point (h/t B.K.).

The Death of the Cyberflâneur (h/t Mimosa). I am looking forward to being a flâneur in Chicago. The mild winter has helped, but I am rather looking forward to the spring for it. For now I suppose I am more of a cyberflâneur… Also, I hate the prefix “cyber.”