A hitting-set generator (HSG) is a polynomial map Gen:\mathbb{F}^k \to \mathbb{F}^n such that for all n-variate polynomials Q of small enough circuit size and degree, if Q is non-zero, then Q\circ Gen is non-zero. In this paper, we give a new construction of such a HSG assuming that we have ... more >>>

In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree d polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can ... more >>>

The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold [Computational Complexity 2013]. In this paper, we show that improved bounds for DNF compression imply improved bounds ... more >>>

In a sequence of fundamental results in the 80's, Kaltofen showed that factors of multivariate polynomials with small arithmetic circuits have small arithmetic circuits. In other words, the complexity class VP is closed under taking factors. A natural question in this context is to understand if other natural classes of ... more >>>