אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

What is an optimal formula computing a given multivariate polynomial $f$? In this work, we show that this question admits an efficient algorithmic solution in an average-case sense.

Specifically, we consider the following situation. Let $\F$ be a field, $S \subseteq \F$ be a finite subset of field elements, $\vecX =(X_1, X_2, \ldots, X_n) $ be a tuple of formal variables and $\Delta \geq 0 $ be an integer representing the product-depth of the hidden (unknown) formula. In this work we define "a random formula" as one generated by the following process. If $\Delta=0$ then pick $(n+1)$ field elements $a_0, a_1, \ldots, a_n$ uniformly at random from $S$ and output a node labelled with the affine form $(a_0 + a_1 X_1 + a_2 X_2 + ... + a_n X_n)$. If $\Delta > 0$ then recursively pick four random subformulas $A,B,C$ and $D$ of product depth $(\Delta-1)$ each and output $(A \cdot B + C \cdot D)$. Thus it’s a binary formula which is layered with alternating layers of addition and multiplication gates and where the leaf nodes are labelled with affine forms over the variable set. We present a randomized algorithm that, given blackbox access to just the output polynomial $f$ of such a formula $\phi$, can efficiently reconstruct back (an equivalent) formula of the same size in time $\poly(n \cdot \size(\phi))$ and with the probability of success (over the random choice of $\phi$) being at least $\left( 1 - \frac{d^{O(1)}}{\abs{S}} \right)$.

This, then, is the strongest model of arithmetic computation for which a reconstruction algorithm is presently known, albeit efficient in a distributional sense rather than in the worst case. The main technical work involved in devising the above algorithm is understanding and characterizing the high-dimensional components of the singular locus of an arbitrary linear combination of (a few) random formulas.

(joint work with Neeraj Kayal, Youming Qiao)