User contributions for Admin

15 February 2023

• 11:2711:27, 15 February 2023 diff hist 0‎ N File:Kth Order Statistic - Time.png ‎No edit summary
• 11:2711:27, 15 February 2023 diff hist 0‎ N File:Graph Coloring - 4-Graph Coloring - Pareto Frontier.png ‎No edit summary current
• 11:2711:27, 15 February 2023 diff hist 0‎ N File:Shortest Path (Directed Graphs) - Nonnegative Weights - Time.png ‎No edit summary
• 11:2711:27, 15 February 2023 diff hist 0‎ N File:Line segment intersection - Reporting all intersection points, line segments - Space.png ‎No edit summary current
• 11:2711:27, 15 February 2023 diff hist 0‎ N File:Matrix Chain Multiplication - Space.png ‎No edit summary current
• 11:2711:27, 15 February 2023 diff hist 0‎ N File:Lowest Common Ancestor - Off-Line Lowest Common Ancestor - Pareto Frontier.png ‎No edit summary current
• 11:2711:27, 15 February 2023 diff hist 0‎ N File:Graph Coloring - 3-Graph Coloring - Time.png ‎No edit summary
• 11:2711:27, 15 February 2023 diff hist 0‎ N File:Link Analysis - Space.png ‎No edit summary current
• 11:2711:27, 15 February 2023 diff hist 0‎ N File:Page Replacements - Online - Space.png ‎No edit summary current
• 11:2711:27, 15 February 2023 diff hist 0‎ N File:Dependency Inference Problem - Multivalued Dependency Inference Problem - Pareto Frontier.png ‎No edit summary current
• 11:2711:27, 15 February 2023 diff hist 0‎ N File:All Permutations - Time.png ‎No edit summary
• 11:1911:19, 15 February 2023 diff hist +102‎ N Reduction from OV to k-OV ‎ Created page with "FROM: OV TO: k-OV == Description == == Implications == == Year == == Reference =="
• 11:1911:19, 15 February 2023 diff hist +104‎ N Reduction from 3-OV to k-OV ‎ Created page with "FROM: 3-OV TO: k-OV == Description == == Implications == == Year == == Reference =="
• 11:1911:19, 15 February 2023 diff hist +619‎ N Reduction from Max-Weight K-Clique to Weighted Depth ‎ Created page with "FROM: Max-Weight K-Clique TO: Weighted Depth == Description == == Implications == if: to-time: $O(n^{\lfloor d/{2}\rfloor-\epsilon})$ for $N$ weighted axis-parallel boxes in $\mathbb{R}^d$<br/>then: from-time: $O(n^{k-{2}\epsilon})$ on $n$ vertex graphs for $k=d$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata,..." current
• 11:1911:19, 15 February 2023 diff hist +623‎ N Reduction from Max-Weight k-Clique to Maximum Subarray ‎ Created page with "FROM: Max-Weight k-Clique TO: Maximum Subarray == Description == == Implications == if: to-time: $O(n^{d+\lfloor d/{2}\rfloor-\epsilon})$ for $d$-dimensional hypercube arrays<br/>then: from-time: $O(n^{k-\epsilon})$ on $n$ vertex graphs for $k=d+\lfloor d/{2}\rfloor$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automa..." current
• 11:1911:19, 15 February 2023 diff hist +596‎ N Reduction from Max-Weight K-Clique to Maximum Square Subarray ‎ Created page with "FROM: Max-Weight K-Clique TO: Maximum Square Subarray == Description == == Implications == if: to-time: $O(n^{d+{1}-\epsilon})$ for $d$-dimensional hypercube arrays<br/>then: from-time: $O(n^{k-\epsilon})$ on $n$ vertex graphs for $k=d+{1}$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Languages, and Programm..." current
• 11:1911:19, 15 February 2023 diff hist +572‎ N Reduction from Weighted, Undirected APSP to 2D Maximum Subarray ‎ Created page with "FROM: Weighted, Undirected APSP TO: 2D Maximum Subarray == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ on $n\times n$ matrices<br/>then: from-time: $O(n^{3-\epsilon/{1}0})$ on $n$ vertex graphs == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Vol. 5..." current
• 11:1911:19, 15 February 2023 diff hist +569‎ N Reduction from Negative Triangle Detection to 2D Maximum Subarray ‎ Created page with "FROM: Negative Triangle Detection TO: 2D Maximum Subarray == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ on $n\times n$ matrices<br/>then: from-time: $O(n^{3-\epsilon})$ on $n$ vertex graphs == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Vol. 55...." current
• 11:1911:19, 15 February 2023 diff hist +616‎ N Reduction from Max-Weight k-Clique to Max-Weight Rectangle ‎ Created page with "FROM: Max-Weight k-Clique TO: Max-Weight Rectangle == Description == == Implications == if: to-time: $O(N^{d-\epsilon})$ on $N$ weighted points in $d$ dimensions<br/>then: from-time: $O(n^{k-\epsilon})$ on $n$ vertices, where $k=\lceil d^{2}\epsilon^{-1}\rceil$ == Year == 2016 == Reference == Backurs, Arturs, Nishanth Dikkala, and Christos Tzamos. "Tight Hardness Results for Maximum Weight Rectangles}}." 43rd International Colloquium on Automata, Lan..." current
• 11:1911:19, 15 February 2023 diff hist +701‎ N Reduction from Bichromatic Hamming Close Pair to Approximate Hard-Margin SVM ‎ Created page with "FROM: Bichromatic Hamming Close Pair TO: Approximate Hard-Margin SVM == Description == == Implications == assume: SETH<br/>then: let $k(a,a')$ be the Gaussian kernel with $C={100}\log n$ and let $\epsilon = \exp(-\omega(\log^{2} n))$, then approximating the optimal value of target within multiplicative factor ${1}+\epsilon$ requires almost quadratic time. == Year == 2017 == Reference == Backurs, A., Indyk, P., & Schmidt, L. (2017). On the fine-graine..." current
• 11:1911:19, 15 February 2023 diff hist +18‎ Reduction from Maximum Inner Product Search to Stable Pair Checking ‎No edit summary
• 11:1911:19, 15 February 2023 diff hist +623‎ N Reduction from Maximum Inner Product Search to Stable Pair Checking ‎ Created page with "FROM: Maximum Inner Product Search TO: Stable Pair Checking == Description == == Implications == assume: OVH<br/>then: for any $\epsilon > {0}$, there is a $c$ such that determining whether a given pair is part of any or all stable matchings in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon})$ == Year == 2016 == Reference == Moeller, Daniel, Ramamohan Paturi, and Stefan Schneider. "Subquadratic algor..."
• 11:1911:19, 15 February 2023 diff hist +585‎ N Reduction from Maximum Inner Product Search to Stable Matching Verification ‎ Created page with "FROM: Maximum Inner Product Search TO: Stable Matching Verification == Description == == Implications == assume: OVH<br/>then: for an $\epsilon > {0}$ there is a $c$ such that verifying a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon}). == Year == 2016 == Reference == Moeller, Daniel, Ramamohan Paturi, and Stefan Schneider. "Subquadratic algorithms for succinct stable matching." I..." current
• 11:1911:19, 15 February 2023 diff hist +591‎ N Reduction from Maximum Inner Product Search to Boolean d-Attribute Stable Matching ‎ Created page with "FROM: Maximum Inner Product Search TO: Boolean d-Attribute Stable Matching == Description == == Implications == assume: OVH<br/>then: for an $\epsilon > {0}$ there is a $c$ such that finding a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon})$. == Year == 2016 == Reference == Moeller, Daniel, Ramamohan Paturi, and Stefan Schneider. "Subquadratic algorithms for succinct stable matchi..." current
• 11:1911:19, 15 February 2023 diff hist +590‎ N Reduction from OV to Disjunctive Queries of Safety in Graphs ‎ Created page with "FROM: OV TO: Disjunctive Queries of Safety in Graphs == Description == == Implications == assume: OVH<br/>then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1 - \epsilon})$ algorithm for any $\epsilon > {0}$ for disjunctive safety ovjectives/queries in MDPs. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction." Proceedings of the 31s..." current
• 11:1911:19, 15 February 2023 diff hist +566‎ N Reduction from OV to Disjunctive Queries of Reachability in MDPs ‎ Created page with "FROM: OV TO: Disjunctive Queries of Reachability in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for target. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction is harder than conjunction." Proceedings of the 31st Annual ACM/IEEE Sympos..."
• 11:1911:19, 15 February 2023 diff hist +642‎ N Reduction from Triangle Detection to Disjunctive Queries of Safety in Graphs ‎ Created page with "FROM: Triangle Detection TO: Disjunctive Queries of Safety in Graphs == Description == == Implications == assume: Strong Triangle<br/>then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k \cdot n^{2})^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for disjunctive safety (objectives or queries) in graphs. == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds: Disjunction..." current
• 11:1911:19, 15 February 2023 diff hist +653‎ N Reduction from Triangle Detection to Disjunctive Queries of Reachability in MDPs ‎ Created page with "FROM: Triangle Detection TO: Disjunctive Queries of Reachability in MDPs == Description == == Implications == assume: Strong Triangle<br/>then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k \cdot n^{2})^{1-\epsilon})$ algorithm for any $\epsilon > {0}$ for target. The bounds holf for dense MDPs with $m=\Theta(n^{2})$ == Year == 2016 == Reference == Chatterjee, Krishnendu, et al. "Model and objective separation with conditional lower bounds:..." current
• 11:1911:19, 15 February 2023 diff hist +678‎ N Reduction from OV to Generalized Büchi Games ‎ Created page with "FROM: OV TO: Generalized Büchi Games == Description == == Implications == assume: OVH<br/>then: there is no $O(m^{2-\epsilon})$ or $O(\min_{1 \leq i \leq k} b_i \cdot (k \cdot m)^{1-\epsilon})$-time algorithm (for any $\epsilon > {0}$ for generalized Büchi games. In particular there is no such algorithm for deciding whether the winning set is non-empty or deciding whether a specifc vertex is in the winning set. == Year == 2016 == Reference == Chat..." current
• 11:1911:19, 15 February 2023 diff hist +692‎ N Reduction from Triangle Detection to Disjunctive coBüchi Objectives ‎ Created page with "FROM: Triangle Detection TO: Disjunctive coBüchi Objectives == Description == == Implications == assume: Strong Triangle<br/>then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k\cdot n^{2})^{1-\epsilon})$-time algorithm for any $epsilon > {0}$ for generalized Büchi games. In particular, there is no such algorithm deciding whether the winning set is non-empty or deciding whether a specific vertex is in the winning set. == Year == 2016 == Refer..." current
• 11:1911:19, 15 February 2023 diff hist +563‎ N Reduction from OV to Largest Common Subtree ‎ Created page with "FROM: OV TO: Largest Common Subtree == Description == == Implications == assume: OVH<br/>then: for all constants $d \geq {2}$, target on two rooted trees of size at most $n$, degree $d$, and height $h \leq \log_d n + O(\log \log n)$ cannot be solved in truly subquadtratic $O(n^{2-\epsilon})$ time == Year == 2018 == Reference == Abboud, A., Backurs, A., Hansen, T. D., Vassilevska Williams, V., & Zamir, O. (2018). Subtree isomorphism revisited. ACM Tra..." current
• 11:1911:19, 15 February 2023 diff hist +544‎ N Reduction from k-SAT to Subset Sum ‎ Created page with "FROM: k-SAT TO: Subset Sum == Description == == Implications == assume: SETH<br/>then: for any $\epsilon > {0}$ there exists a $\delta > {0}$ such that Subset Sum is not in time $O(T^{1-\epsilon}{2}^{\delta n})$, and $k$-Sum is not in time $O(T^{1-\epsilon}n^{\delta k})$ == Year == 2022 == Reference == Abboud, A., Bringmann, K., Hermelin, D., & Shabtay, D. (2022). SETH-based lower bounds for subset sum and bicriteria path. ACM Transactions on Algorit..." current
• 11:1911:19, 15 February 2023 diff hist +557‎ N Reduction from OV to Subtree Isomorphism ‎ Created page with "FROM: OV TO: Subtree Isomorphism == Description == == Implications == assume: OVH<br/>then: for all $d \geq {2}$, target on two rooted unordered trees of size $O(n)$, degree $d$, and height $h \leq {2}\log_d n + O(\log \log n)$ cannot be solved in truly subquadratic $O(n^{2-\epsilon})$ time == Year == 2018 == Reference == Abboud, A., Backurs, A., Hansen, T. D., Vassilevska Williams, V., & Zamir, O. (2018). Subtree isomorphism revisited. ACM Transacti..." current
• 11:1911:19, 15 February 2023 diff hist +12‎ Reduction from k-Clique to RNA Folding ‎No edit summary
• 11:1911:19, 15 February 2023 diff hist +12‎ Reduction from k-Clique to CFG Recognition ‎No edit summary Tag: Reverted
• 11:1911:19, 15 February 2023 diff hist +578‎ N Reduction from k-Clique to RNA Folding ‎ Created page with "FROM: k-Clique TO: RNA Folding == Description == == Implications == assume: k-Clique Hypothesis<br/>then: there is no $O(N^{\omega-\epsilon}) time algorithm for target for any $\epsilon > {0}$ == Year == 2017 == Reference == Abboud, A., Backurs, A., Bringmann, K., & Künnemann, M. (2017, October). Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In 2017 IEEE 58th Annual Symposium on Foundations..."
• 11:1911:19, 15 February 2023 diff hist +582‎ N Reduction from k-Clique to CFG Recognition ‎ Created page with "FROM: k-Clique TO: CFG Recognition == Description == == Implications == assume: k-Clique Hypothesis<br/>then: there is no $O(N^{\omega-\epsilon}) time algorithm for target for any $\epsilon > {0}$ == Year == 2017 == Reference == Abboud, A., Backurs, A., Bringmann, K., & Künnemann, M. (2017, October). Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In 2017 IEEE 58th Annual Symposium on Foundat..."
• 11:1911:19, 15 February 2023 diff hist +525‎ N Reduction from OV to Bichromatic Hamming Close Pair ‎ Created page with "FROM: OV TO: Bichromatic Hamming Close Pair == Description == == Implications == assume: OVH<br/>then: there is no algorithm to solve target in time $O({2}^{o(d)}n^{2-\epsilon})$ on a set of $n$ points in $\{0,{1}\}^{c\log n}$ == Year == 2015 == Reference == Alman, J., & Williams, R. (2015, October). Probabilistic polynomials and hamming nearest neighbors. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (pp. 136-150). IEEE. htt..." current
• 11:1911:19, 15 February 2023 diff hist +590‎ N Reduction from CNF-SAT to sensitive incremental ST-Reach ‎ Created page with "FROM: CNF-SAT TO: sensitive incremental ST-Reach == Description == == Implications == assume: SETH<br/>then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Co..." current
• 11:1911:19, 15 February 2023 diff hist +619‎ N Reduction from CNF-SAT to constant sensitivity (4/3)-approximate incremental diameter ‎ Created page with "FROM: CNF-SAT TO: constant sensitivity (4/3)-approximate incremental diameter == Description == == Implications == assume: SETH<br/>then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S.,..." current
• 11:1911:19, 15 February 2023 diff hist +545‎ N Reduction from Directed, Weighted APSP to 1-sensitive decremental diameter ‎ Created page with "FROM: Directed, Weighted APSP TO: 1-sensitive decremental diameter == Description == == Implications == assume: APSP Hypothesis<br/>then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected weighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems...." current
• 11:1911:19, 15 February 2023 diff hist +586‎ N Reduction from CNF-SAT to sensitive incremental ‎ Created page with "FROM: CNF-SAT TO: sensitive incremental #SSR == Description == == Implications == assume: SETH<br/>then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Condit..." current
• 11:1911:19, 15 February 2023 diff hist +554‎ N Reduction from Directed, Weighted APSP to 2-sensitive decremental st-shortest paths ‎ Created page with "FROM: Directed, Weighted APSP TO: 2-sensitive decremental st-shortest paths == Description == == Implications == assume: APSP Hypothesis<br/>then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected weighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity p..." current
• 11:1911:19, 15 February 2023 diff hist +560‎ N Reduction from Replacement Paths Problem (RPP) to 1-sensitive decremental st-shortest paths ‎ Created page with "FROM: Replacement Paths Problem (RPP) TO: 1-sensitive decremental st-shortest paths == Description == == Implications == assume: APSP Hypothesis<br/>then: target cannot be solved with preprocessing time $O(n^{3-\epsilon})$ and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in directed weighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensiti..." current
• 11:1911:19, 15 February 2023 diff hist +547‎ N Reduction from BMM to 1-sensitive decremental st-shortest paths ‎ Created page with "FROM: BMM TO: 1-sensitive decremental st-shortest paths == Description == == Implications == assume: BMM<br/>then: for directed unweighted graphs with $n$ vertices and $m \geq n$ edges require either $m^{1-o({1})}\sqrt{n}$ preprocessing time or $m^{1-o({1})}/\sqrt{n}$ query time for every function $m$ of $n$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems..." current
• 11:1911:19, 15 February 2023 diff hist +555‎ N Reduction from BMM to 1-sensitive (4/3)-approximate decremental diameter ‎ Created page with "FROM: BMM TO: 1-sensitive (4/3)-approximate decremental diameter == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity..." current
• 11:1911:19, 15 February 2023 diff hist +527‎ N Reduction from BMM to 1-sensitive (4/3)-approximate decremental eccentricity ‎ Created page with "FROM: BMM TO: 1-sensitive (4/3)-approximate decremental eccentricity == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arX..." current
• 11:1911:19, 15 February 2023 diff hist +508‎ N Reduction from BMM to (5/3)-approximate ap-shortest paths ‎ Created page with "FROM: BMM TO: (5/3)-approximate ap-shortest paths == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638. htt..." current
• 11:1911:19, 15 February 2023 diff hist +552‎ N Reduction from BMM to 1-sensitive (3/2)-approximate ss-shortest paths ‎ Created page with "FROM: BMM TO: 1-sensitive (3/2)-approximate ss-shortest paths == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity pro..." current
• 11:1911:19, 15 February 2023 diff hist +552‎ N Reduction from BMM to 2-sensitive (7/5)-approximate st-shortest paths ‎ Created page with "FROM: BMM TO: 2-sensitive (7/5)-approximate st-shortest paths == Description == == Implications == assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs == Year == 2017 == Reference == Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity pro..." current