Tag Archives: academia

How much detail should a review version have?

Posted on by

One pesky problem that seems to pop up when I write or review papers is the “minor algebra error due to space constraints.” You have some theorem and then you go back and redefine x to be 2 y instead of y/2 and then suddenly stuff is off by a factor of 4 everywhere, but that doesn’t matter for the result per se — it’s just some constant floating around. This is of course an issue with conference papers, since they have strict page limits, and you end up shortening proofs to sketches, but it also happens while revising journal papers. One of the jobs of the reviewer is to check that the algebra works out, which becomes tedious if all the algebra is in fact correct but the paper skips 5 lines of simplifications and you have to go and work it out yourself.

Which brings me to the modest proposal : when submitting a journal paper, put in all the algebra, with a little footnote saying that you’ll omit the intermediate steps in the final version. This way, the checking for correctness becomes almost mechanical. Sure, it may make the submitted manuscript look bloated, but then the time saved can be spent on checking the structure of the argument. As an added benefit, the writer will be forced to explore the full ramifications of changing the notation around. Of course, this wouldn’t be possible (probably) for conference papers, but would it help for the journal process?

ISIT 2007 : general impressions

Posted on by

I had meant to start blogging ISIT as it was going on, but that turned out to be infeasible due to a number of factors. The most relevant was that I spent the first 3 days of this year’s conference battling a fever, so by the time I got back to the hotel I was in no mood to type up any of the notes I had taken from the talks, and I also had to leave early the first two days so that I could lie down. Another downside was that my attention was not as sharp as it should have been, so I apologize in advance for the facile nature of my observations.

In general, the program this year felt way more Shannon-theory heavy to me than last year’s. Perhaps that’s because I wasn’t hanging out with many coding theorists, so I didn’t hear about the talks, but I felt like the coding talks in which I was interested were few in number. Furthermore, I ended up missing the one or two that I really wanted to attend (such as the new Reed-Solomon list decoding algorithm).

My biggest gripe was the lack of water at the sessions — there were two snack breaks, between the two morning and two afternoon sessions. There was juice, water, coffee and caffeinated tea, and everything was cleared out immediately upon the resumption of the sessions. I understand taking away the coffee and juice, but there was no water to be had in the session rooms and none in the convention area unless you bought it at the overpriced bar. Perhaps that’s in the contract with the convention center, but it’s a lousy deal.

This year they were also quite zealous in checking that everyone had their conference badge to prove that they had registered. The stinginess with respect to the water complemented (in some sense) their concern that freeloaders not be allowed into the sessions. I left my badge at the hotel one day and was made to get a temporary one for that day.

The big news of course was that Bob Gray won the Shannon Award for next year, which made me happy. I heard some people say beforehand that he seemed like an outside shot since he’s not a pure information theorist per se, and that’s what the award is about. In some sense Sergio Verdú is an Information Theorist’s information theorist, and I think one would be hard-pressed to find a candidate like him. You wouldn’t say Kailath is a pure IT guy either, right?

All in all, I had a good time, and had a few interesting research discussions with different people. I find myself wanting to work on some new problems, which is good from the perspective of learning some new areas, but bad from the perspective of trying to wrap things up and write my thesis. I was asked by several people if I was graduating soon and what I was planning on doing next, which is always a terrifying question. Hopefully I’ll get some of that sorted out this summer…

rejected opening paragraph for my ISIT 2007 paper

Posted on by

And it’s a good thing too — I don’t even like Buffy…

Xander wishes to leave a message for his friend Buffy and writes it on a chalkboard using a secret code. After he leaves, Spike comes by and sees the encoded message on the chalkboard. Not content to leave things as they are, he decides to make some limited alterations to what was written. When Buffy comes back that evening, she has to recover the message left for her by Xander, despite Spike’s non-causal tampering with the encoded message. In this paper we will look at a model for this problem, which can be thought of as randomized coding for arbitrarily varying channels with the codeword known to the jammer.

yet another crunch

Posted on by

As if having the deadlines for ISIT and CISS 2007 so close to each other wasn’t bad enough, the deadlines for the Statistical Signal Processing Workshop and the Information Theory Workshop in Tahoe are both on April 1. In the former case I didn’t mind, since I didn’t have anything I wanted to send to CISS and besides, it’s bad to distract oneself with conference papers. But in the latter case, I have results to send and reasons to go to both. Perhaps going out of town for spring break wasn’t such a good plan after all…

