2 papers
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…