Chi-Ning Chou | DeepAI

DeepAI AI Chat

Featured Co-authors

Mrinal Kumar
27 publications
Preetum Nakkiran
27 publications
Madhu Sudan
27 publications
Tselil Schramm
23 publications
Ruizhe Zhang
22 publications
Alexander Golovnev
21 publications
Boaz Barak
20 publications
Kai-Min Chung
18 publications
Tiancheng Yu
14 publications
Ameya Velingker
14 publications
Nai-Hui Chia
13 publications

∙ 05/04/2022

Sketching Approximability of (Weak) Monarchy Predicates

We analyze the sketching approximability of constraint satisfaction prob...

0 Chi-Ning Chou, et al. ∙

∙ 12/03/2021

Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage

Demonstrating quantum advantage requires experimental implementation of ...

0 Xun Gao, et al. ∙

∙ 08/13/2021

Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond

Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019], we stu...

0 Chi-Ning Chou, et al. ∙

∙ 08/06/2021

Quantum Meets the Minimum Circuit Size Problem

In this work, we initiate the study of the Minimum Circuit Size Problem ...

0 Nai-Hui Chia, et al. ∙

∙ 06/24/2021

Linear Space Streaming Lower Bounds for Approximating CSPs

We consider the approximability of constraint satisfaction problems in t...

0 Chi-Ning Chou, et al. ∙

∙ 05/03/2021

Approximability of all finite CSPs in the dynamic streaming setting

A constraint satisfaction problem (CSP), Max-CSP( F), is specified by a ...

0 Chi-Ning Chou, et al. ∙

∙ 02/24/2021

Approximability of all Boolean CSPs in the dynamic streaming setting

A Boolean constraint satisfaction problem (CSP), Max-CSP(f), is a maximi...

0 Chi-Ning Chou, et al. ∙

∙ 06/11/2020

A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms

We present a general framework for analyzing high-probability bounds for...

0 Chi-Ning Chou, et al. ∙

∙ 05/05/2020

Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits

The linear cross-entropy benchmark (Linear XEB) has been used as a test ...

0 Boaz Barak, et al. ∙

∙ 04/24/2020

Optimal Streaming Approximations for all Boolean Max-2CSPs

We prove tight upper and lower bounds on approximation ratios of all Boo...

0 Chi-Ning Chou, et al. ∙

∙ 11/04/2019

ODE-Inspired Analysis for the Biological Version of Oja's Rule in Solving Streaming PCA

Oja's rule [Oja, Journal of mathematical biology 1982] is a well-known b...

0 Chi-Ning Chou, et al. ∙

∙ 03/06/2019

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

In this note, we give a short, simple and almost completely self contain...

0 Chi-Ning Chou, et al. ∙

∙ 07/17/2018

Tracking the ℓ_2 Norm with Constant Update Time

The ℓ_2 tracking problem is the task of obtaining a streaming algorithm ...

0 Chi-Ning Chou, et al. ∙

∙ 07/09/2018

Personalized Difficulty Adjustment for Countering the Double-Spending Attack in Proof-of-Work Consensus Protocols

Bitcoin is the first secure decentralized electronic currency system. Ho...

0 Chi-Ning Chou, et al. ∙

∙ 05/07/2018

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

We give a quasipolynomial time algorithm for the graph matching problem ...

0 Boaz Barak, et al. ∙

∙ 03/28/2018

On the Algorithmic Power of Spiking Neural Networks

Spiking Neural Networks (SNN) are mathematical models in neuroscience to...

0 Chi-Ning Chou, et al. ∙

∙ 03/15/2018

Some Closure Results for Polynomial Factorization and Applications

In a sequence of seminal results in the 80's, Kaltofen showed that the c...

0 Chi-Ning Chou, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world