# 'meet in the middle' combined with Dynamic Programming for subset sum

What is the reason why nobody has combined the 'meet in the middle' approach with the Dynamic Programming for subset sum?

I found it curious that is a kind of a open problem.. as a matter of fact I never have seen both them combined.

On a paper (1), the author questions if by their combination would be possible to obtain an algorithm with time complexity $O(T^{1/2}*n^{O(1)})$.

Is that time complexity something reasonable?

Could it get better or worse than the above estimation?

(1) SETH-Based Lower Bounds for Subset Sum and Bicriteria Path, Amir Abboud et al. arXiv:1704.04546

• I think that in the first sentence you mean "nobody" rather than "anybody". – Yuval Filmus Nov 26 '17 at 12:25
• Perhaps people have tried and failed? – Yuval Filmus Nov 26 '17 at 12:25
• (edited the question to correct my mistake) – John Seppard Nov 26 '17 at 18:49
• @Yuval perhaps, another possibility, is , if somebody found how to do it, that the final time complexity was not the one expected, do this count as a failure? – John Seppard Nov 26 '17 at 19:45
• Any improvement on the state-of-the-art would have been published. That's how our community works. – Yuval Filmus Nov 26 '17 at 20:31