3 papers
cs.DS2022
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…
cs.CC2022
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…
math.LO1998
Separating complexity classes using autoreducibility
Harry Buhrman, Lance Fortnow, Leen Torenvliet +1
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hie…