118 citations · 126 across the 9 of their papers we have counts for
10 papers
Strong Refutation for Random Quantum 3-SAT at Constant Density
Siu On Chan, Jeff Xu
We give a classical polynomial-time algorithm that strongly refutes random quantum -SAT at sufficiently large constant constraint density, thereby disproving the quantum analogu…
Strongly Refuting Random CSP without Literals
Siu On Chan, Tommaso d'Orsi, Jeff Xu
Under what condition is a random constraint satisfaction problem hard to refute by the sum-of-squares (SoS) algorithm? A sufficient condition is t-wise uniformity, that is, each co…
Rethinking Graph Neural Networks for the Graph Coloring Problem
Wei Li, Ruxuan Li, Yuzhe Ma +3
Graph coloring, a classical and critical NP-hard problem, is the problem of assigning connected nodes as different colors as possible. However, we observe that state-of-the-art GNN…
The Gambler's Problem and Beyond
Baoxiang Wang, Shuai Li, Jiajin Li +1
We analyze the Gambler's problem, a simple reinforcement learning problem where the gambler has the chance to double or lose the bets until the target is reached. This is an early…
On the Worst-Case Approximability of Sparse PCA
Siu On Chan, Dimitris Papailiopoulos, Aviad Rubinstein
It is well known that Sparse PCA (Sparse Principal Component Analysis) is NP-hard to solve exactly on worst-case instances. What is the complexity of solving Sparse PCA approximate…
Random Walks and Evolving Sets: Faster Convergences and Limitations
Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau
Analyzing the mixing time of random walks is a well-studied problem with applications in random sampling and more recently in graph partitioning. In this work, we present new analy…