{"id":3057,"date":"2025-11-13T16:43:33","date_gmt":"2025-11-13T14:43:33","guid":{"rendered":"https:\/\/mathematics.haifa.ac.il\/?p=3057"},"modified":"2025-11-19T11:51:54","modified_gmt":"2025-11-19T09:51:54","slug":"colloquium-tuesday-nov-18-2025-1400-room-614-speaker-gideon-amir-bar-ilan-title-convergence-rate-of-lp-energy-minimization-on-graphs","status":"publish","type":"post","link":"https:\/\/mathematics.haifa.ac.il\/?p=3057","title":{"rendered":"Colloquium: Tuesday Nov. 18, 2025 (14:00, room 614). Speaker: Gideon Amir (Bar Ilan). Title: &#8220;Convergence rate of l^p-energy minimization on graphs&#8221;."},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Abstract:&nbsp;We consider the following dynamics on a connected graph (V,E) with n vertices. Given p&gt;1 and an initial opinion profile f_0: V \\to [0,1], at each integer step t &gt;= 1 a uniformly random vertex v=v_t is selected, and the opinion there is updated to the value f_{t}(v) that minimizes the sum \\sum_{w \\sim v} |f_t(v)-f_{t-1}(w)|^p taken over all neighbours w of v. The case p=2 yields linear averaging dynamics, but for all p \\ne 2 the dynamics are nonlinear. In the limiting case p=\\infty (known as <em>Lipschitz learning<\/em>), f_t(v) is the average of the largest and smallest values of f_{t-1}(w) among the neighbours w of v. We show that the number of steps needed to reduce the oscillation of f_t below epsilon is at most n^{beta_p} (up to logarithmic factors in n and epsilon), where beta_p=\\max(\\frac{2p}{p-1},3); we prove that the exponent beta_p is optimal. The phase transition at p=3 is a new phenomenon. We also derive matching upper and lower bounds for convergence time as a function of n and the average degree; these are the most challenging to prove.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Joint work with Fedor Nazarov and Yuval Peres.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Abstract:&nbsp;We consider the following dynamics on a connected graph (V,E) with n vertices. Given p&gt;1 and an initial opinion profile f_0: V \\to [0,1], at each integer step t &gt;= 1 a uniformly random vertex v=v_t is selected, and the&#8230;<br \/><a class=\"read-more-button\" href=\"https:\/\/mathematics.haifa.ac.il\/?p=3057\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-3057","post","type-post","status-publish","format-standard","hentry","category-colloquium"],"_links":{"self":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/3057","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3057"}],"version-history":[{"count":1,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/3057\/revisions"}],"predecessor-version":[{"id":3058,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=\/wp\/v2\/posts\/3057\/revisions\/3058"}],"wp:attachment":[{"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3057"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3057"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathematics.haifa.ac.il\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3057"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}