Reduction from CNF-SAT to

FROM: CNF-SAT TO: #SSR

Implications

if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing
then: SETH is false

Year

2014

Reference

Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 434-443. IEEE, 2014.

https://ieeexplore.ieee.org/abstract/document/6979028?casa_token=daaoBjrHUa4AAAAA:DCjk_WMWZ5Is6KvGpmS8a2bL9LskvV0P1zEG4U2u-Tm_C8sixu1w65OpTyjml1HEpaikXhtYsg