3 papers
cs.DS2026
From Dynamic Programs to Greedy Algorithms
Dieter van Melkebeek
We show for several computational problems how classical greedy algorithms for special cases can be derived in a simple way from dynamic programs for the general case: interval sch…
cs.CC2025
Polynomial Identity Testing via Evaluation of Rational Functions
Ivan Hu, Dieter van Melkebeek, Andrew Morgan
We introduce a hitting set generator for Polynomial Identity Testing based on evaluations of low-degree univariate rational functions at abscissas assoc…
cs.DS2024
Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees
Ivan Hu, Dieter van Melkebeek, Andrew Morgan
Given a rooted tree and a ranking of its leaves, what is the minimum number of inversions of the leaves that can be attained by ordering the tree? This variation of the problem of…