1 citations · 1 across the 8 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
The Exact Approximation Ratio of the Optimal Fixed-Price Mechanism in Bilateral Trade
Tao Jiang, Minbo Gao, Shaowei Cai
In bilateral trade, a seller owns an item that a buyer may value more, and their values are drawn independently from known distributions. A fixed-price mechanism posts a single pri…
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…