Daily Archives: June 26, 2012

Quick thoughts on Trailhead

Posted on by

If you’re attending ISIT then you probably got an email about Trailhead, a graphical system which links papers at ISIT “based on how many authors they have in common in the references, and each paper is linked to the 4 closest neighbors.” It’s written by Jonas Arnfred, a student at EPFL. The search feature doesn’t seem to be working, but it’s a fun little app.

I wonder how different the graph would look using something like the Toronto Paper Matching System, which is used by NIPS and ICML to match papers to reviewers. One could even imagine a profiler which would help you pick out papers which would be interesting to you — you could upload 10 papers of your own or that you find interesting, and it could re-visualize the conference through that viewpoint.

I was interested in the 19 papers which had no connections. Here are a few, randomly sampled:

  • Fish et al., Delay-Doppler Channel Estimation with Almost Linear Complexity
  • Song and İs ̧can, Network Coding for the Broadcast Rayleigh Fading Channel with Feedback
  • Bilal et al., Extensions of \mathbb{Z}_2\mathbb{Z}_4-Additive Self-Dual Codes Preserving Their Properties
  • Bernal-Buitrago and Simón, Partial Permutation Decoding for Abelian Codes
  • Kovalev and Pryadko, Improved quantum hypergraph-product LDPC codes
  • Price and Woodruff, Applications of the Shannon-Hartley Theorem to Data Streams and Sparse Recovery
  • Willems, Constrained Probability
  • Nowak and Kays, On Matching Short LDPC Codes with Spectrally-Efficient Modulation

They seem to run the gamut, topic wise, but I think one would be hard-pressed to find many unlinked multi-user information theory papers.

On the other side, there’s a little cluster of quantum information theory papers which all have similar citations, unsurprisingly. They show up as a little clique-ish thing on the bottom right in my rendering (it may be random).

Who are my neighbors in the graph?

  • Strong Secrecy in Compound Broadcast Channels with Confidential Messages — Rafael F. Wyrembelski, Holger Boche
  • Lossy Source-Channel Communication over a Phase-Incoherent Interference Relay Channel — H. Ebrahimzadeh Saffar, M. Badiei Khuzani and P. Mitran
  • Shannon Entropy Convergence Results in the Countable Infinite Case — Jorge Silva, Patricio Parada
  • Non-adaptive Group Testing: Explicit bounds and novel algorithms — Chun Lam Chan, Sidharth Jaggi, Venkatesh Saligrama, Samar Agnihotri
  • Non-coherent Network Coding: An Arbitrarily Varying Channel Approach — Mahdi Jafari Siavoshani, Shenghao Yang, Raymond Yeung
Advertisement

Thresholds in random integer programs

Posted on by

Karthik Chandrasekaran gave a talk at TTI today on the feasibility of integer programs. Given a polytope defined by the inequalities A x \le b in dimension n, can we say whether the polytope contains an integer point? In general, the problem is NP-hard, but efficient algorithms are known for special sub-cases. The goal in this talk was to understand if random instances of the problem are also hard.

The first thing to figure out is what do we mean by a random instance? Consider a point x_0 and the sphere S of radius R around x_0. Now draw m vectors x_1, x_2, \ldots, x_m uniformly from the surface of the unit sphere, and consider the polytope defined by faces which are tangent to S at x_0 + x_i for i = 1, 2, \ldots, m. That is, the vector x_0 + x_i is the normal vector of that face. This defines a random polytope whose distribution depends on the parameters (n,m,x_0,R). The goal is to find how R scales with n and m such that with high probability, the polytope contains an integer point for all x_0.

If the radius R is too small, then this will be hard to do because guaranteeing that an integer point is in the interior for all x_0 becomes hard. If R = \sqrt{n}/2, then we will always have an integer point. What should the real scaling for R look like?

The simple form of the main result is that if n \le m \le 2^{\sqrt{n}} and R \ge c_1 \sqrt{log(m/n)}, with high probability the polytope will have an integer point for every x_0. Conversely, if R \le c_0 \sqrt{ log(m/n) }, then with high probability the polytope “centered” at x_0 = (1/2,1/2,\ldots,1/2) with not contain an integer point. Note that if the number of faces is linear in n, then a constant radius is sufficient. I’m trying to square that with the “infinite dimensional spheres have vanishing volume and expanding surface area” but I think the fact that the polytope is “pointy” means that L_1 geometry gives better intuition.

To prove these bounds on R, they make a connection to the discrepancy of random Gaussian matrices (which approximate the random unit vector row matrices). The paper is on arxiv for those who want to take a look.