- 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.
Assorted Links (Algorithms)
Leave a reply