3 papers
cs.DS2026
Polynomial-Time Singular Witnesses for Non-SNS Sign Patterns
Tao Jiang, Minbo Gao, Shaowei Cai
Sign-nonsingularity asks whether every real matrix with prescribed entry signs is nonsingular. Polynomial-time algorithms recognize square sign-nonsingular patterns through their c…
cs.DS2026
A Better Analysis For PPSZ For 3-SAT
Tao Jiang, Shaowei Cai
We revisit Scheder's analysis of the original PPSZ algorithm. Keeping his regular and irregular estimates unchanged, we express them in common structural coordinates and replace on…
cs.AI2024
Local Search for Integer Quadratic Programming
Xiang He, Peng Lin, Shaowei Cai
Integer Quadratic Programming (IQP) is an important problem in operations research. Local search is a powerful method for solving hard problems, but the research on local search al…