From assumption to algorithmic limits

Where ETH-based lower bounds appear

ETH connects SAT’s presumed difficulty to conditional limits for other problems.

Where ETH-based lower bounds appear Three-SAT hardness and reductions lead to conditional lower bounds in graph algorithms, computational geometry, and other fields. If ETH is refuted, the affected arguments must be revisited, but faster algorithms do not follow automatically. 3-SAT on n variables the source problem ETH + a reduction “If 3-SAT needs exponential time, then this target task has a runtime limit.” Graph algorithms treewidth · treedepth exact and approximate algorithms Computational geometry Earth Mover’s Distance dimension-dependent complexity Other fields databases · computational biology many ETH-conditioned results If ETH is refuted Recheck each ETH-dependent proof. A faster algorithm for every target does not follow. CONDITIONAL LOWER BOUNDS ARE THEORETICAL LIMITS, NOT BENCHMARKS