New pages

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

• 11:14, 15 February 2023 ‎Nested loop join ( Joins) (hist | edit) ‎[299 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O({1})$ words (Just need to keep track of which rows are being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM(?) == Year == 1960 == Reference == -")
• 11:14, 15 February 2023 ‎Basic Local Alignment Search Tool (BLAST) (Edit Sequence, constant-size alphabet Sequence Alignment) (hist | edit) ‎[369 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$? words (Uses at most a constant number of O(m)*O(n) arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/2231712")
• 11:14, 15 February 2023 ‎Gapped BLAST (Edit Sequence, constant-size alphabet Sequence Alignment) (hist | edit) ‎[369 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$? words (Uses at most a constant number of O(m)*O(n) arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/9254694")
• 11:14, 15 February 2023 ‎Apostolico–Giancarlo Algorithm (Single String Search String Search) (hist | edit) ‎[440 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(m + s)$ + $O(n)$ == Space Complexity == $O(m)$ words (https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech&sei-redir=1) == Description == Variant of BM == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech&sei-redir=1")
• 11:14, 15 February 2023 ‎Boyer-Moore-Horspool (BMH) (Single String Search String Search) (hist | edit) ‎[386 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn + s)$ == Space Complexity == $O(s)$ words (Derived: Uses a bad-character shift table of size $O(s)$) == Description == Bad-character heuristic == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380100608")
• 11:14, 15 February 2023 ‎BOM (Backward Oracle Matching) (Single String Search String Search) (hist | edit) ‎[396 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(m)$ + $O(mn)$ == Space Complexity == $O(m)$ words (https://link.springer.com/content/pdf/10.1007/3-540-47849-3_18.pdf) == Description == Automaton-based oracle == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/chapter/10.1007/3-540-47849-3_18")
• 11:14, 15 February 2023 ‎Raita Algorithm (Single String Search String Search) (hist | edit) ‎[388 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn + s)$ == Space Complexity == $O(s)$ words (Derived: Uses a bad-character shift table of size $O(s)$) == Description == Slight variation of BMH == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://www.cin.ufpe.br/~paguso/courses/if767/bib/Raita_1992.pdf")
• 11:14, 15 February 2023 ‎Aho–Corasick (AC) Algorithm (Multiple String Search String Search) (hist | edit) ‎[410 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n + m + z)$ == Space Complexity == $O(km)$ words (Derived: Number of states of the automaton that is created) == Description == Automaton-based, finite automaton that tracks the partial prefix match == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://cr.yp.to/bib/1975/aho.pdf")
• 11:14, 15 February 2023 ‎Commentz-Walter Algorithm (Multiple String Search String Search) (hist | edit) ‎[434 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(km)$ words (Derived: Number of states of the automaton that is created) == Description == Automaton-based, constructs a converse state machine from the given patterns == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://link.springer.com/chapter/10.1007/3-540-09510-1_10")
• 11:14, 15 February 2023 ‎Backward Non-Deterministic DAWG Matching (BNDM) (Single String Search String Search) (hist | edit) ‎[347 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(sm)$ words (https://link.springer.com/chapter/10.1007/BFb0030778) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/chapter/10.1007/BFb0030778")
• 11:14, 15 February 2023 ‎Fast Hybrid Algorithm (Single String Search String Search) (hist | edit) ‎[389 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$+ $O(m+s)$ == Space Complexity == $O(m)$ words (Derived: Uses three tables, each of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://thesai.org/Downloads/Volume8No6/Paper_15-Fast_Hybrid_String_Matching_Algorithm.pdf")
• 11:14, 15 February 2023 ‎Quick-Skip Searching (Single String Search String Search) (hist | edit) ‎[327 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: Uses two tables, both of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2012 == Reference == http://www.ijcte.org/papers/462-G1278.pdf")
• 11:14, 15 February 2023 ‎String-Matching with Finite Automata (Single String Search String Search) (hist | edit) ‎[275 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: $O(m)$ states in the DFA) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
• 11:14, 15 February 2023 ‎Two-way String-Matching Algorithm (Single String Search String Search) (hist | edit) ‎[364 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n + m)$ == Space Complexity == $O({1})$ words (http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf")
• 11:14, 15 February 2023 ‎Shor's algorithm Quantum Implementation (Second Category Integer Factoring Integer Factoring) (hist | edit) ‎[374 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ qubits (https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm) == Description == Quantum algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Quantum == Year == 1994 == Reference == https://ieeexplore.ieee.org/document/365700/")
• 11:14, 15 February 2023 ‎General number field sieve (Second Category Integer Factoring Integer Factoring) (hist | edit) ‎[403 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(exp(({1}+o({1})$)({64}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically? == Space Complexity == $O(n^{2/3})$ bits (http://www.ams.org/notices/199612/pomerance.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == http://www.ams.org/notices/199612/pomerance.pdf")
• 11:14, 15 February 2023 ‎Special number field sieve (First Category Integer Factoring Integer Factoring) (hist | edit) ‎[419 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(exp(({1}+o({1})$)({32}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically? == Space Complexity == $O(n^{2/3})$ bits (http://www.ams.org/notices/199612/pomerance.pdf) == Description == For integers of the form $r^e \pm s$, for r and s relatively small == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference ==")
• 11:14, 15 February 2023 ‎Bader & Cong Parallel Implementation (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) ‎[467 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E log(V)$/p) == Space Complexity == $O(V)$ total words (Initializes and uses a constant number of arrays of size O(V) (and does work similar to work done in Boruvka/Prim algorithm)) == Description == Parallel algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == PRAM/SMPs? == Year == 2006 == Reference == https://www.sciencedirect.com/science/article/pii/S0743731506001262")
• 11:14, 15 February 2023 ‎Incremental convex hull algorithm; Michael Kallay ( Convex Hull) (hist | edit) ‎[294 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference == https://www.sciencedirect.com/science/article/pii/002001908490084X")
• 11:14, 15 February 2023 ‎Alon and Kahale (3-Graph Coloring Graph Coloring) (hist | edit) ‎[279 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.24}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://www.cs.tau.ac.il/~nogaa/PDFS/spectcolpr1.pdf")
• 11:14, 15 February 2023 ‎Johnson (3-Graph Coloring Graph Coloring) (hist | edit) ‎[300 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.4422}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1988 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0020019088900658")
• 11:14, 15 February 2023 ‎Hirsch (3-Graph Coloring Graph Coloring) (hist | edit) ‎[273 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.239}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://dl.acm.org/doi/10.5555/314613.314838")
• 11:14, 15 February 2023 ‎Schöning (3-Graph Coloring Graph Coloring) (hist | edit) ‎[260 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.333}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/document/814612")
• 11:14, 15 February 2023 ‎Robson (3-Graph Coloring Graph Coloring) (hist | edit) ‎[296 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.2108}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0196677486900325")
• 11:14, 15 February 2023 ‎Wu et al. (LCS Longest Common Subsequence) (hist | edit) ‎[328 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$? words (Derived: Same as the above two) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://publications.mpi-cbg.de/Wu_1990_6334.pdf")
• 11:14, 15 February 2023 ‎Ahuja et al. ( Maximum Flow) (hist | edit) ‎[326 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(VELog(V(LogU)$^{0.5} / E)) == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1987 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.5093&rep=rep1&type=pdf")
• 11:14, 15 February 2023 ‎Miller and Myers (LCS Longest Common Subsequence) (hist | edit) ‎[393 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$ words (Derived: Uses an upper triangular matrix $M$ that is size $(m + 1) \times (m + 1)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380151102")
• 11:14, 15 February 2023 ‎Nakatsu et al. (LCS Longest Common Subsequence) (hist | edit) ‎[375 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$ words (https://link.springer.com/content/pdf/10.1007/3-540-58338-6_63.pdf, Fig. 3) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://link.springer.com/article/10.1007/BF00264437")
• 11:09, 15 February 2023 ‎List:Algorithms (hist | edit) ‎[281,464 bytes] ‎Admin (talk | contribs) (Created page with "{| class="wikitable sortable" style="text-align:center;" width="100%" ! Family !! Name !! Year !! Time Complexity !! Space Complexity |- | style="text-align:left;" | Approximate OBST || style="text-align:left;" | Melhorn's Approximation algorithm (Approximate OBST Optimal Binary Search Trees) || 1975 || $O(n)$ || $O(n)$ |- | style="text-align:left;" | Approximate OBST || style="text-align:left;" | Karpinski (Appro...")
• 10:55, 15 February 2023 ‎Reduction from MAX-CNF-SAT to Maximum Local Edge Connectivity (hist | edit) ‎[480 bytes] ‎Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: Maximum Local Edge Connectivity == Description == == Implications == assume: SETH<br/>then: for any $\epsilon > {0}$, in graphs with $n$ nodes and $\tilde{O}(n)$ edges, target cannot be solved in time $O(n^{2-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4), 1-15. https://dl.acm.org/doi/abs/10.1145/32...")
• 10:55, 15 February 2023 ‎Reduction from MAX-CNF-SAT to All-Pairs Maximum Flow (hist | edit) ‎[602 bytes] ‎Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: All-Pairs Maximum Flow == Description == == Implications == assume: SETH<br/>then: for any fixed $\epsilon > {0}$, in graphs with $n$ nodes, $m=O(n)$ edges, and capacities in $\{1,\cdots,n\}$ target cannot be solved in time $O((n^{2}m)^{1-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4), 1-15. https:/...")
• 10:55, 15 February 2023 ‎Reduction from MAX-CNF-SAT to st-Maximum Flow (hist | edit) ‎[503 bytes] ‎Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: st-Maximum Flow == Description == == Implications == assume: SETH<br/>then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Dynamic Bipartite Maximum-Weight Matching (hist | edit) ‎[676 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Dynamic Bipartite Maximum-Weight Matching == Description == == Implications == if: to-time: amortized $O(n^{2-\epsilon})$ update and query times in decremental or incremental graphs<br/>then: APSP Hypothesis 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...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Dynamic $st$-Shortest Path (hist | edit) ‎[661 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Dynamic $st$-Shortest Path == Description == == Implications == if: to-time: amortized $O(n^{2-\epsilon})$ update and query times in decremental or incremental graphs<br/>then: APSP Hypothesis 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 Scien...")
• 10:55, 15 February 2023 ‎Reduction from Triangle Detection to Dynamic Bipartite Maximum-Weight Matching (hist | edit) ‎[767 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Dynamic Bipartite Maximum-Weight Matching == Description == == Implications == let $\gamma = (w-{1})/(w+{1}) \in ({1}/{3},{0.408})$<br/>if: to-time: $O(m^{2\gamma-\epsilon})$ update and query times even after O(m^{1+\gamma-\epsilon}) preprocessing time for any $\epsilon > {0}$<br/>then: Strong Triangle is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply stro...")
• 10:55, 15 February 2023 ‎Reduction from Triangle Detection to Strong Connectivity (dynamic) (hist | edit) ‎[755 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Strong Connectivity (dynamic) == Description == == Implications == let $\gamma = (w-{1})/(w+{1}) \in ({1}/{3},{0.408})$<br/>if: to-time: $O(m^{2\gamma-\epsilon})$ update and query times even after O(m^{1+\gamma-\epsilon}) preprocessing time for any $\epsilon > {0}$<br/>then: Strong Triangle is false == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bou...")
• 10:55, 15 February 2023 ‎Reduction from Triangle Detection to Dynamic st-Reach (hist | edit) ‎[791 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Dynamic st-Reach == Description == == Implications == assume: SETH<br/>then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$ == Year == 2014 == Reference == Abboud, Amir, and Virginia Vassilevska Williams. "Popula...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Dynamic ST-Reach (hist | edit) ‎[672 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic ST-Reach == Description == == Implications == if: to-time: $O(m^{2-\epsilon})$ amrotized update and query times, 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 Com...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Dynamic 4/3-Diameter (hist | edit) ‎[676 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic 4/3-Diameter == Description == == Implications == if: to-time: $O(m^{2-\epsilon})$ amrotized update and query times, 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...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Dynamic Connected Subgraph (hist | edit) ‎[699 bytes] ‎Admin (talk | contribs) (Created page with "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 Symp...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to (hist | edit) ‎[677 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: #SSR == 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 o...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Dynamic MaxSCC (hist | edit) ‎[687 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Dynamic MaxSCC == 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 Fou...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to SC2 (hist | edit) ‎[676 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: SC2 == 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...")
• 10:55, 15 February 2023 ‎Reduction from Min-Weight k-Clique to Minimum Weight k-Cycle (hist | edit) ‎[635 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Min-Weight k-Clique TO: Minimum Weight k-Cycle == Description == == Implications == if: to-time: $O(nm^{\lceil k/{2} \rceil / \lambda - \epsilon})$ for any $\epsilon > {0}$ for $m = \Theta(n^{1+{1}/(\lambda - {1})}) edges and $n$ nodes where $\lambda = k - \lceil k/{2} \rceil + {1}$<br/>then: from-time: $O(n^{k - \epsilon})$ for some $\epsilon > {0}$ == Year == 2018 == Reference == Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Will...")
• 10:55, 15 February 2023 ‎Reduction from Min-Weight k-Cycle to Undirected Wiener Index (hist | edit) ‎[450 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Min-Weight k-Cycle TO: Undirected Wiener Index == Description == == Implications == if: to-time: $f(N,M)$ for N nodes, M edges<br/>then: from-time: $\tilde{O}(f(N,M)+M)$ == Year == 2018 == Reference == Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proc. SODA, page to appear, 2018. https://arxiv.org/pdf/1712.08147v2.pdf, Theorem B.2")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Approximate Betweenness Centrality (hist | edit) ‎[720 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Approximate Betweenness Centrality == Description == $\alpha$-approximation for any finite $\alpha$ (possibly depending on $m$) == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Approximate Reach Centrality (hist | edit) ‎[688 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Approximate Reach Centrality == Description == $\alpha$-approximation for any finite $\alpha$ (possibly depending on $m$) == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and d...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Positive Betweenness Centrality (hist | edit) ‎[732 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Positive Betweenness Centrality == Description == Positive Betweenness Centrality in directed or undirected graphs with weights in $\{1, 2\}$ == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality...")
• 10:55, 15 February 2023 ‎Reduction from Betweenness Centrality (BC) to Diameter (hist | edit) ‎[588 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Betweenness Centrality (BC) TO: Diameter == Description == == Implications == if: to-time: Truly subcubic<br/>then: from-time: Truly subcubic Monte-Carlo PTAS == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA...")
• 10:55, 15 February 2023 ‎Reduction from Approximate Betweenness Centrality to Diameter (hist | edit) ‎[556 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Approximate Betweenness Centrality TO: Diameter == Description == $\alpha$-approximation with $\alpha > 1$ == Implications == == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681...")

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)