All public logs
Jump to navigation
Jump to search
Combined display of all available logs of Algorithm Wiki. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)- 10:30, 15 February 2023 Admin talk contribs created page Unbalanced Orthogonal Vectors Hypothesis (UOVH) (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 Admin talk contribs created page Orthogonal Vectors Hypothesis (OVH) (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 Admin talk contribs created page Strong Exponential Time Hypothesis (SETH) (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 Admin talk contribs created page Exponential Time Hypothesis (ETH) (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 Admin talk contribs created page All-Integers 3SUM (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 Admin talk contribs created page 3SUM' (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 Admin talk contribs created page Real 3SUM (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 Admin talk contribs created page 3SUM (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 Admin talk contribs created page Approximate Hard-Margin SVM (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 Admin talk contribs created page BHCP (Redirected page to Bichromatic Hamming Close Pair) Tag: New redirect
- 10:30, 15 February 2023 Admin talk contribs created page Bichromatic Hamming Close Pair (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 Admin talk contribs created page Dynamic Dihedral Rotation Queries (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 Admin talk contribs created page Static Dihedral Rotation Queries (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 Admin talk contribs created page Conjunctive Büchi Objectives (Redirected page to Generalized Büchi Games) Tag: New redirect
- 10:30, 15 February 2023 Admin talk contribs created page Generalized Büchi Games (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...")
- 10:30, 15 February 2023 Admin talk contribs created page Disjunctive coBüchi Objectives (Created page with "{{DISPLAYTITLE:Disjunctive coBüchi Objectives (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 coBüchi: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that visits the set $T$ a finite amount of times. Furthermore, in the disjunctive problem, you a...")
- 10:30, 15 February 2023 Admin talk contribs created page Disjunctive Queries of Safety in Graphs (Created page with "{{DISPLAYTITLE:Disjunctive Queries of Safety in Graphs (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 safety: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$). Furthe...")
- 10:30, 15 February 2023 Admin talk contribs created page Safety in Graphs (Created page with "{{DISPLAYTITLE:Safety in Graphs (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 safety: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$). == Related Problems == Subp...")
- 10:30, 15 February 2023 Admin talk contribs created page Conjunctive Safety Queries in MDPs (Created page with "{{DISPLAYTITLE:Conjunctive Safety Queries in MDPs (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 Markov Decision Process (MDP), and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in...")
- 10:30, 15 February 2023 Admin talk contribs created page Disjunctive Safety Queries in MDPs (Created page with "{{DISPLAYTITLE:Disjunctive Safety Queries in MDPs (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 Markov Decision Process (MDP), and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in...")
- 10:30, 15 February 2023 Admin talk contribs created page Safety in MDPs (Created page with "{{DISPLAYTITLE:Safety in MDPs (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 Markov Decision Process (MDP), and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$). == Related Pr...")
- 10:30, 15 February 2023 Admin talk contribs created page Generalized Reachability in MDPs (Redirected page to Conjunctive Reachability Queries in MDPs) Tag: New redirect
- 10:30, 15 February 2023 Admin talk contribs created page Conjunctive Reachability Queries in MDPs (Created page with "{{DISPLAYTITLE:Conjunctive Reachability Queries in MDPs (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 Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach...")
- 10:30, 15 February 2023 Admin talk contribs created page Disjunctive Reachability Queries in MDPs (Created page with "{{DISPLAYTITLE:Disjunctive Reachability Queries in MDPs (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 Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach...")
- 10:30, 15 February 2023 Admin talk contribs created page Reachability in MDPs (Created page with "{{DISPLAYTITLE:Reachability in MDPs (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 Markov Decision Process (MDP), and the objective is reachability: given a set of target vertices $T\subseteq V$, determine whether there is an infinite path that visits a vertex in $T$ at least once (i.e. you want to reach some vertex in $T$)....")
- 10:30, 15 February 2023 Admin talk contribs created page MIPS (Redirected page to Maximum Inner Product Search) Tag: New redirect
- 10:30, 15 February 2023 Admin talk contribs created page Maximum Inner Product Search (Created page with "{{DISPLAYTITLE:Maximum Inner Product Search (Maximum Inner Product Search)}} == Description == Given a new query $q$, MIPS targets at retrieving the datum having the largest inner product with $q$ from the database $A$. Formally, the MIPS problem is formulated as below: $p = \arg \max \limits_{a \in A} a \top q$ == Parameters == No parameters found. == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions TO Problem...")
- 10:29, 15 February 2023 Admin talk contribs created page RNA Folding (Created page with "{{DISPLAYTITLE:RNA Folding (RNA Folding)}} == Description == In RNA Folding we are given a string over some alphabet (e.g. $\{A, C, G, T\}$) with a fixed pairing between its symbols (e.g. $A − T$ match and $C − G$ match), and the goal is to compute the maximum number of non-crossing arcs between matching letters that one can draw above the string (which corresponds to the minimum energy folding in two dimensions). == Parameters == <pre>n: length of the given str...")
- 10:29, 15 February 2023 Admin talk contribs created page Ap-reach (Created page with "{{DISPLAYTITLE:ap-reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$, determine for each pair $s \neq t \in V$ whether $t$ is reachable from $s$. == Related Problems == Generalizations: st-Reach Related: #SSR, sensitive incremental #SSR, ST-Reach, constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive incremental st-reach == Parameters == <pre>n: number of vertices m: num...")
- 10:29, 15 February 2023 Admin talk contribs created page 2-sensitive incremental st-reach (Created page with "{{DISPLAYTITLE:2-sensitive incremental st-reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$ and vertices $s, t \in V$, incrementally determine wheteher $t$ is reachable from $s$, with sensitivity 2, i.e. when 2 edges are added. == Related Problems == Generalizations: st-Reach Related: #SSR, sensitive incremental #SSR, ST-Reach, constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, ap-re...")
- 10:29, 15 February 2023 Admin talk contribs created page 1-sensitive incremental ss-reach (Created page with "{{DISPLAYTITLE:1-sensitive incremental ss-reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$ and a source node $s \in G$, an incremental single-source reachability algorithm maintains the set of nodes reachable from $s$ (i.e., all nodes $v$ for which there is a path from $s$ to $v$ in the current version of $G$) during a sequence of edge insertions, with sensitivity 1, i.e. when 1 edge is inserted. == Related Problems == Generalizations...")
- 10:29, 15 February 2023 Admin talk contribs created page Constant sensitivity incremental ST-Reach (Created page with "{{DISPLAYTITLE:constant sensitivity incremental ST-Reach (Vertex Reachability)}} == Description == Given a graph $G=(V,E)$, incrementally determine whether each node $s\in S\subseteq V$ can reach a node $t\in T \subseteq V$, with a constant sensitivity of $K(\epsilon, t)$, i.e. when $K(\epsilon, t)$ edges are added. == Related Problems == Generalizations: ST-Reach Related: #SSR, sensitive incremental #SSR, st-Reach, 1-sensitive incremental ss-reac...")
- 10:29, 15 February 2023 Admin talk contribs created page St-Reach (Created page with "{{DISPLAYTITLE:st-Reach (Vertex Reachability)}} == Description == Given a directed graph $G=(V,E)$ and vertices $s, t \in V$, determine wheteher $t$ is reachable from $s$. == Related Problems == Subproblem: constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive incremental st-reach, ap-reach Related: #SSR, sensitive incremental #SSR, ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive increm...")
- 10:29, 15 February 2023 Admin talk contribs created page ST-Reach (Created page with "{{DISPLAYTITLE:ST-Reach (Vertex Reachability)}} == Description == Given a graph $G=(V,E)$, determine whether each node $s\in S\subseteq V$ can reach a node $t\in T \subseteq V$. == Related Problems == Subproblem: constant sensitivity incremental ST-Reach, 1-sensitive incremental ss-reach, 2-sensitive incremental st-reach, ap-reach Related: #SSR, sensitive incremental #SSR, st-Reach, 1-sensitive incremental ss-reach, 2-sensitive...")
- 10:29, 15 February 2023 Admin talk contribs created page Sensitive incremental (Created page with "{{DISPLAYTITLE:sensitive incremental #SSR (Vertex Reachability)}} == Description == A data structure with sensitivity $d$ for a problem $P$ has the following properties: It obtains an instance $p$ of $P$ and is allowed polynomial preprocessing time on $p$. After the preprocessing, the data structure must provide the following operations: (Batch) Update: Up to $d$ changes are performed to the initial problem instance $p$, e.g., $d$ edges are added to or removed from $p...")
- 10:29, 15 February 2023 Admin talk contribs created page OuMv (Redirected page to Online Vector-Matrix-Vector Multiplication) Tag: New redirect
- 10:29, 15 February 2023 Admin talk contribs created page Online Vector-Matrix-Vector Multiplication (Created page with "{{DISPLAYTITLE:Online Vector-Matrix-Vector Multiplication (Matrix-Vector Multiplication)}} == Description == Let $M$ be a binary $n \times n$ matrix than can be preprocessed. After preprocessing $n$ vector pairs $(u^1, v^1), \ldots, (u^n, v^n)$, arrive one at a time and the task is to compute $(u^i)^T M v^i$ before being presented with the $i+1$th vector pair for every $i$. == Related Problems == Related: Online Matrix-Vector Multiplication == Parameters == <...")
- 10:29, 15 February 2023 Admin talk contribs created page OMv (Redirected page to Online Matrix-Vector Multiplication) Tag: New redirect
- 10:29, 15 February 2023 Admin talk contribs created page Online Matrix-Vector Multiplication (Created page with "{{DISPLAYTITLE:Online Matrix-Vector Multiplication (Matrix-Vector Multiplication)}} == Description == We are given an $n \times n$ matrix $M$ and will receive $n$ column-vectors of size $n$, denoted by $v_1, \ldots , v_n$, one by one. After seeing each vector $v_i$, we have to output the product $Mv_i$ before we can see the next vector. == Related Problems == Related: Online Vector-Matrix-Vector Multiplication == Parameters == <pre>n: dimension of square matr...")
- 10:29, 15 February 2023 Admin talk contribs created page Minimum Weight k-Cycle (Redirected page to Shortest k-Cycle) Tag: New redirect
- 10:29, 15 February 2023 Admin talk contribs created page Shortest k-Cycle (Created page with "{{DISPLAYTITLE:Shortest k-Cycle (Graph Cycles)}} == Description == Given a graph $G=(V,E)$ with non-negative weights, find a minimum weight cycle of length $k$. == Related Problems == Generalizations: Shortest Cycle == Parameters == <pre>n: number of vertices m: number of edges k: length of cycle</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" sty...")
- 10:29, 15 February 2023 Admin talk contribs created page Minimum Weight Cycle (Redirected page to Shortest Cycle) Tag: New redirect
- 10:29, 15 February 2023 Admin talk contribs created page Shortest Cycle (Created page with "{{DISPLAYTITLE:Shortest Cycle (Graph Cycles)}} == Description == Given a graph $G=(V,E)$ with non-negative weights, find a minimum weight cycle. == Related Problems == Subproblem: Shortest k-Cycle == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" style="text-align:center;" width="100%"...")
- 10:29, 15 February 2023 Admin talk contribs created page Price Query (Created page with "{{DISPLAYTITLE:Price Query (Price Query)}} == Description == For a graph with edge weight function $c : E \rightarrow Z$, a price query is an assignment of node weights $p : V \rightarrow Z$. Such a query has a yes answer if and only if there is a $(u,v) \in E$ such that $p(u) + p(v) > c(u,v)$. (Intuitively, the $p(v)$ are “prices” on the nodes, the $c(u,v)$ are costs of producing $u$ and $v$, and a price query asks if there is an edge we are willing to “sell”...")
- 10:29, 15 February 2023 Admin talk contribs created page Independent Set Queries (Created page with "{{DISPLAYTITLE:Independent Set Queries (Independent Set Queries)}} == Description == For a graph $G=(V,E)$ and a given subset of vertices $S\subseteq G$, answer the query of the form "is $S$ an independent set?" == Parameters == <pre>n: number of vertices m: number of edges</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Reductions FROM Problem == {| class="wikitable sortable" style="text-align:center;" width=...")
- 10:29, 15 February 2023 Admin talk contribs created page APMW (Redirected page to All Pairs Minimum Witness) Tag: New redirect
- 10:29, 15 February 2023 Admin talk contribs created page All Pairs Minimum Witness (Created page with "{{DISPLAYTITLE:All Pairs Minimum Witness (Minimum Witness)}} == Description == Fix an instance of negative triangle with node sets $I, J, K$ and weight function $w$. Let $i \in I, j \in J, k \in K$. Recall that the triple $(i, j, k)$ is a negative triangle iff $(w(i, k) \odot w(k, j)) + w(i, j) < 0$. Fix a total ordering $<$ on the nodes in $K$ in the negative triangle instance. For any $i \in I, j \in J$, a node $k \in K$ is called a minimum witness for $(i, j)$ if $(...")
- 10:29, 15 February 2023 Admin talk contribs created page Minimum Witness Finding (Created page with "{{DISPLAYTITLE:Minimum Witness Finding (Minimum Witness)}} == Description == Fix an instance of negative triangle with node sets $I, J, K$ and weight function $w$. Let $i \in I, j \in J, k \in K$. Recall that the triple $(i, j, k)$ is a negative triangle iff $(w(i, k) \odot w(k, j)) + w(i, j) < 0$. Fix a total ordering $<$ on the nodes in $K$ in the negative triangle instance. For any $i \in I, j \in J$, a node $k \in K$ is called a minimum witness for $(i, j)$ if $(i,...")
- 10:29, 15 February 2023 Admin talk contribs created page Multiple Local Alignment (Created page with "{{DISPLAYTITLE:Multiple Local Alignment (Local Alignment)}} == Description == Given $k$ input strings and a scoring function on pairs of letters, one is asked to find the substrings of the $k$ input strings that are most similar under the scoring function. == Related Problems == Generalizations: Local Alignment == Parameters == <pre>k: number of input strings n: length of input strings?</pre> == Table of Algorithms == Currently no algorithms in our databas...")
- 10:29, 15 February 2023 Admin talk contribs created page Local Alignment (Created page with "{{DISPLAYTITLE:Local Alignment (Local Alignment)}} == Description == Given two input strings and a scoring function on pairs of letters, one is asked to find the substrings of the two input strings that are most similar under the scoring function. == Related Problems == Subproblem: Multiple Local Alignment == Parameters == <pre>n: length of input strings?</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Red...")