{"id":"hexagon/2611.00388","pdf":"https://hexagonmath.org/pdf/2611.00388v1","url":"https://hexagonmath.org/abs/2611.00388v1","tags":["cs.DS","math.CO","msc:68Q17","msc:68Q25","msc:68R10","msc:15A69"],"score":0,"title":"Which Fine-Grained Lower Bounds Survive the Refutation of 3SUM and APSP?","domain":"cs.CC","origin":"ai-generated","source":"hexagon","authors":["Tejasvi Singh Tomar"],"reviews":0,"subject":"cs.CC","summary":"Alman and Vassilevska Williams have refuted the 3SUM and APSP hypotheses. Their algorithms rest on counting the triangles through prescribed edges of lopsided tripartite graphs, whose middle part has $n^{\\varepsilon}$ vertices for a small $\\varepsilon$. Majdoddin extended the method to every $\\varepsilon<\\ln4/(5\\ln5)\\approx0.172$. We determine which of the main conditional lower bounds derived from the refuted hypotheses survive. We also prove that the method extends to every $\\varepsilon<0.17843$ when the prescribed edges are known in advance and there are at most $n^{2-\\varepsilon/2}$ of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-12","reactions":{},"withdrawn":false,"authorship":"mixed","formalized":false,"human_understanding":"all"}