### Abstract

In this paper we study the complexity of constructing a hitting set for VP, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given n, s, r in unary outputs a set of inputs from Q^{n} of size poly(n, s, r), with poly(n, s, r) bit complexity, that hits all n-variate polynomials of degree r that are the limit of size s algebraic circuits. Previously it was known that a random set of this size is a hitting set, but a construction that is certified to work was only known in EXPSPACE (or EXPH assuming the generalized Riemann hypothesis). As a corollary we get that a host of other algebraic problems such as Noether Normalization Lemma, can also be solved in PSPACE deterministically, where earlier only randomized algorithms and EXPSPACE algorithms (or EXPH assuming the generalized Riemann hypothesis) were known. The proof relies on the new notion of a robust hitting set which is a set of inputs such that any nonzero polynomial that can be computed by a polynomial size algebraic circuit, evaluates to a not too small value on at least one element of the set. Proving the existence of such a robust hitting set is the main technical difficulty in the proof. Our proof uses anti-concentration results for polynomials, basic tools from algebraic geometry and the existential theory of the reals.

Original language | English (US) |
---|---|

Title of host publication | STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Monika Henzinger, David Kempe, Ilias Diakonikolas |

Publisher | Association for Computing Machinery |

Pages | 87-99 |

Number of pages | 13 |

ISBN (Electronic) | 9781450355599 |

DOIs | |

State | Published - Jun 20 2018 |

Event | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: Jun 25 2018 → Jun 29 2018 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 |
---|---|

Country | United States |

City | Los Angeles |

Period | 6/25/18 → 6/29/18 |

### Keywords

- Algebraic circuits
- Arithmetic circuits
- Explicit construction
- Hitting-set
- PSPACE
- Polynomial identity testing

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'A PSPACE construction of a hitting set for the closure of small algebraic circuits'. Together they form a unique fingerprint.

## Cite this

*STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*(pp. 87-99). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3188745.3188792