 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 AlmostLinearTime 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 depth3 formulas of subexponential 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.
 Building Web Applications on Top of Encrypted Data Using Mylar: practical CryptDB for the web, just adding some lines of code!
 More attacks on WPA2: Exposing WPA2 security protocol vulnerabilities
 Identity based encryption for secure and accountable warrant execution
 If the backdooring of Dual EC DRBG wasn’t enough, now a TLS extension named Extended Random makes it worse.
 An illuminating story on freedom and spying under totalitarian regimes: What would current records say about you?
 The 2013 Turing Award goes to Leslie Lamport, author of LaTeX and the Paxos family of protocols
 The research program Univalent Foundations of Mathematics by the famed Vladimir Voevodsky is a really ambitious one: it would revolutionise automated theorem proving
 A mechanised proof of Fermat’s Little Theorem (HOL4)
 I have recently learnt that the beautiful books Proofs without Words I and Proofs without Words II by Roger B. Nelsen have an historical precedent from a more impressive mid19th century book: Oliver Byrne’s edition of Euclid.
 Understanding understanding source code with FMRI: how does the brain understands source code? What areas are involved? Thanks to this research, now we know:
I wonder how does this fit with another partiallyrelated publication, The Experience of Mathematical Beauty and its Neural Correlates: could wellstructured, clean code with idioms and patterns produce the same neural experience of beauty?
 Visual Programming Languages: quick glance over dozens of VPLs.
 Physically Based Rendering: From Theory to Implementation: the first computer book to be awarded an Oscar! And opensource!
 Node.js is the biggest innovation in web development in years: this comparison with Java gives a little insight on its performance improvements.
 Common types of trading algorithms: a list of trading algorithms, with source code and some benchmarking. The Quantopian community is growing fast!
 The Nature and Incidence of Software Piracy – Evidence from Windows 7: I’ve read many petty studies on software piracy, but this is the first wellresearch one.
 A History of Security Economics: an interesting perspective from the author of Security Engineering.
 From Berkeley, some good empirical studies on computer security: An Empirical Study of the Effectiveness of Security Code Review & An Empirical Study of Vulnerability Rewards Programs.
 French Team Invents Faster CodeBreaking Algorithm: I like the sincerity about the heuristics of the algorithm, even when the article is promotional.
 A Brief History of NSA Backdoors: and it’s indeed brief. There is so much the public doesn’t know about…
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.

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.

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 polylogarithmic algorithm: a theoretical advance with multiple nice applications in practice (routing, transportation, robotics…)

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

Automatic patch generation learned from humanwritten 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.

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

Pinocchio, Nearly Practical Veriﬁable 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.
 The library of George B. Dantzig is for sale: peering over the libraries of great mean is as enlightening as their work.
 Benford’s Law and the Art of Succeeding in Multiple Choice Tests: funny application of Benford’s Law.
 Polymath8: I’ve been following this project on collaborative mathematics and the article on Wired is a good description of its course.
 Rota’s conjecture proved: well, almost proved, there are some problems with the inequivalent representation of matroids, but it’s almost here.
 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).
 Amdahl’s Law vs. GustafsonBarsis’ Law: it contains an interesting insight on the impact of parallelization in relation to power consumption.
 Moore’s Law in Photonics: mass diffusion of photonics is nearer than anyone else could think of.
 Predicting the Path of Technological Innovation: this paper introduces a simple model that works quite well across markets.
 The Economics of LongTerm Digital Storage: comparison and forecast of the different storage technologies.
 Turing award goes to Goldwasser&Micali: zeroknowledge, semantic security and universal forgery under chosen message attack.
 The DDoS That Almost Broke the Internet: attacking whole Internet eXchanges just to bring down SpamHaus.
 Cybersecurity: The digital arms trade: price quotes for exploits, The Economist’s style.
 NSA Cryptologs: was this really classified? Many opinions and littletonone noteworthy facts.
 RC4 as used in TLS/SSL is broken: see page 306. More here.
 Basic Analysis of Entry and Exit in the US Broadband Market (20052008): broadband is a toobroad category.
 Margin Squeeze in the Telecommunications Sector: A More EconomicsBased Approach. An issue in which the European Union Competition Authorities are ahead of the US Supreme Court.
 An Empirical Analysis of the Demand for Fixed and Mobile Telecommunications Services. Mobile calls are more inelastic than local calls.
 Network effects, Customer Satisfaction and Recommendation on the Mobile Phone Market. Supplyside rule over demandside effects on the mobile market.
 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.
 Dynamic Graph Connectivity in Polylogarithmic Worst Case Time: simpler algorithm with many applications.
 Strongly Universal String Hashing is Fast: just 0.2 cycles per byte to achieve strong universality (implementation).
 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.
Archives
 September 2017
 February 2017
 April 2014
 March 2014
 December 2013
 November 2013
 July 2013
 April 2013
 March 2013
 February 2013
 January 2013
 December 2012
 November 2012
 October 2012
 September 2012
 August 2012
 July 2012
 June 2012
 May 2012
 March 2012
 February 2012
 January 2012
 December 2011
 November 2011
 October 2011
 August 2011
 July 2011
 June 2011
 May 2011
 April 2011
 March 2011
 February 2011
Blogroll
 ACM Queue
 Asymco
 Bentham's Gaze
 Bristol Cryptography Blog
 Computational Complexity
 Cryptographic Engineering
 ECRYPTEU
 Elliptic News
 ePrint IACR
 Financial Times Tech Blog
 Gödel's Lost Letter and P=NP
 IEEE Spectrum
 ImperialViolet
 InfoQ
 Jefferson's Wheel
 Lessons Learned
 Light Blue Touchpaper
 Marginal Revolution
 Musing on Markets
 Nature
 Nick Higham
 Outsourced Bits
 Quanta Magazine
 Renesys Blog
 Schneier on Security
 Science
 Telco 2.0
 The Economist
 The Leisure of the Theory Class
 The morning paper
 Tomasz Tunguz
 Turing’s Invisible Hand
 Unenumerated