Skip to main content
eScholarship
Open Access Publications from the University of California

Limits on the Pseudorandomness of Low-Degree Polynomials over the Integers

  • Author(s): Korb, Alexis Lei Wan
  • Advisor(s): Sahai, Amit
  • et al.
Abstract

We initiate the study of a problem called the Polynomial Independence Distinguishing Problem (PIDP). The problem is parameterized by a set of polynomials Q = (q_1, ... , q_m) of n variables and an input distribution D over the reals. The goal of the problem is to distinguish a tuple of the form {q_i, q_i(x)}_{i in [m]} from {q_i, q_i(x_i)}_{i in [m]} where x, x_1, ... , x_m are each sampled independently from the distribution D^n. Refutation and search versions of this problem are conjectured to be hard in general for polynomial time algorithms (Feige, STOC 02) and are also subject to known theoretical lower bounds for various hierarchies (such as Sum-of-Squares and Sherali-Adams). Nevertheless, we show polynomial time distinguishers for the problem in several scenarios, including settings where such lower bounds apply to the search or refutation versions of the problem.

Main Content
Current View