Questions tagged [algorithms]
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
1,562
questions
0
votes
0
answers
20
views
Time complexity of Magma's `NormEquation` for quadratic extensions of $2$-adic fields
Note: This is similar to, but easier than, a previous question I asked here. It is a different question! I'm hoping this one might get an answer because it concerns a standard algorithm, whereas the ...
4
votes
1
answer
145
views
Algorithms to count perfect matchings in near planar graphs
It is well known that counting perfect matchings is tractable in planar graphs (due to Kastelyn).
I am interested in classes of (for lack of a better word) "near" planar graphs (1-planar, ...
3
votes
0
answers
31
views
Implementation of Friedman's algorithm of reconstructing simple polytopes
In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
2
votes
1
answer
175
views
Generating all possible subsets in order of sum
Given a set of positive integers, I am looking for method to algorithmically generate all possible subsets in order of their sum. Because the the count of possible subsets is exponential ($2^n$), it ...
0
votes
0
answers
27
views
Prove the NP-hardness of the following problem: Whether there exists a partition for a set of data points
Can anybody help me prove the NP-hardness of the following question:
Given $x_0, x_1, ..., x_m \in \mathbb{R}^n$, determine whether there exists a partition $S\cup [m]\backslash S$, such that $x_0 \in ...
-1
votes
0
answers
32
views
What are the assumptions when dealing with the EM Algorithm in order to calculate $f_{\textbf{Y}|\textbf{X},\theta}(\textbf{Y}|\textbf{X},\theta)$?
Consider the EM Algorithm. In order to apply it, we are given the observed data $\textbf{X}$ (generated by some distribution depending on some parameters), which can be a vector, a matrix or a matrix ...
0
votes
0
answers
64
views
What is the complexity of computing isomorphism of two non-regular graphs?
Regular graphs are the graphs in which the degree of each vertex is the same. Much research has gone into investigating isomorphism of regular graphs, and we know that computing isomorphism for ...
0
votes
0
answers
23
views
Building hypercubes from the bottom up
let $H^k$ denote a $k$-dimensional hypercube in a complete symmetric graph $G(V,E)$ without self-loops and parallel edges; let $|V|=2^n$ be the number of vertices.
setting
$\mathbb{H}^0 := V$, i.e. ...
1
vote
0
answers
62
views
Algorithm to generate configurations with kissing number 12
That the kissing number of a sphere in dimension 3 is 12 is well known. However, it is also known that there is a lot of empty space between the 12 spheres. I deduce (am I wrong?) that there are many ...
14
votes
3
answers
2k
views
Guaranteed correct digits of elementary expressions
Let $E$ be the set of elementary expressions, defined as the smallest set of mathematical expressions such that $1 \in E$, and if $a,b \in E$ then $a + b$, $a - b$, $ab$, $a/b$, $\exp(a)$, $\log(a)$ ...
1
vote
0
answers
60
views
A small lemma on cache resets (Bloom filters in particular)
Assume a fixed set of message $D$ and an associated distribution for selecting each message $d_i$ such that the total probability $\sum_{i \in D} d_i = 1$. We create a cache with $M$ bits and $k$ ...
2
votes
0
answers
91
views
What is the complexity / name of word search problem in linear groups?
This is a question about a search problem associated with user6976's question. Suppose we are given a finite set of elements $S \subset \mathrm{GL}_n(\mathbb{Q})$ containing inverses of all its ...
1
vote
0
answers
93
views
Algorithms to decompose a graded module over $R[x]$, where $R$ is a PID
There is a certain class of objects, which can be thought of either as modules over a ring $R[x]$ or as functors. A few equivalent definitions are given below. The question is what computer algorithms ...
0
votes
0
answers
36
views
Weighted matroid intersection algorithm
From Combinatorial Optimization, Theory and Algorithms, Sixth Edition, 2018, by Bernhard Korte and Jens Vygen:
...
1
vote
0
answers
38
views
Recurrence relation quicksort median-of-three
I am looking for a recurrence relation that describes the average number of comparisons of the quicksort algorithm considering an input array of size $n$. If the pivot element is picked randomly, the ...
32
votes
3
answers
2k
views
Are these fast convergent series for $\log(2)$, $\log(3)$ and $\log(5)$ already known and proven?
Updated on Feb.16.2024
Fortunately for three of these series, Eqs. (1), (3) and (4), I have found a proof using classical methods which I placed in the Answers section below. (I doubt that there is a ...
0
votes
0
answers
23
views
Online algorithms for MSTs from time series
Is it possible to construct the MST (minimum-weight spanning tree) for an potentially infinite sequence of points $\lbrace (i,Y[i]): i\in\mathbb{N}_0,\,c_{\text{min}} \le Y[i]\le c_{\text{max}}\rbrace$...
2
votes
1
answer
109
views
Convexity of a function
Let: $F_{j+1,y}(s)$ be the cumulative distribution function of a binomial distribution with mean $y$, $j+1$ independent trials considered for $s$ successes. Is it possible to show in any way that:
$\...
1
vote
0
answers
159
views
Fast algorithm for computing certain signal transformations
Let $f,g,h:\mathbb Z\to\mathbb C$ supported on $[-n,n]$. For $\tau\in \mathbb Z$, let $\operatorname{sh}_\tau f$ be the shift of $f$ by $\tau$ (i.e. $(\operatorname{sh}_\tau f)(t) = f(t-\tau)$). ...
4
votes
3
answers
286
views
How to recover integer part from known fractional root part?
Suppose you have $r=n+f$ where $n\in\mathbb{N}$ and $f\in (0,1)$. I know that $r^2$ is an integer and I can also get as many digits of $f$ as I like, is there a way to recover the value of $n$?
Thank ...
5
votes
0
answers
78
views
Recovering a binary function on a lattice by studying its sum along closed walks
I recently posted this question on MSE. While it attracted interest, no answers were submitted, so I thought to try and post it here.
I have a binary function $f:\mathbb N^2\rightarrow\{0,1\}$. While ...
5
votes
1
answer
187
views
Bounds on how many Sidon sets required to cover an integer range from 0-N
If I have a range from 0-N (0,1,2,3...N) and I want to cover that set with some number of Sidon sets, is there a tighter bound than N for how many sets I would need.
For instance:
0,1,2,3
can be split ...
0
votes
0
answers
13
views
Complexity of finding single source paths with capacity constraints and length constraints
Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...
1
vote
0
answers
68
views
(Hyper)Graph canonical labeling - Optimizing for subgraphs [Nauty/Traces?]
To a hypergraph, we can apply the following transformations:
[Vertex Removal of Type A] Remove a specified vertex from the hypergraph. As for the edges that contained this vertex, remove all of these ...
0
votes
0
answers
146
views
Solve NP-hard type problems with linear programming
I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force.
I ask this ...
1
vote
1
answer
196
views
Calculating the value of periodic continued fractions with $a_i\in\lbrace 0,1\rbrace$
Question:
How can the value of continued fractions of the form
$$y:=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\begin{align}\ddots& \\ &a_{n-1}+\cfrac{1}{a_n+y}\end{align}}}}}$$
$$...
0
votes
0
answers
29
views
Minimizing the number of grid squares to cover a polygon
Given an arbitrary polygon, and a grid square size x, I'd want to find a placement of the polygon such that it covers the minimum amount of cells in the grid.
The ...
2
votes
0
answers
475
views
Are these finite semirings known?
I am trying to prove the properties below, and by doing this, I hope to find a way to speed up the computation of the below defined addition and multiplication. I am also interested if these finite ...
1
vote
0
answers
65
views
Given a group $G$, is there any algorithm / method to check whether a group is sequenceable, or this problem is NP- hard?
The title of the question says it all: just recall that
A non-trivial finite group $G$ of order $n$ is said to be sequenceable if its elements can be arranged in a sequence $(b_1, b_2,\ldots , b_n)$ ...
2
votes
1
answer
149
views
Metropolis-Hastings kernel in measure theory
I'm facing difficulties in formulating the Metropolis-Hastings kernel for a specific problem where I need to sample from a probability distribution involving both discrete and continuous degrees of ...
2
votes
1
answer
187
views
Slicing bivariate exponential generating functions on x and y
Let $F(x, y) = e^{y D(x)}$ be a generating function for sets of objects enumerated by $D(x)$ that also keeps track of the number of sets (enumerated by the variable $y$, while $x$ enumerates the total ...
0
votes
0
answers
35
views
Consider the probability of connecting the terminal vertices using Binary Decision Diagram with length constraint
Definitions
Given an undirected graph $G=(V,E,p),p:E \to [0,1]$ where $V$ is the set of vertices, $E$ is the set of edges and $m=|E|$, and $p$ represents the probability that an edge functions. A set ...
0
votes
1
answer
177
views
Can we integrate arbitrary rational functions of Jacobian elliptic functions?
We can integrate arbitrary rational functions of the trigonometric functions because of the tangent half-angle substitution (https://en.m.wikipedia.org/wiki/Tangent_half-angle_substitution). This led ...
4
votes
2
answers
275
views
Approximating a fraction with a given denominator
Let $M$, $N$ be large natural numbers (say ~200 bits). Let $L$ be a smaller number, (say ~100 bits).
I want to approximate the fraction:
$$\frac{M}{N} \sim \frac{k}{L+r}$$
where $r$ is at most $L$. In ...
3
votes
0
answers
86
views
Efficient multiplication of Cayley-Dickson numbers
The question was already asked here, but doesn't have any meaningful answer, hence I'd like to re-post it.
Assuming that we have an algebra with conjugation, we can use Cayley-Dickson construction to ...
5
votes
1
answer
299
views
Recover unknown vector through shifted argmax queries
$\DeclareMathOperator*{\argmax}{arg\,max}$
I am interested in finding an efficient algorithm for the following problem:
Let $x \in [0,1]^n$ be some vector, with $x_n = 1$.
We want to recover $x$, ...
2
votes
0
answers
73
views
Minimum cost k-edge connected subgraph
The problem of finding a k-edge connected spanning subgraph with the minimum number of edges is $ \mathcal{NP} $-hard in general. Is it the case for positive weighted graphs with "fractional ...
7
votes
1
answer
243
views
Efficiently computing $\sum_k x^{k^2}$ modulo $p$
Let $p$ be prime. There is a whole host of "large" degree polynomials that can be computed efficiently modulo $p$. I was wondering if:
$$q(x) = \sum_{k=0}^{p-1} x^{k^2}$$
is a polynomial ...
2
votes
0
answers
60
views
Degeneracy and the "Linear Degeneracy Testing" problem
The Affine Degeneracy problem is about deciding whether $n$ given points in $\mathbb{R}^d$ (or $\mathbb{Q}^d$) are "in general position". i.e. there is no $d+1$ tuple of points which lies in ...
4
votes
0
answers
123
views
Looking for a generalization of fast Fourier transform form for Gauss sums
I want to compute quickly compute a sum of the form
$$\sum_{k=0}^{N}\sum_{l=0}^{M} e(g^{a^k*b^l})$$
Assume $a^N = b^M = 1$ modulo $q-1$.
Where $e(x) = e^{2\pi ix /q}$. This is very similar to the ...
2
votes
1
answer
361
views
Implementing the $\pi$ BBP algorithm
The formula
$$\pi = \sum_{k=0}^\infty \frac{1}{16^k} \left( \frac{4}{8k + 1} - \frac{2}{8k + 4} - \frac{1}{8k + 5} - \frac{1}{8k + 6}\right)$$
is a basis of the BBP algorithm for calculating arbitrary ...
0
votes
1
answer
87
views
Graph vertices selection for paths sum minimalization
Let $G = (V, E)$ be a simple, finite, weighted, undirected, connected graph. Let $P = \{p_{ij}, p_{kl}, p_{il}, ... \}$ be a set of paths, where $p_{ij}$ is a path from $i$-th to $j$-th vertex. Is ...
4
votes
1
answer
196
views
Is there a Bailey–Borwein–Plouffe (BBP) formula for $\gamma$ (euler-mascheroni constant)?
I was reading about BBP type formulas and there was a lot about $\pi$ and some $\log$'s. I started searching for some other constants and could find $2$ formulas for the catalan constant and learned ...
4
votes
2
answers
189
views
Algorithm for grouping tetrahedra from Voronoi diagram
I have a set of 3D Voronoi generator points and their neighbouring points, which, when connected, should result in a Delaunay tetrahedralization. However, I'm having a hard time implementing this. My ...
5
votes
1
answer
271
views
Questions about algorithms for permutation groups
Let $G < S_n$ be a permutation group of degree $n$, $\mathcal{P(n)}$
denote the set of all partitions of $n$, and $c: G \rightarrow
\mathcal{P}(n)$, where $c(g)$ is the partition given by the ...
5
votes
0
answers
135
views
A non-trivial (not a concatenation of de Bruijn sequences) infinite binary sequence whose initial $2^{n+1}$ bits contain all $n$-bit words for any $n$
Does there exist an infinite binary sequence $B$ that satisfies all of the following three properties?
It is possible to prove that for any integer $n$ the initial $2^{n+1}$ bits of $B$ contain all $...
0
votes
0
answers
24
views
Calculating minimum weight matchings in graphs with self-loops
Question:
which of the minimum-weight perfect matching algorithms can properly deal with the presence of self-loops?
The motivation for the question is the calculation of minimum-weight 'imperfect' ...
12
votes
1
answer
929
views
Apéry's constant $\zeta(3)$ fastest convergent series
UPDATE Feb.02.2024
The series below, Eq.(3) for computing and Eq.(2) for verifying, were applied by Andrew Sun on Dec.22.2023 to get over $2\cdot10^{12}$ decimal digits and break the number of ...
1
vote
0
answers
135
views
Complexity of calculating the expectation of $\operatorname{Tr} h(A)$, $A$ is a random matrix
$A$ is a $d_1\times d_1$ random matrix. Given $\{g_i\}~(1\leq i\leq n)$ iid Gaussian variables, $f_{ij}(g_1,g_2,...,g_n)~(1\leq i,j\leq d_1)$ are degree-$d_2$ polynomials. And $f_{ij}\equiv f_{ji}~(\...
0
votes
0
answers
46
views
Approximation factor for TSP Algorithm
The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...