Despite Yury‘s attempts to get me to “stop blogging,” here is my much-delayed recap of Allerton. Because of moving to TTI-Chicago right after Allerton and then almost immediately shuttling back to UCSD for the iDASH Privacy Workshop, things have been a bit delayed. I could only attend for two days but I wanted to highlight a few interesting talks that I saw. More Allerton blogging was done by Michael Mitzenmacher (part 1, part 2) and a bit by Maxim Raginsky about his talk on causal calculus (since he blogged about it I don’t have to, ha!). The conference has gotten too big and the rooms are too small to hold the audience, so it probably is time to move the thing. We have similar issues at ITA and the 2012 ITA Workshop is moving off campus next year (you heard it here first, folks!)

But here are some interesting talks I saw:

Optimal Deadline Scheduling with Commitment
S. Chen, L. Tong, and T. He
Lang Tong talked about a cute scheduling problem (although he said they were still looking for the right context in which it would arise) in which jobs come into a processor with four parameters : arrival time, processing time, deadline, and reward. If you can schedule and process the task by the deadline you get the reward. They want to a scheduling policy which achieves a good competitive ratio versus a scheduler who has knowledge of the jobs in advance. They show the best ratio is . The converse comes from looking at an adversary scheduling jobs with higher and higher rewards and processing times. The achievable strategy is a simple threshold/profit test, but the tricky part is proving it achieves the lower bound.

Interference Is Not Noise
S. Bodas, D. Shah, and D. Wischik
This was a talk about wireless medium access in which nodes have external packet arrivals and have to send packets in a slotted model. Optimal scheduling could be done by scheduling a max-weight independent set in the conflict graph, where the weights are queue lengths, but this is computationally hard to do. They relax the model to allow for decoding of interference from other users. This works if nodes are sending linear combinations of symbols in a window of symbols in their queue. The transmit strategy is to flip a coin with a probability proportional to the inverse of the number of files at the transmitted plus the queue lengths at its receivers. At least that’s how I understood the scheme to go.

Generalizing the Posterior Matching Scheme to Higher Dimensions Via Optimal Transportation
R. Ma and T. Coleman
The title pretty much says it. Posterior matching involves the “message point” view of communication with feedback (c.f. Horstein or Schalkwijk-Kailath). The control problem is that the the encoder is trying to steer the posterior belief of the decoder. Rui Ma talked about the case where the message set is for example, and makes a connection between optimal transportation.

Ergodic Mirror Descent
J. Duchi, A. Agarwal, M. Johansson, and M.I. Jordan
This paper looked at stochastic subgradient descent based on non-independent (but mixing) samples from the underlying distribution. A typical example is where the samples are drawn according to a random walk on a graph or via some Markov Chain. They show convergence in expectation as well as with high probability, which in this case is , more or less. Pretty cool!

Controlled Gossip
V. Borkar and A. Karnik
This paper looked at a case where a fixed can fix some of the values of nodes in a gossip algorithm. I got a bit lost when the problem was mapped to an MDP, but there was this great quote from Prof. Borkar: “We will take what we might call engineers’ license, like poetic license. We change the problem into something we can solve.”

The Efficiency of Common Randomness Generation
L. Zhao and Y.-K. Chia
The goal of this paper was to come up with way to look at the Hirschfeld-Gebelein-Renyi correlation by connecting it to the slope of the key generation capacity as a function of the rate. The setup is that an encoder with can send a message of rate to a receiver with correlated to in order to generate a secret key. The capacity is and they show . The result hinges on a different characterization by Erkip and Cover, which I think I might blog about later. (I know, promises, promises).

Opinion Fluctuations and Persistent Disagreement in Social Networks
D. Acemoglu, G. Como, F. Fagnani, and A. Ozdaglar
This was a talk based on the author’s extensive work on gossip models where some agents are “stubborn” and do not perform updates. These stubborn agents stop the network from reaching consensus (unsurprisingly), but they show convergence of the time-average of each agents’ opinion. There are lots of results, but I’d refer the interested reader to the preprint.

User Rankings from Comparisons: Learning Permutations in High Dimensions
I. Mitilagkas, A. Gopalan, C. Caramanis, and S. Vishwanath
This paper was on the sample complexity of learning a set of permutations based on pairwise rankings. They had upper and lower bounds which more or less matched, but there seems to be a lot of different variations on this problem that could be interesting for those who are inclined to study such things…

Geometry of the 3-User MIMO Interference Channel
G. Bresler, D. Cartwright, and D. Tse
This was a really nice talk on looking at where and when interference alignment is and is not possible in the interference channel. They took a divide-and-conquer approach to see what sorts of degrees of freedom were possible. More general results are coming at ITW I think, and those use some algebraic geometry.