Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Designing Compact ILPs via Fast Witness Verification
MichaÅ WÅodarczyk
The standard formalization of preprocessing in parameterized complexity is given by kernelization. In this work, we depart from this paradigm and study a different type of preproce…
cs.DS2024
Does Subset Sum Admit Short Proofs?
MichaÅ WÅodarczyk
We investigate the question whether Subset Sum can be solved by a polynomial-time algorithm with access to a certificate of length poly(k) where k is the maximal number of bits in…