43 citations · 99 across the 11 of their papers we have counts for
17 papers
Sketching Approximability of (Weak) Monarchy Predicates
Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi +2
We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals.…
Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
Xun Gao, Marcin Kalinowski, Chi-Ning Chou +3
Demonstrating quantum advantage requires experimental implementation of a computational task that is hard to achieve using state-of-the-art classical systems. One approach is to pe…
A Superconducting Nanowire-based Architecture for Neuromorphic Computing
Andres E. Lombo, Jesus E. Lares, Matteo Castellani +3
Neuromorphic computing is poised to further the success of software-based neural networks by utilizing improved customized hardware. However, the translation of neuromorphic algori…
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…
Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond
Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu +1
We introduce a notion of \emph{generic local algorithm} which strictly generalizes existing frameworks of local algorithms such as \emph{factors of i.i.d.} by capturing local \emph…
Linear Space Streaming Lower Bounds for Approximating CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +2
We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on variables taking values in $\{0…
Sketching approximability of all finite CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +1
A constraint satisfaction problem (CSP), , is specified by a finite set of constraints for positive int…
Approximability of all Boolean CSPs with linear sketches
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +1
In this work we consider the approximability of in the context of sketching algorithms and completely characterize the approximability of all Boolean CSPs. Sp…
A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
Chi-Ning Chou, Juspreet Singh Sandhu, Mien Brabeeba Wang +1
One of the challenges in analyzing learning algorithms is the circular entanglement between the objective value and the stochastic noise. This is also known as the "chicken and egg…
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…
(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
Boaz Barak, Chi-Ning Chou, Zhixian Lei +2
We give a quasipolynomial time algorithm for the graph matching problem (also known as noisy or robust graph isomorphism) on correlated random graphs. Specifically, for every …
Some Closure Results for Polynomial Factorization and Applications
Chi-Ning Chou, Mrinal Kumar, Noam Solomon
In a sequence of seminal results in the 80's, Kaltofen showed that the complexity class VP is closed under taking factors. A natural question in this context is to understand if ot…
On the Algorithmic Power of Spiking Neural Networks
Chi-Ning Chou, Kai-Min Chung, Chi-Jen Lu
Spiking Neural Networks (SNN) are mathematical models in neuroscience to describe the dynamics among a set of neurons that interact with each other by firing instantaneous signals,…