2 papers
cs.LG2026
QuadraSHAP: -Exact Shapley Values for Product Games in Logarithmic Parallel Time
Majid Mohammadi, Grigory Reznikov, Pavel Sinitcyn +2
We introduce QuadraSHAP, a method for -exact Shapley computation in product games, cooperative games whose coalition values factorize across players. Given a tolerance ,…
cs.CC2023
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
Tatiana Belova, Alexander S. Kulikov, Ivan Mihajlin +3
The field of fine-grained complexity aims at proving conditional lower bounds on the time complexity of computational problems. One of the most popular assumptions, Strong Exponent…