2 papers
cs.DS2026
Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model
Dani Dorfmann, Dani Dorfman, Simon Döring +5
If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs? Inspired by this question, we introduce a new computational model for…
cs.DS2026
The Classical Weisfeiler-Leman Algorithm Stabilizes in Rounds
Simon Döring, Daniel Neuen
The classical Weisfeiler-Leman algorithm (also known as the -dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuris…