New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 08:33, 10 April 2023 Shell Sort (Sedgewick) (Comparison Sorting Sorting) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{3}3})$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0196677486900015?via%3Dihub")
- 08:33, 10 April 2023 Shell Sort (Pratt) (Comparison Sorting Sorting) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log^{2} n)$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://apps.dtic.mil/sti/pdfs/AD0740110.pdf")
- 08:33, 10 April 2023 Shell Sort (Frank & Lazarus) (Comparison Sorting Sorting) (hist | edit) [313 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.5})$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/citation.cfm?doid=366947.366957")
- 08:32, 10 April 2023 Shell Sort (Shell) (Comparison Sorting Sorting) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ words (in-situ sorting) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1959 == Reference == https://dl.acm.org/citation.cfm?doid=368370.368387")
- 08:32, 10 April 2023 Khuller; Matias ( Closest Pair Problem) (hist | edit) [444 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$, not sure if this is auxiliary not mentioned (https://www.sciencedirect.com/science/article/pii/S0890540185710498, Theorem 2.3) == Description == Randomized Sieve == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == not mentioned == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540185710498")
- 08:29, 10 April 2023 Nivasch (Cycle Detection Cycle Detection) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(\mu + \lambda)$ == Space Complexity == $O(\log\mu)$ Stack size (https://www.gabrielnivasch.org/fun/cycle-detection) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2004 == Reference == https://drive.google.com/file/d/16H_lrjeaBJqWvcn07C_w-6VNHldJ-ZZl/view")
- 08:29, 10 April 2023 Sedgewick; Szymanski; and Yao (Cycle Detection Cycle Detection) (hist | edit) [400 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $(\mu + \lambda)({1}+\Theta({1}/sqrt(M)))$ == Space Complexity == M Memory cells (https://epubs.siam.org/doi/abs/10.1137/0211030?journalCode=smjcat) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1982 == Reference == https://epubs.siam.org/doi/abs/10.1137/0211030?journalCode=smjcat")
- 08:29, 10 April 2023 Eppstein (Subset Sum The Subset-Sum Problem) (hist | edit) [380 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(n max(S))$ == Space Complexity == $O(t logt)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S019667749690841X?via%3Dihub")
- 08:29, 10 April 2023 Compression/Clustering (Vector Quantization) (k-ANNS Nearest Neighbor Search) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == Varies by codebook structure == Space Complexity == Varies by codebook structure (Table 2) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 1992 == Reference ==")
- 08:29, 10 April 2023 Projected radial search (k-ANNS for a dense 3D map of geometric points Nearest Neighbor Search) (hist | edit) [418 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k)$ == Space Complexity == $O({1})$ words (Derived: There are 5 local variables and no tables or lists aside from input/output) == Description == == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == http://www.araa.asn.au/acra/acra2013/papers/pap148s1-file1.pdf")
- 08:29, 10 April 2023 Locality-sensitive hashing (k-ANNS Nearest Neighbor Search) (hist | edit) [474 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nLkt)$ (pre-processing) $O(L(kt+dnP_2^k))$ (query-time) == Space Complexity == $O(nL)$ hash table cells (https://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search) == Description == == Approximate? == Approximate Approximation Factor: c == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == http://infolab.stanford.edu/~ullman/mmds/ch3n.pdf")
- 08:29, 10 April 2023 Hierarchical Navigable Small World (HNSW) (k-ANNS Nearest Neighbor Search) (hist | edit) [419 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(M)$ bytes of memory (https://arxiv.org/abs/1603.09320, "Memory usage is proportional to choice of M") == Description == == Approximate? == Approximate Approximation Factor: ? experimental results == Randomized? == No, deterministic == Model of Computation == == Year == 2018 == Reference == https://doi.org/10.1109/TPAMI.2018.2889473")
- 07:57, 10 April 2023 Work-conserving schedulers (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [231 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 07:57, 10 April 2023 Multilevel queue scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above; also level information for each task) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 07:57, 10 April 2023 Round-robin scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 07:57, 10 April 2023 First come, first served (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 07:57, 10 April 2023 Shortest remaining time first (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [250 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 07:57, 10 April 2023 Priority scheduling (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 07:57, 10 April 2023 Fixed priority shortest job first (Unweighted Interval Scheduling, Online Interval Scheduling) (hist | edit) [394 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == $O(n+k)$? words (Keep track of (sorted, based on criteria) list of (unscheduled, running, etc.; just un-done) tasks, along with machine statuses and task priorities) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 07:57, 10 April 2023 BOYS algorithm (Entity Resolution Entity Resolution) (hist | edit) [394 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n^{2})$ words (Derived: As written stores counts/probabailities for all pairs of entries.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://www.sciencedirect.com/science/article/abs/pii/016794739390116B")
- 07:56, 10 April 2023 Gremban; Miller; Zagha (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [454 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiZa94-tr.pdf) == Description == Support Tree Conjugate Gradients (STCG) == Approximate? == Approximate Approximation Factor: ? == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://www.cs.cmu.edu/~glmiller/Publications/Papers/GrMiZa94-tr.pdf")
- 07:55, 10 April 2023 David (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [238 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference ==")
- 07:55, 10 April 2023 Closed formula (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [238 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n \log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference ==")
- 07:54, 10 April 2023 Hirschberg's algorithm (Edit sequence Sequence Alignment) (hist | edit) [329 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://dl.acm.org/doi/10.1145/360825.360861")
- 07:54, 10 April 2023 Masek; Patterson (Edit distance Sequence Alignment) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn / log(n))$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0022000080900021) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0022000080900021")
- 07:53, 10 April 2023 No-Steal, Force (hist | edit) [492 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:No-Steal, Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a No-Steal/Force policy, the recovery algorithm will never write uncommited data to memory, but will force all commits to memory. == Related Problems == Related: Steal, No-Force == Parameters == $n$: number of transactions before crash == Table of Algorithms == Currently no algorithms in our database for t...")
- 07:53, 10 April 2023 Steal, No-Force (hist | edit) [914 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Steal, No-Force (Recovery)}} == Description == Recovery is the process of reverting back to a safe state prior to a system failure. With a Steal/No-Force policy, the recovery algorithm will write possibly uncommited data to memory, while not forcing all commits to memory. == Related Problems == Related: No-Steal, Force == Parameters == $n$: number of transactions before crash == Table of Algorithms == {| class="wikitable sortable" style="t...")
- 07:53, 10 April 2023 Unweighted Interval Scheduling, Online (hist | edit) [3,094 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Unweighted Interval Scheduling, Online (Interval Scheduling)}} == Description == Given are $n$ intervals of the form $(s_j , f_j)$ with $s_j < f_j$, for $j = 1, \ldots , n$. These intervals are the jobs that require uninterrupted processing during that interval. We will assume (without loss of generality) that the $s_j$’s and the $f_j$’s are nonnegative integers. We say that two intervals (or jobs) overlap if their intersection is nonempty, otherwise...")
- 07:52, 10 April 2023 Root Computation with continuous first derivative (hist | edit) [764 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Root Computation with continuous first derivative (Root Computation)}} == Description == Given a real function with continuous first derivative, compute one of the roots. == Related Problems == Related: General Root Computation == Parameters == $\epsilon$: (additive) tolerance error $a, b$: endpoint values, with $b>a$ $n_{max}$: maximum number of iterations == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;"...")
- 07:52, 10 April 2023 General Root Computation (hist | edit) [2,713 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:General Root Computation (Root Computation)}} == Description == Given a real continuous function, compute one of the roots. == Related Problems == Related: Root Computation with continuous first derivative == Parameters == $\epsilon$: (additive) tolerance error $a, b$: endpoint values, with $b>a$ $n_{max}$: maximum number of iterations == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name...")
- 14:52, 15 February 2023 Reduction from OV to Disjunctive Reachability Queries in MDPs (hist | edit) [563 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: Disjunctive Reachability Queries 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 Symposium...")
- 11:19, 15 February 2023 Reduction from OV to k-OV (hist | edit) [135 bytes] Admin (talk | contribs) (Created page with "FROM: OV TO: k-OV == Description == == Implications == == Year == == Reference ==")
- 11:19, 15 February 2023 Reduction from 3-OV to k-OV (hist | edit) [141 bytes] Admin (talk | contribs) (Created page with "FROM: 3-OV TO: k-OV == Description == == Implications == == Year == == Reference ==")
- 11:19, 15 February 2023 Reduction from Max-Weight K-Clique to Weighted Depth (hist | edit) [619 bytes] Admin (talk | contribs) (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,...")
- 11:19, 15 February 2023 Reduction from Max-Weight k-Clique to Maximum Subarray (hist | edit) [623 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from Max-Weight K-Clique to Maximum Square Subarray (hist | edit) [596 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from Weighted, Undirected APSP to 2D Maximum Subarray (hist | edit) [572 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from Negative Triangle Detection to 2D Maximum Subarray (hist | edit) [569 bytes] Admin (talk | contribs) (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....")
- 11:19, 15 February 2023 Reduction from Max-Weight k-Clique to Max-Weight Rectangle (hist | edit) [616 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from Bichromatic Hamming Close Pair to Approximate Hard-Margin SVM (hist | edit) [701 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from Maximum Inner Product Search to Stable Pair Checking (hist | edit) [641 bytes] Admin (talk | contribs) (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:19, 15 February 2023 Reduction from Maximum Inner Product Search to Stable Matching Verification (hist | edit) [585 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from Maximum Inner Product Search to Boolean d-Attribute Stable Matching (hist | edit) [591 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from OV to Disjunctive Queries of Safety in Graphs (hist | edit) [590 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from OV to Disjunctive Queries of Reachability in MDPs (hist | edit) [563 bytes] Admin (talk | contribs) (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:19, 15 February 2023 Reduction from Triangle Detection to Disjunctive Queries of Safety in Graphs (hist | edit) [642 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from Triangle Detection to Disjunctive Queries of Reachability in MDPs (hist | edit) [653 bytes] Admin (talk | contribs) (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:...")
- 11:19, 15 February 2023 Reduction from OV to Generalized Büchi Games (hist | edit) [678 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from Triangle Detection to Disjunctive coBüchi Objectives (hist | edit) [692 bytes] Admin (talk | contribs) (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...")
- 11:19, 15 February 2023 Reduction from OV to Largest Common Subtree (hist | edit) [563 bytes] Admin (talk | contribs) (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...")