2 citations · 3 across the 14 of their papers we have counts for
5 papers · 1 filter
Almost Optimal FPT Inapproximability for k-SetCover
Venkatesan Guruswami, Xuandi Ren
We show that -approximate parameterized -SetCover is W[1]-hard, and has no -time algorithms under ETH. This improves upon…
Inapproximability of Unique-Machine Precedence Scheduling for Unit-Length Jobs
Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang
The Unique-Machine Precedence Scheduling (UMPS) problem, introduced by [DKRSTZ22], seeks a makespan-minimizing schedule of precedence-constrained jobs when each job has a unique el…
On the Approximability of Parameterized Minimum Monotone Satisfying Assignment
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +1
The parameterized Minimum Monotone Satisfying Assignment (-MMSA) problem asks whether a monotone Boolean circuit admits a satisfying assignment of Hamming weight at most . Th…
Strong Inapproximability for a Promise Rank Problem
Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang
Given a linear subspace of matrices over that is promised to contain a matrix of rank , we prove that it is hard to find a matrix of rank $n^{o(1/…
Scaling Reasoning Tokens via RL and Parallel Thinking: Evidence From Competitive Programming
Qianfan Zhang, Tianyu Guo, Xuandi Ren +4
We study how to scale reasoning token budgets for competitive programming through two complementary approaches: training-time reinforcement learning (RL) and test-time parallel thi…