The (proper-)learning or reconstruction problem for algebraic computation is the following algorithmic task. Given access to a black box computing a polynomial F, output a circuit computing F. It is called "proper-learning'' whenever the output circuit is expected to be of the "same type'' as the provided black box. This is evidently a harder problem than polynomial identity testing, and even designing an efficient, randomized reconstruction algorithm for highly structured circuit-models is a non-trivial task.
One such highly structured model is that of Read-once Oblivious ABPs (ROABPs for short), where efficient randomized reconstruction is possible, provided the algorithm is also given "the order'' of the ROABP; this is sometimes called the "grey-box'' setting. In this talk, we will explore the missing part of the question in the title: how hard is it to find the order of an ROABP in the black-box setting?
Based on a recent work with Vishwas Bhargava, Pranjal Dutta and Sumanta Ghosh.
