Showing cs.DSShow all
2 papers · 1 filter
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…