4 citations · 4 across the 1 of their papers we have counts for
9 papers
Quantum Meets the Minimum Circuit Size Problem
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang +1
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…
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
Boaz Barak, Chi-Ning Chou, Xun Gao
The linear cross-entropy benchmark (Linear XEB) has been used as a test for procedures simulating quantum circuits. Given a quantum circuit with inputs and outputs and purp…
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT
Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy
We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an…
ODE-Inspired Analysis for the Biological Version of Oja's Rule in Solving Streaming PCA
Chi-Ning Chou, Mien Brabeeba Wang
Oja's rule [Oja, Journal of mathematical biology 1982] is a well-known biologically-plausible algorithm using a Hebbian-type synaptic update rule to solve streaming principal compo…
Closure of VP under taking factors: a short and simple proof
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 variate degree $…
Tracking the Norm with Constant Update Time
Chi-Ning Chou, Zhixian Lei, Preetum Nakkiran
The \emph{ tracking problem} is the task of obtaining a streaming algorithm that, given access to a stream of items from a universe , outputs at e…