New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:31, 15 February 2023 Grigoryan (n-Queens Completion n-Queens Problem) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (Derived: two control arrays of size O(n)) == Description == == Approximate? == Approximate Approximation Factor: error < 0.0001 and decreases with increasing n == Randomized? == Yes, Monte Carlo == Model of Computation == == Year == 2018 == Reference == https://arxiv.org/abs/1912.05935")
- 10:31, 15 February 2023 Spatial GAN-Based; Urs Bergmann, Nikolay Jetchev, Roland Vollgraf (Texture Synthesis Texture Synthesis) (hist | edit) [321 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(N)$ == Space Complexity == $O(N)$ (https://arxiv.org/abs/1705.06566) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2017 == Reference == https://arxiv.org/abs/1705.06566")
- 10:31, 15 February 2023 Tree-structured vector quantization Wei-Levoy (Texture Synthesis Texture Synthesis) (hist | edit) [373 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log n)$ == Space Complexity == $O(nd)$ (https://dl.acm.org/doi/abs/10.1145/344779.345009) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == TSVQ Tree == Year == 2000 == Reference == https://dl.acm.org/doi/abs/10.1145/344779.345009")
- 10:31, 15 February 2023 MotifSampler (Motif Search Motif Search) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(n + m)$ words (derived: essentially just modified Gibbs sampling) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/12015892")
- 10:31, 15 February 2023 Lawrence Gibbs Sampling (Motif Search Motif Search) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(n + m)$ words (derived: two data structures, one uses O(n) and one uses O(m)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://science.sciencemag.org/content/262/5131/208")
- 10:31, 15 February 2023 Lawrence, Reilly (Motif Search Motif Search) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(nm)$ words (https://www.ncbi.nlm.nih.gov/pubmed/2184437) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/2184437")
- 10:31, 15 February 2023 Valentin Polishchuk, and Jukka Suomela (Almost Stable Marriage Problem Stable Matching Problem) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ == Space Complexity == $O({1})$ words (derived: must be \leq time complexity) == Description == == Approximate? == Approximate Approximation Factor: 2 + \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://arxiv.org/pdf/0812.4893.pdf")
- 10:31, 15 February 2023 Lokshtanov (Subset Sum The Subset-Sum Problem) (hist | edit) [346 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(n^{3} t)$ == Space Complexity == $O(n^{2})$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == https://dl.acm.org/doi/abs/10.1145/1806689.1806735")
- 10:31, 15 February 2023 Serang (Subset Sum The Subset-Sum Problem) (hist | edit) [350 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 == 2014 == Reference == https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0091507")
- 10:31, 15 February 2023 Epstein (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")
- 10:31, 15 February 2023 Klinz (Subset Sum The Subset-Sum Problem) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(σ^{({3}/{2})})$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://doi.org/10.1002/(SICI)1097-0037(199905)33:3%3C189::AID-NET5%3E3.0.CO;2-2")
- 10:31, 15 February 2023 Pferschy (Subset Sum The Subset-Sum Problem) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n' t)$ == Space Complexity == $O(t)$ (https://dl.acm.org/doi/pdf/10.1145/3329863, Table 1) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://link.springer.com/article/10.1007/s006070050042")
- 10:31, 15 February 2023 Faaland (Subset Sum The Subset-Sum Problem) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n' t)$ == Space Complexity == $O(t)$ (https://doi.org/10.1287/opre.21.1.332) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1973 == Reference == https://doi.org/10.1287/opre.21.1.332")
- 10:31, 15 February 2023 Pisinger (Subset Sum The Subset-Sum Problem) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nt/logt)$ == Space Complexity == $O(t/logt)$ words (https://link.springer.com/article/10.1007/s00453-002-0989-y) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/article/10.1007/s00453-002-0989-y")
- 10:31, 15 February 2023 Compression/Clustering (Vector Quantization) (k Approximate Nearest Neighbors Search (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 ==")
- 10:31, 15 February 2023 Projected radial search (k Approximate Nearest Neighbors 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")
- 10:31, 15 February 2023 Locality-sensitive hashing (k Approximate Nearest Neighbors Search (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")
- 10:31, 15 February 2023 Hierarchical Navigable Small World (HNSW) (k Approximate Nearest Neighbors Search (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")
- 10:31, 15 February 2023 Larmore (Approximate OBST Optimal Binary Search Trees) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.6})$ == Space Complexity == $O(n)$ (Derived: Computing and storing f_{d,l} for each n elements) == Description == == Approximate? == Approximate Approximation Factor: \epsilon = o(1) == Randomized? == No, deterministic == Model of Computation == == Year == 1987 == Reference == https://www.sciencedirect.com/science/article/pii/0196677487900526")
- 10:31, 15 February 2023 Klawe; Mumey (Alphabetic Tree Problem Optimal Binary Search Trees) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (Derived: uses a worklist of size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference == https://epubs.siam.org/doi/abs/10.1137/S0895480193256651?journalCode=sjdmec")
- 10:31, 15 February 2023 Karpinski (Approximate OBST Optimal Binary Search Trees) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{0.6})$ == Space Complexity == $O({1})$ (Derived: dynamic programming and making use of Monge matrix properties) == Description == == Approximate? == Approximate Approximation Factor: \epsilon = o(1) == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.6940&rep=rep1&type=pdf")
- 10:31, 15 February 2023 Melhorn's Approximation algorithm (Approximate OBST Optimal Binary Search Trees) (hist | edit) [458 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (https://people.mpi-inf.mpg.de/~mehlhorn/ftp/mehlhorn3.pdf, storing left/right subtrees' weights) == Description == == Approximate? == Approximate Approximation Factor: 0.63 H \leq P_opt \leq P_balanced \leq 2 + 1.44 H == Randomized? == No, deterministic == Model of Computation == == Year == 1975 == Reference == https://people.mpi-inf.mpg.de/~mehlhorn/ftp/mehlhorn3.pdf")
- 10:31, 15 February 2023 Weak Parametrized Inapproximability Hypothesis (WPIH) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Target Problem == Approximate 2-CSP == Description == There is some constant $\delta > 0$ such that given an instance $\varphi$ of 2-CSP on the Boolean hypercube graph $Q$ over alphabet of size $n$, it is W(1)-hard to distinguish == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == == Proven? == No == Year == == References/Citation == ? CCC '22")
- 10:31, 15 February 2023 Parametrized Inapproximability Hypothesis (PIH) (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "== Target Problem == Approximate 2-CSP == Description == There is some constant $\delta > 0$ such that 2-CSP on $k$ vertices and alphabet size $n$ is W(1)-hard to approximate to a $(1-\delta)$ factor == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == == Proven? == No == Year == 2017 == References/Citation == https://epubs.siam.org/doi/abs/10.1137/1.9781611975994.134")
- 10:31, 15 February 2023 $\delta$-Triangle Conjecture (hist | edit) [395 bytes] Admin (talk | contribs) (Created page with "== Target Problem == Triangle Detection == Description == Any Algorithm requires $m^{1+\delta-o(1)}$ time in expectation to detect whether an $m$ edge graph contains a triangle == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == == References/Citation ==")
- 10:30, 15 February 2023 Strong Triangle Conjecture (hist | edit) [705 bytes] Admin (talk | contribs) (Created page with "== Target Problem == Triangle Detection == Description == Any Algorithm requires $\min(n^{w-o(1)}, m^{2w/(w+1)-o(1)})$ time in expectation to detect whether an $n$ node $m$ edge graph contains a triangle. Moreover, any combinatorial algorithm requires $m^{3/2-o(1)}$ == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == 2014 == Referenc...")
- 10:30, 15 February 2023 More Believable Exponential Time Hypothesis (MBETH) (hist | edit) [567 bytes] Admin (talk | contribs) (Created page with "== Target Problem == k-SAT == Description == There exists a $k \geq 3$ and a $\delta > 0$ so that $k$-SAT on $n$ variables cannot be solved in $O(2^{\delta n})$ == Implies the following Hypothesis == ETH == Implied by the following Hypothesis == ETH, SETH == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No ==...")
- 10:30, 15 February 2023 Nondeterministic Strong Exponential Time Hypothesis (NSETH) (hist | edit) [491 bytes] Admin (talk | contribs) (Created page with "== Target Problem == [[]] == Description == Refuting unsatisfiable $k$-CNF formulas on $n$ variables requires nondeterministic $2^{n-o(n)}$ time for unbounded $k$. == Implies the following Hypothesis == SETH == Implied by the following Hypothesis == == Computation Model == == Proven? == No (Variants have been disproved) == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.p...")
- 10:30, 15 February 2023 Online Matrix Vector Multiplication Hypothesis (OMV Hypothesis) (hist | edit) [541 bytes] Admin (talk | contribs) (Created page with "== Target Problem == OMV == Description == Every (randomized) algorithm that can process a given $n \times n$ Boolean matrix $A$, and then in an online way can compute the products $Av_i$ for any $n$ vectors $v_1,\ldots,v_n$, must take total time $n^{3-o(1)}$. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == == References/Citatio...")
- 10:30, 15 February 2023 Boolean Matrix Multiplication Hypothesis (BMM Hypothesis) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Target Problem == BMM == Description == Any combinatorial BMM algorithm requires $n^{3-o(1)}$ time. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.pdf Page 17")
- 10:30, 15 February 2023 Exact k-Clique Hypothesis (hist | edit) [521 bytes] Admin (talk | contribs) (Created page with "== Target Problem == Exact $k$-Clique == Description == The Exact $k$-Clique problem on $n$ node graphs with edge weights in $\{-n^{100k},\ldots,n^{100k}\}$ requires (randomized) $n^{k-o(1)}$ time. == Implies the following Hypothesis == OVH == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people...")
- 10:30, 15 February 2023 Min-Weight k-Clique Hypothesis (hist | edit) [588 bytes] Admin (talk | contribs) (Created page with "== Target Problem == Min-Weight $k$-Clique == Description == The Min-Weight $k$-Clique problem on $n$ node graphs with edge weights in $\{-n^{100k},\ldots, n^{100k}}$ requires (randomized) $n^{k-o(1)}$ time. == Implies the following Hypothesis == Exact k-Clique Hypothesis, OVH == Implied by the following Hypothesis == == Computation Model == Word-Ram on $\log(n)$ bit words == Proven...")
- 10:30, 15 February 2023 Hitting Set Hypothesis (HS Hypothesis) (hist | edit) [442 bytes] Admin (talk | contribs) (Created page with "== Target Problem == HS == Description == No randomized algorithm can solve HS on $n$ vectors in $\{0,1\}^d$ in $n^{2-\epsilon}\poly(d)$ time for $\epsilon > 0$. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 5")
- 10:30, 15 February 2023 All Pairs Shortest Paths Hypothesis (APSP Hypothesis) (hist | edit) [517 bytes] Admin (talk | contribs) (Created page with "== Target Problem == APSP == Description == No randomized algorithm can solve APSP in $O(n^{3-\epsilon})$ time for $\epsilon > 0$ on $n$ node graphs with edge weights in $\{-n^c,\ldots,n^c\}$ and no negative cycles for large enough $c$. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csa...")
- 10:30, 15 February 2023 3SUM Hypothesis (3-SUM Hypothesis) (hist | edit) [467 bytes] Admin (talk | contribs) (Created page with "== Target Problem == 3-SUM == Description == 3-SUM on $n$ integers in $\{-n^4,\ldots,n^4\}$ cannot be solved in $O(n^{2-\epsilon})$ time for any $\epsilon > 0$ by a randomized algorithm. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 2")
- 10:30, 15 February 2023 K-Clique Hypothesis (hist | edit) [480 bytes] Admin (talk | contribs) (Created page with "== Target Problem == [[$k$-Clique for all $k > 0$]] == Description == No randomized algorithm can detect a $k$-Clique in an $n$-node graph in $O(n^{\omega k / 3 - \epsilon})$ time for any $\epsilon > 0$. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.pdf Hypothe...")
- 10:30, 15 February 2023 K-OV Hypothesis (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "== Target Problem == k-OV == Description == No randomized algorithm can solve k-OV on instances of size $n$ in $n^{k-\epsilon}\poly(d)$ time for constant $\epsilon > 0$. == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? == No == Year == == References/Citation == http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 4")
- 10:30, 15 February 2023 Unbalanced Orthogonal Vectors Hypothesis (UOVH) (hist | edit) [590 bytes] Admin (talk | contribs) (Created page with "== Target Problem == UOV == Description == Let $0 < \alpha \leq 1$. For no $\epsilon > 0$ there is an algorithm for OV, restricted to $m = \Theta(n^\alpha)$ and $d \leq n^{o(1)}$, that runs in time $O((nm)^{(1−\epsilon)})$. == Implies the following Hypothesis == SETH, OVH == Implied by the following Hypothesis == OVH == Computati...")
- 10:30, 15 February 2023 Orthogonal Vectors Hypothesis (OVH) (hist | edit) [594 bytes] Admin (talk | contribs) (Created page with "== Target Problem == OV == Description == For no $\epsilon > 0$ there is an algorithm for OV, restricted to $n = m$, that runs in time $O(n^{(2−\epsilon)}poly(d))$. == Implies the following Hypothesis == SETH, UOVH == Implied by the following Hypothesis == k-OV Hypothesis, UOVH == Compu...")
- 10:30, 15 February 2023 Strong Exponential Time Hypothesis (SETH) (hist | edit) [629 bytes] Admin (talk | contribs) (Created page with "== Target Problem == k-SAT == Description == For every $\epsilon > 0$, there exists an integer $k \geq 3$ such that $k$-SAT cannot be solved in $O(2^{(1-\epsilon) n})$ time. == Implies the following Hypothesis == MBETH, ETH == Implied by the following Hypothesis == OVH, [[Unbalanced Orthogonal Vectors Hypothesis (UOVH)|UOVH]...")
- 10:30, 15 February 2023 Exponential Time Hypothesis (ETH) (hist | edit) [579 bytes] Admin (talk | contribs) (Created page with "== Target Problem == 3SAT == Description == There is some constant $\delta > 0$ such that CNF-SAT requires $\Omega(2^{\delta n})$. == Implies the following Hypothesis == MBETH == Implied by the following Hypothesis == SETH, MBETH == Computation Model == Word-RAM on $\log(n)$ bit words == Proven? =...")
- 10:30, 15 February 2023 All-Integers 3SUM (hist | edit) [1,226 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:All-Integers 3SUM (3SUM)}} == Description == Given three lists $A, B, C$ of $n$ integers each, output the list of all integers $a \in A$ such that there exist $b \in B,c \in C$ with $a + b + c = 0$. == Related Problems == Generalizations: 3SUM Related: Real 3SUM, 3SUM' == Parameters == <pre>n: number of integers in each set</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions...")
- 10:30, 15 February 2023 3SUM' (hist | edit) [2,140 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3SUM' (3SUM)}} == Description == Given three sets of integers $A, B, C$ of total size $n$, are there $a\in A, b\in B, c\in C$ such that $a + b = c$? == Related Problems == Generalizations: 3SUM Related: Real 3SUM, All-Integers 3SUM == Parameters == <pre>n: number of integers in each set</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem == {| class="wikitable so...")
- 10:30, 15 February 2023 Real 3SUM (hist | edit) [1,344 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Real 3SUM (3SUM)}} == Description == Given a set $S$ of reals, determine whether there is a subset of $S$ of size 3 that sums to 0. == Related Problems == Subproblem: 3SUM Related: 3SUM', All-Integers 3SUM == Parameters == <pre>S: the set of reals n: the number of real numbers in the set</pre> == Table of Algorithms == {| class="wikitable sortable" style="text-align:center;" width="100%" ! Name !! Year !! Time !! Space !! Approxim...")
- 10:30, 15 February 2023 3SUM (hist | edit) [4,609 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:3SUM (3SUM)}} == Description == Given a set $S$ of integers, determine whether there is a subset of $S$ of size 3 that sums to 0. == Related Problems == Generalizations: Real 3SUM Subproblem: 3SUM', All-Integers 3SUM Related: All-Integers 3SUM == Parameters == <pre>S: the set of integers n: the number of integers in the set</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reduc...")
- 10:30, 15 February 2023 Approximate Hard-Margin SVM (hist | edit) [1,216 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Approximate Hard-Margin SVM (Support Vector Machines (SVM))}} == Description == A (primal) hard-margin SVM is an optimization problem of the following form: $\min\limits_{\alpha_1,\ldots,\alpha_n\geq 0} \frac{1}{2} \sum \limits_{i,j = 1}^n \alpha_i \alpha_j y_i y_j k(x_i, x_j)$ subject to $y_i f(x_i) \geq 1, i = 1, \ldots, n$ where $f(x) := \sum_{i=1}^n \alpha_i y_i k(x_i, x)$ == Parameters == No parameters found. == Table of Algorithms == Curre...")
- 10:30, 15 February 2023 Bichromatic Hamming Close Pair (hist | edit) [1,893 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Bichromatic Hamming Close Pair (Bichromatic Hamming Close Pair)}} == Description == Given two sets $A = \{a_1, \ldots, a_n\} \subseteq \{0, 1\}^d$ and $B = \{b_1, \ldots, b_n\} \subseteq \{0, 1\}^d$ of $n$ binary vectors and an integer $t \in \{2, \ldots, d\}$, decide if there exists a pair $a \in A$ and $b \in B$ such that the number of coordinates in which they differ is less than $t$ (formally, $Hamming(a, b) := |a − b|1 < t$). If there is such a pa...")
- 10:30, 15 February 2023 Dynamic Dihedral Rotation Queries (hist | edit) [514 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Dynamic Dihedral Rotation Queries (Dihedral Rotation Queries)}} == Description == Determine whether a given dihedral rotation is feasible or not, and if it is, modify the chain by performing the rotation. == Related Problems == Related: Static Dihedral Rotation Queries == Parameters == <pre>n: number of edges in the chain</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == References/Citation ==...")
- 10:30, 15 February 2023 Static Dihedral Rotation Queries (hist | edit) [948 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Static Dihedral Rotation Queries (Dihedral Rotation Queries)}} == Description == Determine whether a given dihedral rotation is feasible or not, without modifying the chain. == Related Problems == Related: Dynamic Dihedral Rotation Queries == Parameters == <pre>n: number of edges in the chain</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sor...")
- 10:30, 15 February 2023 Generalized Büchi Games (hist | edit) [1,947 bytes] Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Generalized Büchi Games (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a standard graph, and the objective is Büchi: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that visits the set $T$ an infinite amount of times. Furthermore, in the conjunctive problem, you are giv...")