1 citations · 1 across the 8 of their papers we have counts for
9 papers
Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensions
Tao Jiang, Minbo Gao, Shaowei Cai
Ganian et al. (ICLR 2026) proved that quantized neural network training is fixed-parameter tractable when parameterized jointly by architecture treewidth, input dimension , and…
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…
Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation
Tao Jiang, Minbo Gao, Shaowei Cai
A pointwise-unbiased one-bit compressor reconstructs every real input in expectation while transmitting one bit. For a scalar source with CDF , mean , and $\mathcal J(P)=…
Depth Enables Local Entropy: Quadratic Depth Dependence in Deep Variation-Norm ReLU Regression
Tao Jiang, Minbo Gao, Shaowei Cai
We study Gaussian regression over the explicit vector-valued Parhi--Nowak deep-RBV^2 architecture with depth L, width w, layer-sum variation budget A, and output bound B. For this…
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…
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…
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…
OPTDTALS: Approximate Logic Synthesis via Optimal Decision Trees Approach
Hao Hu, Shaowei Cai
The growing interest in Explainable Artificial Intelligence (XAI) motivates promising studies of computing optimal Interpretable Machine Learning models, especially decision trees.…
ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization
Zhihan Chen, Peng Lin, Hao Hu +1
As a broadly applied technique in numerous optimization problems, recently, local search has been employed to solve Pseudo-Boolean Optimization (PBO) problem. A representative loca…