Good survey articles for communications theorists

Posted on by

One thing that I could have used when I started graduate school was a good list of survey articles and introductions to different modeling paradigms and mathematical ideas used in communications and signal processing. It would have done wonders to help me get up to speed on these widely-used ideas. As a grad student, you can’t take classes in everything, and a lot of these ideas are important in research but haven’t really made it into course curricula either. Hopefully people reading this will comment and suggest more titles — I’ll expand the list as more material is suggested.

Topics that it would nice to have (preferably at a level for early graduate school) : convex analysis, Fourier analysis, percolation (there’s a book but it’s a bit advanced for many I think), generating functions… anything else, really.

High dimensional convex geometry

Keith M. Ball, An Elementary Introduction to Convex Geometry, Mathematical Sciences Research Institute Publications Vol. 31 : Flavors of Geometry, 1998.
This is a survey article that requires a bit of mathematical maturity, but covers a lot interesting material on high dimensional balls, convex polytopes, volume ratios, and ends up in Dvoretsky’s Theorem. This is less of a “techniques” paper but is good for getting some intuition and facts straight about high dimensional convex things.

Isoperimetric inequalities

A. Dembo, T. Cover, and J.A. Thomas, Information theoretic inequalities, IEEE Transactions on Information Theory, 37(6), 1991.
This is the information-theoretic take on some isoperimetric inequalities.

Markov Chains and Mixing

V. Guruswami. Rapidly Mixing Markov Chains: A Comparison of Techniques, May 2000.
A nice readable survey that gets the main results across.

Game Theory

Robert Gibbons, Game Theory for Applied Economists, Princeton University Press, 1992.
This is a quick read that will get the basic terminology and ideas of game theory. It’s not as useful for learning the deeper stuff, but it’s definitely accessible and well-written.

Auctions and auction theory — used for network congestion and resource allocation

Paul Klemperer, A Survey of Auction Theory, in Auctions: Theory and Practice, Princeton University Press, 2004.
A non-technical introduction to the study of auctions and how they are modeled. Good for getting an idea of what all the fuss is about.
Vijay Krishna, Auction Theory, Academic Press, 2002.
This book covers the basics and reading the first few chapters should let you get a handle on the terminology so that you can read some of the network congestion and pricing papers.

Conditional growth charts

Posted on by

The Annals of Statistics published a “discussion paper” on Conditional growth charts by Y. Wei and and X. He, with 4 comment papers and a rejoinder from the authors. It’s reminiscent of the Crooked Timber book events (Iron Council was a particular favorite), only significantly more formal. It’s a new format to me for mathematical publication, and almost feels like “peer review in public,” with the mean comments taken out. Perhaps if I get some time I’ll read the paper for real and see what the fuss is about…

ITA Workshop : Panel on publication issues

Posted on by

Part of ITA was a panel on publication issues in information theory. Paul Siegel was the moderator and led off with three binaries to spark discussion “paper versus plasma” (the medium of publication), “prophets versus profits” (the financial model), and “peer review versus page rank” (quality measurements). Pretty much everyone thought page rank was not really a measure of anything except… page rank, so peer review was not under attack (thank goodness). In general people were in favor of paper at least for archival purposes, so that the ability to browse would still be there. Finally, everyone said they liked the IEEE (no surprise there) and its publication model.

Dave Forney talked about the spiraling costs of Elsevier-owned journals to libraries and urged people to just say no. He implicated those professors who choose to be on the editorial boards of such journals as being part of the problem, and urged them to divest from Elsevier, as it were. In general, he wanted faculty to be more proactive and aware of these important issues, a stance that I was 100% with. He then turned to ArXiV, and told everyone to submit their preprints to ArXiV so that people could know what research is being done. He said usage was increasing, but too slowly.

Andrea Goldsmith said that she found ArXiV to be of limited use since articles posted there are not peer reviewed, and the value of an article is only guaranteed via publication in the Transactions. For the publication model, she stressed the importance of access to the Transactions for the entire IEEE, so that the IT Society should not drift off. She also urged faculty to put institutional pressure on Elsevier by boycotting.

