Dr. Anna Latour

Last week, I presented the work I did with prof. Kuldeep Meel and prof. Arunabha Sen at IJCAI 2023.

We showed the benefits of reducing a problem to a computationally harder problem (yes, you read that right!), by demonstrating how it allows us to solve much larger problem instances.

It was so much fun to finally share this work with so many fantastic researchers at IJCAI! Thank you to all organisers for making this conference possible. I'm also super grateful to the reviewers who gave us great feedback!

Please find our paper, slides, poster, a short video, and our open source tool, gismo, here: www.annalatour.nl/publication/2023-08-01-Solving-the-Identifying-Code-Set-Problem-with-Grouped-Independent-Support

#IJCAI2023 #IJCAI #AcademicMastodon #FOSS #PostdocLife #ConstraintProgramming #BooleanSatisfiability #Complexity #AcademicChatter #OpenSource #OpenSourceSoftware

Aug 26, 2023 at 1:31pmWeb
Show threadNils Goroll 🕊️Aug 26, 2023
@anna thank you for sharing. I have not devoured the material, but I just wanted to mention that "reducing to a harder problem" is something we do all the time, even in simple cases like turning a list into a tree or a hashmap.
Show threadDr. Anna LatourAug 27, 2023

@slink Hi Nils, are you referring to things like knowledge compilation? For example, taking information in one form (e.g., CNF), and compiling it into another datastructure (e.g., ROBDD), and in return get the ability to perform certain queries/operations in a tractable manner on the new datastructure?

If yes, I would say that what we are doing is somewhat orthogonal to that.

The representation starts out as a mathematical one, and we have to encode it into some kind of machine-readable input to solve it. In the former SotA, the number of linear constraints in the ILP grows (roughly) exponentially, whereas in our approach, the number of clauses in the CNF grows linearly. Hence, we don't have to spend extra computational effort to obtain our encoding.

Show threadNils Goroll 🕊️Aug 27, 2023
@anna @anna @anna thank you for your response, i have read your paper again and having almost no knowledge in your field i now think that my comment might not have been appropriate.
i was only referring to the statement in your post about the fact that a computationally harder algorithm allows to increase the problem size due to a more efficient encoding. to me this sounds like a classical time/space tradeoff.
Show threadDr. Anna LatourAug 27, 2023

@slink Thanks for clarifying and for asking the question! :)

Yes, that is true!

Another example would be predicate logic versus propositional logic. Predicate logic allows you to express certain problems a lot more compactly.

However, just because on a high level, our reduction is an example of classical time/space tradeoff, that doesn't make our contribution trivial or uninteresting.

The problem that we study is 25 years old, and there are still papers being published that study it. The problem that we reduce it to is quite esoteric and has so far only been used as a preprocessing step for another problem. I think it's kinda cool that we show that it can be used directly to model and solve real-world combinatorial optimisation problems.

On top of that: the tradeoff is only useful if you have the tools to actually solve the computationally harder problem. Thanks to the enormous progress made by the SAT community in creating SAT solvers that are very fast in practice (like CryptoMiniSAT by @msoos, which we use in our work), we were able to create such a tool.

Therefore, I think that our work also demonstrates that we are making concrete progress towards creating useful tools in the "Beyond NP" realm, and solving the associated problems. I think it would be very cool if we could continue this momentum and identify other such reductions that help us solve concrete problems :)

(Sorry for the TED talk, you caught me at the end of a very long week of endlessly talking about this work 😅 )

Show threadNils Goroll 🕊️Aug 27, 2023
@anna @msoos i do very much appreciate your detailed answer and i hope to understand the significance of your work at least superficially (otherwise i would not have looked at it in the first place). thank you so much for taking the time to respond to a noob stranger from outside your bubble!
Show threadDr. Anna LatourAug 27, 2023
@slink My pleasure :)
Very happy that somebody is asking questions, and it helps me think about the context of our work and how to frame it :)