Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NOAM SOLOMON:
All reports by Author Noam Solomon:

TR19-065 | 1st May 2019
Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon

Derandomization from Algebraic Hardness: Treading the Borders

Revisions: 2

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 >>>


TR19-037 | 5th March 2019
Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Closure of VP under taking factors: a short and simple proof

Revisions: 1

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 >>>


TR19-028 | 1st March 2019
Shachar Lovett, Noam Solomon, Jiapeng Zhang

From DNF compression to sunflower theorems via regularity

Revisions: 1

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 >>>


TR18-052 | 16th March 2018
Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Some Closure Results for Polynomial Factorization and Applications

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 >>>




ISSN 1433-8092 | Imprint