## תקציר

Randomizing polynomials represent a function f(x) by a low-degree randomized mapping p(x, r) over a finite field F such that, for any input x, the output distribution of p(x, r) depends only on the value of f(x). We study the class of functions f which admit an efficient representation by constant-degree randomizing polynomials. It is known that this class contains NC ^{1} as well as log-space classes contained in NC ^{2}. Whether it contains all polynomial-time computable functions is a wide open question. A positive answer would have major and unexpected consequences, including the existence of efficient constant-round multiparty protocols with unconditional security, and the equivalence of (polynomial-time) cryptography and cryptography in NC ^{0}. We obtain evidence for the limited power of randomizing polynomials by showing that a useful subclass of constant-degree randomizing polynomials cannot efficiently capture functions beyond NC. Concretely, we consider randomizing polynomials over fields F of a small characteristic in which each monomial has degree (at most) 2 in the random inputs r and constant degree in x. This subclass captures most constructions of randomizing polynomials from the literature. Our main result is that all functions f which can be efficiently represented by such randomizing polynomials over fields of a small characteristic are in non-uniform NC. (The same holds over arbitrary fields given a quadratic residuosity oracle.) This result is obtained in two steps: (1) we observe that computing f as above reduces to counting roots of degree-2 multivariate polynomials; (2) we design parallel algorithms for the latter problem. These parallel root counting algorithms may be of independent interest. On the flip side, our main result provides an avenue for obtaining new parallel algorithms via the construction of randomizing polynomials. This gives an unexpected application of cryptography to algorithm design. We provide several examples for the potential usefulness of this approach.

שפה מקורית | אנגלית |
---|---|

כותר פרסום המארח | ITCS 2012 - Innovations in Theoretical Computer Science Conference |

עמודים | 76-89 |

מספר עמודים | 14 |

מזהי עצם דיגיטלי (DOIs) | |

סטטוס פרסום | פורסם - 2012 |

פורסם באופן חיצוני | כן |

אירוע | 3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 - Cambridge, MA, ארצות הברית משך הזמן: 8 ינו׳ 2012 → 10 ינו׳ 2012 |

### סדרות פרסומים

שם | ITCS 2012 - Innovations in Theoretical Computer Science Conference |
---|

### כנס

כנס | 3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 |
---|---|

מדינה/אזור | ארצות הברית |

עיר | Cambridge, MA |

תקופה | 8/01/12 → 10/01/12 |