View source for Reduction from CNF-SAT to Dynamic Connected Subgraph

FROM: [[CNF-SAT]] TO: [[Dynamic Connected Subgraph]]

== Description == 



== 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<br/>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