Recent searches
Search options
I wrote up a little article about a problem that shows up in homomorphic encryption called "cheapest shift network" https://www.jeremykun.com/2024/09/02/shift-networks/
Homomorphic encryption is absolute magic.
@rk well this subproblem is relatively banal :) but somehow it has nerd sniped me.
@j2kun When I implemented a Beneš routing solver (for 64-bit bit-permutations) I read some papers, gave up, and threw it at a SAT solver. That worked well (in a single SAT solve, no looping for counter-examples required), and also generalized to other sequences of shift-distances (with non-power-of-two distances). I wasn't trying to optimize for cost but I could have put a constraint on cost and binary-searched for the minimum satisfiable cost
@harold do you think that'd scale to length-65536 permutations? That's like the biggest of what I'm looking at needing to support
@j2kun I don't know, it's a large step up. Going by memory, some 64 element instances solved nearly instantly and some took almost a second. Based on that I expect that some 64k instances can be solved in a reasonable amount of time and some cannot, with the time for easy cases scaling nearly linearly in their size (if it even makes sense to talk about cases scaling up) and the time for hard cases scaling much worse
@harold well if your code is open source please post a link, I'd love to check it out