Steve McLaughlin also brought up the ties that bind IEEE and IT. The online Transactions are a major source of revenue, and it was the IT Society that spurred the creation of IEEExplore. He lauded ArXiV as a good impetus to embrace new ideas and models for publication, and floated the idea of an Open Access (OA) journal to complement the Transactions.

Dave Neuhoff reiterated that the journal should be the focus of the field, and that conference papers are not archival for information theorists. Because of this and other reasons, the IT Society was able to convince the IEEE to grant online access to conference proceedings.

Vince Poor, the current Editor-In-Chief, talked about copyright issues in the age of ArXiV and pointed out how reasonable the IEEE is. He seemed to indicate that Elsevier doesn’t affect our community much, but I didn’t really follow his argument there. He also claimed that market forces will push the publication industry to embrace electronic formats.

Rüdiger Urbanke was very excited about ArXiV because it could provide timestamps, and since the field is moving faster these timestamps are important. He also questioned the 5 page ISIT paper, which is not reviewed that carefully, and said that if there is a 5 page limit on correspondences the scale doesn’t make sense, especially in light of conference papers being non-archival. Finally, the pressure to publish is what enables Elsevier, and so this pressure must be alleviated somehow.

In the Q&A, one person asked about double-blind reviewing, which the panel wholeheartedly embraced. I think they should do it to, and I really have no idea what is holding it up, except that perhaps Pareja, the online paper management system, has to be hacked to do it. Someone else asked why we need timestamps from ArXiV when there are timestamps on the IT Transactions papers already, but Urbanke said that it has to do with time scales more than anything, and ArXiV lets you track revisions. Another person complained that ArXiV could become a repository for erroneous results and rejected papers, but Forney was quick to note that ArXiV’s value lies in showing who is working on what, and clearly there are no guarantees on the veracity of the claims made there. The last question was on the nature of journal papers versus conference papers — if conference papers are not archival, does that make it ok to merge 3 conference papers to make a journal paper? The panel seemed surprised to hear that this could be considered double-publishing, and the informal consensus seemed to be that doing so was not self-plagiarism.

I was most disappointed that nobody took up Steve McLaughlin’s comment on making an OA journal that is peer-reviewed and pay-to-publish. I’ve already written about having a new letters journal, but an OA journal would provide an alternative place to publish papers that is not evil and possibly has faster review turnaround than the IT Transactions. Given there are 900 papers submitted a year to the IT Transactions now, it seems like the benefits would be great. It would also help alleviate the Elsevier-feeding publication pressure. But the IT Society could never endorse such a project and thus a panel like this would not address that issue. You’d have to get professors without their official IEEE hats on to discuss this freely, and that wasn’t going to happen at this panel. I think if the OA option is on the table it could get modified into something more palatable and friendly to the iEEE, but it of course would take some discussion and a desire to make it happen.

ITA Workshop : source and channel coding

Posted on by

There were some talks on dynamic spectrum access as well as waterfilling and other resource allocation problems.

  • Twice-universal types and simulation of individual sequences (Alvaro Martín, Universidad de la República, Neri Merhav, Technion, Gadiel Seroussi, Universidad de la República, and Marcelo J. Weinberger, HP Labs)

    A universal source code partitions the set of all length-n sequences so that under an iid model class into types, so that two sequences that have the same type have the same probability. If we look at order-k Markov sources, we can ask for a universal code that is universal for all n and k. This leads to twice-universal source codes. Given a Markov-order esimator that takes a sequence and estimates an order k, we can intersect the set of sequences with the same order with the type class of order k. Given some conditions on the quality of the order estimator, this partition has some nice properties, including simulation of individual sequences with similar empirical statistics.

  • Universal noiseless compression for noisy data (Gil I. Shamir, University of Utah, Tjalling J. Tjalkens, Frans M. J. Willems, Eindhoven University of Technology)

    We’d like to be able to compress noisy data, since sometimes we only have access to noisy data. What they propose is a new probability estimator that can take into account upper and lower bounds on the probability to be estimated. So if I know the true probability lies in [a,b] I can use that knowledge in the estimator. When a = 0, b = 1 this reduces to the Krichevsky-Trofimov (KT) estimator. Intuitively, noise reduces the richness of the model class, and hence reduces the redundancy. Some properties of the esimator and corresponding compression results were given.

  • On universal coding of unordered data (Lav R. Varshney and Vivek K Goyal, MIT)

    Suppose you want to compress data but don’t care about the order of the data (think database records for concreteness) — then using a source code for vectors is silly, since you want a source code for multisets. In this work they address universal coding for multisets , and show that universal lossless coding is impossible, but a low universal rate is achievable across the model class (iid sources I believe, but it might be more general).

  • Sum-Capacity of a Degraded Gaussian Multiaccess Relay Channel (Lalitha Sankar, WINLAB, Rutgers, Gerhard Kramer, Bell Labs, and Narayan B. Mandayam, WINLAB, Rutgers)

    For a physically degraded multiple-access relay channel (MARC), the decode-forward inner bound and old outer bounds do not match in general. But by making new outer bounds that exploit the causality of the relay, an optimized decode-forward scheme meets the outer bound.

  • Secrecy generation for channel models (Imre Csiszar, Renyi Institute, Budapest, and Prakash Narayan, Univ. of Maryland, College Park, USA)

    I am not as familiar with the 2004 paper on which this work builds (but I’m reading it now). The model is that an encoder transmits a vector into a DMC with many outputs. Other terminals each view one output and then can engage in public discussion that is overheard by an eavesdropper. The terminals must come up with a secret key that is secret from the eavesdropper. The results are related to a multerminal source problem that was discussed earlier.

