Interesting work! We definitely need far better inference models in computational biology than what we currently have. I agree with your paper that modeling is unfortunately more of an "art" than a science nowadays... and with huge societal consequences.

Having said that, on a cursory read I think you may be misapplying Valiant's algorithm...

In particular, the original (union bound) PAC guarantee relies crucially on IID samples, so you cannot straightforwardly apply it to time series data and expect the guarantee to hold unchanged. Instead, you should use block bootstrap methods to sample consecutive segments of your time series of a certain size --in which case a (possibly weaker) PAC-like guarantee might hold, provided the dependence across time decays sufficiently fast [1].

I'm also a bit concerned about the semantics of your approach, since I thought gene regulatory inference was/is notoriously intractable, and Valiant's model is very stringent and conservative... So IMO somewhere along the line you are getting a massive free lunch simply by reducing to k-CNF!

Not saying it's wrong per se of course; but I couldn't easily tell exactly where the 'trick' is... So if I were you I would try to communicate more clearly (to dumb non-experts like me) how exactly this particular reduction captures something highly non-trivial in gene regulatory networks to achieve such a (seemingly) drastic speedup..

[1] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4551412/

--