4 citations · 7 across the 11 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
The PPSZ algorithm of Paturi, Pudlák, Saks, and Zane solves 3-SAT by processing the variables in a uniformly random order, setting a variable whenever a bounded number of clauses i…