All reports by Author Chi-Ning Chou:

__
TR21-011
| 13th February 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy#### Classification of the streaming approximability of Boolean CSPs

Revisions: 1

__
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

__
TR18-052
| 16th March 2018
__

Chi-Ning Chou, Mrinal Kumar, Noam Solomon#### Some Closure Results for Polynomial Factorization and Applications

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal ... more >>>

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

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

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

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