• The Matching Polytope has Exponential Extension Complexity. A perfect matching polytope cannot be written as a linear program with polynomially many constraints, only exponentially, so P!=NP cannot be proven using these methods.
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs. This breakthrough algorithm applies the electrical flow method to analyze the full graph at the same time, the inventive step now being that it identifies the paths that create bottlenecks.
• Arithmetic circuits: a chasm at depth three. Any algebraic circuit can be expressed as depth‑3 formulas of sub-exponential size.
• Stratus: Load Balancing the Cloud for Carbon Emissions Control. Arbitrage between clouds and their physical locations will become so competitive that even electricity costs and their taxes will be priced on.

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