brainI wonder how does this fit with another partially-related publication, The Experience of Mathematical Beauty and its Neural Correlates: could well-structured, clean code with idioms and patterns produce the same neural experience of beauty?


2013 is coming to an end, and many papers have been published this year. My recommendations for the next holidays follow: deep, imaginative, mixing the practical and theoretical, and perfect to inspire hope for a better future.

  1. A Simple Algorithm for the Graph Minor Decomposition. A quadratic time algorithm for computing graph minor decompositions is presented, improving from the previous cubic lower bound. It’s very intuitive and easy to understand, so I bet it will appear on future books on algorithms, turning it into a classic.

  2. Dynamic graph connectivity in polylogarithmic worst case time. The classic problem of whether there is a path between two nodes on a dynamically changing graph has a poly-logarithmic algorithm: a theoretical advance with multiple nice applications in practice (routing, transportation, robotics…)

  3. Ambient backscatter: wireless communication out of thin air. Imagine devices communicating wirelessly using ambient radio-frequency as the only source of power, by backscattering ambient RF signals: the Internet of Things (IoT) must surely run over this in the future.

  4. Automatic patch generation learned from human-written patches: although the rate of successfully generated patches is still quite low, it’s interesting to learn that there are progresses on this frankly quite boring area of software maintenance.

  5. F10, A Fault-Tolerant Engineered Network: a novel way to successfully attack the commonplace problem of network reliability and performance in datacenters by re-examining all the involved parts: network topology, routing algorithm and failure detection.

  6. Pinocchio, Nearly Practical Verifiable Computation: amazing improvements in the generation of proofs of general computations and their verification, rendering into the practical this basic necessity of the next cloud computing landscape. Combine this with Pepper and you’re surely gaining knowledge of the most important advances of this year on the future of cloud computing.

  1. The library of George B. Dantzig is for sale: peering over the libraries of great mean is as enlightening as their work.
  2. Benford’s Law and the Art of Succeeding in Multiple Choice Tests: funny application of Benford’s Law.
  3. Polymath8: I’ve been following this project on collaborative mathematics and the article on Wired is a good description of its course.
  4. Rota’s conjecture proved: well, almost proved, there are some problems with the inequivalent representation of matroids, but it’s almost here.
  1. Statistical Basis for Predicting Technological Progress: excellent paper on how easy is to forecast technological progress for some selected technologies (the main problem now being the identification of those technologies).
  2. Amdahl’s Law vs. Gustafson-Barsis’ Law: it contains an interesting insight on the impact of parallelization in relation to power consumption.
  3. Moore’s Law in Photonics: mass diffusion of photonics is nearer than anyone else could think of.
  4. Predicting the Path of Technological Innovation: this paper introduces a simple model that works quite well across markets.
  5. The Economics of Long-Term Digital Storage: comparison and forecast of the different storage technologies.
  1. Turing award goes to Goldwasser&Micali: zero-knowledge, semantic security and universal forgery under chosen message attack.
  2. The DDoS That Almost Broke the Internet: attacking whole Internet eXchanges just to bring down SpamHaus.
  3. Cyber-security: The digital arms trade: price quotes for exploits, The Economist’s style.
  4. NSA Cryptologs: was this really classified? Many opinions and little-to-none noteworthy facts.
  5. RC4 as used in TLS/SSL is broken: see page 306. More here.
  1. Basic Analysis of Entry and Exit in the US Broadband Market (2005-2008): broadband is a too-broad category.
  2. Margin Squeeze in the Telecommunications Sector: A More Economics-Based Approach. An issue in which the European Union Competition Authorities are ahead of the US Supreme Court.
  3. An Empirical Analysis of the Demand for Fixed and Mobile Telecommunications Services. Mobile calls are more inelastic than local calls.
  4. Network effects, Customer Satisfaction and Recommendation on the Mobile Phone Market. Supply-side rule over demand-side effects on the mobile market.
  1. A Simple Algorithm for the Graph Minor Decomposition: Logic Meets Structural Graph Theory. A simple and elegant quadratic time algorithm for computing graph minor decompositions.
  2. Dynamic Graph Connectivity in Polylogarithmic Worst Case Time: simpler algorithm with many applications.
  3. Strongly Universal String Hashing is Fast: just 0.2 cycles per byte to achieve strong universality (implementation).
  4. A Randomized Parallel Algorithm with Run Time O(n^2) for Solving an NxN System of Linear Equations: Extending Raghavendra’s algorithm for linear equations over finite fields, over the reals.
Set your Twitter account name in your settings to use the TwitterBar Section.