A month or two ago I was on the shuttle going to campus and ended up talking with Steve Checkoway about his work. He described a problem in election auditing that sounded pretty interesting : given an election between, say, two candidates, and the ability to sample individual ballots at random and compare how they were counted versus how they should have been counted, how should we design an auditing algorithm that has the following property: if the auditor certifies that the reported winner is the true winner, then it is wrong with probability no larger than 
After a couple more meetings we came up with a pretty simple method based on minimizing a Kullback-Leibler divergence. This minimum KL-divergence gives a bound on the error probability of our algorithm which we can then compare to
We wrote up a paper on it with Steve’s advisor Hovav Shacham and submitted it to 2010 Electronic Voting Technology Workshop, where it was accepted. We’re making some major-ish revisions (mostly in the simulations) but I’m pretty excited about it. There are some fun analysis questions lurking in the corners that we didn’t have time to get to yet, but I’m looking forward to poking at them after ISIT.
Speaking of which, ISIT is coming up — not sure how much I will blog, but there will be something at least.
it can detect all signals whose support is the same as 
with an iid process (say equiprobable coin flips) 
. Using the 
and 
. If the entropy spectrum in 
are the number of bits in each chunk). How do you size the chunks to maximize the volume? This can be solved with dynamic programming. There are still several open questions left, but the whole construction relies on using “optimal codes of finite blocklength” which also needs to be solved. Lav has some interesting ideas along these lines that he told me about when I was in Boston two weeks ago… 
constraints. Achievability uses Han-Kobayashi in a block-Markov encoding with backward decoding, and the converse uses the El Gamal-Costa argument with some additional Markov properties. For the “bit-level” deterministic channel model, there is an interpretation of the feedback as filling a “hole” in the interference graph.
, Bob has 
and they want to compute some functions 
and 
. The pairs 
are iid and jointly distributed according to some distribution 
. As an example, 
could be correlated bits and 
and 
could be the AND function. In previous work the authors characterized the the rate region (allowing vanishing probability of error) for 
rounds of communication, and here they look at the case when there are infinitely many back-and-forth messages. The key insight is to characterize the sum-rate needed as a function of 
and look at that surface’s analytic properties. In particular, they show it’s the minimum element of a class 
of functions which have some convexity properties. There is a 
, where the realized state sequence is known ahead of time at the encoder. The first paper proved a technical lemma about the image size of “good codeword sets” which are jointly typical conditioned on a large subset of the typical set of 
sequences. That is, given a code and a set of almost 
typical sequences in 
from long binary strings 
so that a verifier can look at a new long vector 
and tell whether or not 
. They develop a scheme which stores the index of a reference vector 
that is “close” to 
. This can be done with low complexity. They calculated false accept and reject rates for this scheme. Since the goal is not reconstruction or approximation, but rather a kind of classification, they can derive a reference vector set which has very low rate.
bits per pair, and the other in which only the labels 
must be sent. He defined a rate-distortion-like function where the generalization error the classifier played the role of the distortion. In the first case it’s easier for the encoder to learn the classifier itself and send the classifier over — this takes 0 bits per sample, asympotically, and incurs no extra generalization error. In the second case he uses a kind of Wyner-Ziv-like scheme which is a bit more involved. Compression is not a thing many machine learning folks think about, so I think there’s a lot of interesting stuff in this direction.
users and the decoder wants to detect which users transmitted. The users are each “on” with some fixed probability, and they show this can be put into a sparsity detection framework. There are two problems to overcome — the near-far effect of large dynamic range of the received signals, and a “multiaccess interference” (MAI) phenomenon that plagues most detection algorithms, including the Lasso and orthogonal matching pursuit (OMP). The question is whether a practical algorithm can overcome these effects — they show that a modification of OMP can do so as long as the decoder knows some additional information about the received signals, namely the power profile which is the order of the users’ power, conditional that they are active.
An Ergodic Walk 