ITA Workshop : networks

Posted on by

There were some talks on dynamic spectrum access as well as waterfilling and other resource allocation problems.

  • Robust routing for dynamic ad hoc wireless networks based on embeddings (D. Tschopp, EPFL, S.N. Diggavi, EPFL and M. Grossglauser, EPFL)

    In fading, multiple unicast networks with mobility and point-to-point links, how can we do route discovery withi limited control overhead? This is a question of topology versus geometry and so they use a graph embedding of the communication graph (taking fading into account) into Rn to minimize the worst-case stretch. By using beacons to coordinate partial graph distances they can decentralize the approach a bit.

  • Coding achieves the optimal delay-capacity trade-off in mobile ad hoc networks (Lei Ying, Sichao Yang and R. Srikant, University of Illinois at Urbana-Champaign)

    For networks in which packets have a hard delay deadline, it’s bad news if a packet just dies onces its deadline expires — you might hope to code over packets so that if a packet dies from delay its contents can be recovered from other packets that made it in time (writing this makes it sound like Watership Down). This work tries to look at a mobility model in which nodes choose a fresh new location every time slot and uses coding across packets to help maximize a link rate.

  • On the throughput-region of a random wireless ad hoc network with geographic routing (Sundar Subramanian, Sanjay Shakkottai, University of Texas at Austin, Piyush Gupta, Bell Labs)

    Geographic routing is bad for network congestion and doesn’t deal well with holes in the networks (although there are hacks for this). By splitting a route into multiple paths, the authors can bound away the congestions. To deal with holes, you can erasure-code across the routes and drop a packet if you hit a hole. These two algorithms are shown to be order-optimal up to log factors in the network size.

  • On the wireless communication architecture for consensus problems (Anna Scaglione, Cornell)

    This work tried to incorporate quantization error into gossip algorithms as well as other physical-layer considerations. I wasn’t able to parse out the results (the talk was notation-heavy), but I suppose I will get to see the paper soon.

  • The law second class customers obey (James Martin, Oxford University, Balaji Prabhakar, Stanford University)

    The best thing about this talk was that it was given on a whiteboard (no slides) and was one of the clearest talks I went to at the whole workshop. Maybe technology is getting in the way. Suppose that we have an exponential service time queue with two Poisson arrival processes (first and second class customers). The first class customers queue up as if the second class customers were not there. Clearly the departure process for the first class customers is also Poisson. What about the second class customers? They use Weber’s result on the
    interchangeability of exponential-server queues to get an alternate derivation of the departure law.

  • On the broadcast capacity of wireless networks (Birsen Sirkeci-Mergen and Michael Gastpar, UC Berkeley)

    Suppose we have a central broadcaster in a network that wants to flood one message across all the nodes. This paper addresses how do to this for dense and extended networks, under iid and “spatially continuous” fading. For dense networks a two-phase protocol involving cooperation works. For an extended network, a cooperative multistage broadcase protocol is proposed. The key is that multihop protocols perform very badly on the broadcast problem and cooperative protocols are needed to get reasonable results.