All reports by Author Chi-Ning Chou:

__
TR22-068
| 5th May 2022
__

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy#### Sketching Approximability of (Weak) Monarchy Predicates

Revisions: 1

__
TR21-116
| 10th August 2021
__

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang#### Quantum Meets the Minimum Circuit Size Problem

Revisions: 1

__
TR21-086
| 22nd June 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy#### Linear Space Streaming Lower Bounds for Approximating CSPs

Revisions: 1

__
TR21-063
| 3rd May 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy#### Approximability of all finite CSPs in the dynamic streaming setting

Revisions: 3

__
TR21-011
| 13th February 2021
__

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

Revisions: 4
,
Comments: 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, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy

We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first ... more >>>

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang

In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory---its hardness is mysterious, and a better understanding of its hardness can have ... more >>>

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

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints. We also identify ... more >>>

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

A constraint satisfaction problem (CSP), Max-CSP$({\cal F})$, is specified by a finite set of constraints ${\cal F} \subseteq \{[q]^k \to \{0,1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from ${\cal F}$ to subsequences of the $n$ ... more >>>

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