Tag Archives: information theory

ITA Workshop 2012 : More Talks

Posted on by

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.

ITA Workshop 2012 : Talks

Posted on by

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.

Call for Papers : ICITS 2012

Posted on by

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
Montreal, Quebec, Canada
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.

Linkage

Posted on by

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).

You got that right, Arnold Schwartzenegger.

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.”

IEEE page charges for Open Access

Posted on by

I just got an email saying my page proofs are ready for my paper with Alex Dimakis on mobility in gossip algorithms. If I want to make the paper open access, I have to shell out $3000. I think this is in addition to the $110 per page “voluntary” page charges. Now, I’m on the record as being a fan of Open Access, but $3k is a pretty hefty chunk of change! Has anyone else had experience with this?

Some deals from Cambridge

Posted on by

Network Information Theory by Abbas El Gamal and Young-Han Kim is out! I saw copies in Young-Han’s office earlier this month when I was visiting San Diego. Having been at UCSD while the book was being written, I can attest to the comprehensiveness, attention to detail, and clarity of the writing. A must-have!

In addition, Cambridge is having a sale — many books for $10 softcover and $20 hardcover. Most of them are not comm/SP/IT related, so you won’t have to spend all of your money… One warning is that the website is INCREDIBLY SLOW and there is no real search interface for the sale, so you have to get through pages of “MRS Symposium Proceedings.” Titles that may be of interest:

and others, including sensor nets titles and miscellaneous wireless comm titles. Just use ENGR11 as the discount code.

Linkage

Posted on by

It’s been a while since I’ve posted, and I am going to try to post more regularly now, but as usual, things start out slowly, so here are some links. I’ve been working on massaging the schedule for the 2012 ITA Workshop (registration is open!) as well as some submissions for KDD (a first for me) and ISIT (since I skipped last year), so things are a bit hectic.

Chicago Restaurant Week listings are out, for the small number of you readers who are in Chicago. Some history on the Chicago activities of CORE in the 40s.

Via Andrew Gelman, a new statistics blog.

A paper on something called Avoidance Coupling, which I want to read sometime when I have time again.

Our team, Too Big To Fail, finished second in the 2012 MIT Mystery Hunt. There were some great puzzles in there. In particular, Picture An Acorn was awesome (though I barely looked at it), and Slash Fiction was a lot of fun (and nostalgia-inducing. Ah, Paris!). Erin has a much more exhaustive rundown.

Spread spectrum… in spaaaaaaaace…

Posted on by

I saw on the ArXiV earlier this month a paper on interstellar communication by Berkeley’s own David Messerschmitt. I only met him once, really, at my prelim exam oh so many years ago, but I figured I would give it a read. And here you thought spread spectrum was dead…

Prof. Messerschmitt proposes using spread-spectrum because of its combination of interference robustness and detectability. The fundamental assumption is that the receiver doesn’t know too much about the modulation strategy of the transmitter (this is a case of stochastic encoding but deterministic decoding). The choice of wide-band signaling is novel — SETI-related projects have looked for narrowband signals. The bulk of the paper is on what to do at the transmitter:

The focus of this paper is on the choice of a transmitted signal, which directly parallels the receiver’s challenge of anticipating what type of signal to expect. In this we take the perspective of a transmitter designer, because in the absence of explicit coordination it is the transmitter, and the transmitter alone, that chooses the signal. This is significant be- cause the transmitter designer possesses far less information about the receiver’s environment than the receiver designer, due to both distance (tens to hundreds of light-years) and speed-of-light delay (tens to hundreds of years). While the receiver design can and should take into account all relevant characteristics of its local environs and available resources and technology, in terms of the narrower issue of what type of signal to expect the receiver designer must rely exclusively on the perspective of the transmitter designer.

The rest of the paper centers on designing the coding scheme which is robust to any kind of radio-frequency interference (RFI), without assuming any knowledge at the decoder — specific knowledge of the RFI (say, a statistical description) can only enhance detection, but the goal is to be robust against the modeling issues. To get this robustness, he spends a fair bit of time is spent developing isotropic models for noise and coding (which should be familiar to information theorists of a Gaussian disposition) and then reduces the problem to looking for appropriate time and bandwidth parameters.

This is definitely more of a “communication theory” paper, but I think some of the argument could be made clearer by appeals to some things that are known in information theory. In particular, this communication problem is like coding over an AVC; the connection between spread-spectrum techniques and AVCs has been made before by Hughes and Thomas. However, translating Shannon-theoretic ideas from AVCs to concrete modulation schemes is a bit messy, and some kind of translation is needed. This paper doesn’t quite “translate” but it does bring up an interesting communication scenario : what happens when the decoder only has a vague sense of your coding scheme?

HGR maximal correlation and the ratio of mutual informations

Posted on by

From one of the presentation of Zhao and Chia at Allerton this year, I was made aware of a paper by Elza Erkip and Tom Cover on “The efficiency of investment information” that uses one of my favorite quantities, the Hirschfeld–Gebelein–Rényi maximal correlation; I first discovered it in this gem of a paper by Witsenhausen.

The Hirschfeld–Gebelein–Rényi maximal correlation \rho_m(X,Y) between two random variables X and Y is

\sup_{f \in \mathcal{F}_X, g \in \mathcal{G}_Y} \mathbb{E}[ f(X) g(Y) ]

where \mathcal{F}_X is all real-valued functions such that \mathbb{E}[ f(X) ] = 0 and \mathbb{E}[ f(X)^2 ] = 1 and \mathcal{G}_Y is all real valued functions such that \mathbb{E}[ g(Y) ] = 0 and \mathbb{E}[ g(Y)^2 ] = 1. It’s a cool measure of dependence that covers discrete and continuous variables, since they all get passed through these “normalizing” f and g functions.

The fact in the Erkip-Cover paper is this one:

sup_{ P(z|y) : Z \to Y \to X } \frac{I(Z ; X)}{I(Z ; Y)} = \rho_m(X,Y)^2.

That is, the square of the HGR maximal correlation is the best (or worst, depending on your perspective) ratio of the two sides in the Data Processing Inequality:

I(Z ; Y) \ge I(Z ; X).

It’s a bit surprising to me that this fact is not as well known. Perhaps it’s because the “data processing” is happening at the front end here (by choosing P(z|y)) and not the actual data processing Y \to X which is given to you.