{"id":1466,"date":"2014-04-10T17:33:15","date_gmt":"2014-04-10T15:33:15","guid":{"rendered":"http:\/\/cerezo.name\/blog\/?p=1466"},"modified":"2024-10-14T13:25:36","modified_gmt":"2024-10-14T11:25:36","slug":"assorted-links-algorithms-2","status":"publish","type":"post","link":"https:\/\/cerezo.name\/blog\/2014\/04\/10\/assorted-links-algorithms-2\/","title":{"rendered":"Assorted Links (Algorithms)"},"content":{"rendered":"<ul>\n<li style=\"text-align: justify;\"><a href=\"http:\/\/arxiv.org\/abs\/1311.2369\" target=\"_blank\" rel=\"noopener\">The Matching Polytope has Exponential Extension Complexity<\/a>. A perfect matching polytope cannot be written as a linear program with polynomially many constraints, only exponentially, so P!=<span class=\"caps\">NP<\/span> cannot be proven using these methods.<\/li>\n<li style=\"text-align: justify;\"><a href=\"http:\/\/math.mit.edu\/~kelner\/Publications\/Docs\/1304.2338v2.pdf\" target=\"_blank\" rel=\"noopener\" class=\"broken_link\">An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs<\/a>. 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.<\/li>\n<li style=\"text-align: justify;\"><a href=\"http:\/\/eccc.hpi-web.de\/report\/2013\/026\/\" target=\"_blank\" rel=\"noopener\">Arithmetic circuits: a chasm at depth three<\/a>. Any algebraic circuit can be expressed as depth\u20113 formulas of sub-exponential size.<\/li>\n<li style=\"text-align: justify;\"><a href=\"http:\/\/www.tara.tcd.ie\/bitstream\/2262\/67834\/1\/Stratus_v2.pdf\" target=\"_blank\" rel=\"noopener\" class=\"broken_link\">Stratus: Load Balancing the Cloud for Carbon Emissions Control<\/a>. Arbitrage between clouds and their physical locations will become so competitive that even electricity costs and their taxes will be priced on.<\/li>\n<\/ul>\n\n","protected":false},"excerpt":{"rendered":"<p>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!=<span class=\"caps\">NP<\/span> 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&nbsp;graph&nbsp;[\u2026]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"wp_typography_post_enhancements_disabled":false,"ngg_post_thumbnail":0},"categories":[18],"tags":[],"_links":{"self":[{"href":"https:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1466"}],"collection":[{"href":"https:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/comments?post=1466"}],"version-history":[{"count":2,"href":"https:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1466\/revisions"}],"predecessor-version":[{"id":1530,"href":"https:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/1466\/revisions\/1530"}],"wp:attachment":[{"href":"https:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/media?parent=1466"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/categories?post=1466"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/tags?post=1466"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}