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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
55 views

Solving system of linear diophantine equations with exponential coefficients over the integers

In general, solving a system of linear diophantine equations over the integers is polynomial time solvable on the size of the coefficients of the equations. I am interested in an extension of this ...
user1868607's user avatar
0 votes
0 answers
21 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 ...
Robeto Leo's user avatar
1 vote
0 answers
86 views

How to know if a random natural number is a probable semiprime?

Let that $n\in\Bbb N$ generated from a hash function where $n$ is long enough to be hard to factor in the gnfs algorithm. How to check if $n$ is probably a semi‑prime in a faster way than factoring it ...
user2284570's user avatar
-1 votes
0 answers
31 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 ...
user1234's user avatar
  • 159
0 votes
0 answers
59 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 ...
Eauriel's user avatar
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. ...
Manfred Weis's user avatar
  • 12.6k
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 ...
GRquanti's user avatar
  • 111
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)$ ...
rosan98's user avatar
  • 199
1 vote
0 answers
59 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$ ...
Birdy Nam Nam's user avatar
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 ...
Fiktor's user avatar
  • 1,264
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 ...
GHPR's user avatar
  • 11
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: ...
Ray Butterworth's user avatar
1 vote
0 answers
37 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 ...
Martin Clever's user avatar
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 ...
Jorge Zuniga's user avatar
  • 2,202
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$...
Manfred Weis's user avatar
  • 12.6k
2 votes
1 answer
105 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: $\...
Marco Max Fiandri's user avatar
1 vote
0 answers
157 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)$). ...
Rami's user avatar
  • 2,571
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 ...
ReverseFlowControl's user avatar
5 votes
0 answers
77 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 ...
GSofer's user avatar
  • 191
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 ...
Bobby Morelli's user avatar
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 $...
Yossi Peretz's user avatar
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 ...
Johann Birnick's user avatar
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 ...
Juan Carlos's user avatar
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}}}}}$$ $$...
Manfred Weis's user avatar
  • 12.6k
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 ...
b9s's user avatar
  • 101
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 ...
mathoverflowUser's user avatar
1 vote
0 answers
64 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)$ ...
SUTANAY BHATTACHARJEE's user avatar
2 votes
1 answer
143 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 ...
Iris Allevi's user avatar
2 votes
1 answer
185 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 ...
Oleksandr  Kulkov's user avatar
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 ...
caaaaaat's user avatar
0 votes
1 answer
176 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 ...
Nomas2's user avatar
  • 303
4 votes
2 answers
273 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 ...
mtheorylord's user avatar
3 votes
0 answers
85 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 ...
Oleksandr  Kulkov's user avatar
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$, ...
Florian Tramèr's user avatar
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 ...
Bence's user avatar
  • 21
7 votes
1 answer
242 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 ...
mtheorylord's user avatar
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 ...
Tippisum's user avatar
  • 153
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 ...
mtheorylord's user avatar
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 ...
Nomas2's user avatar
  • 303
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 ...
Tomasz Rybotycki's user avatar
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 ...
Pinteco's user avatar
  • 521
4 votes
2 answers
187 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 ...
catmousedog's user avatar
5 votes
1 answer
270 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 ...
Victor Miller's user avatar
5 votes
0 answers
133 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 $...
lyrically wicked's user avatar
0 votes
0 answers
23 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' ...
Manfred Weis's user avatar
  • 12.6k
12 votes
1 answer
924 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 ...
Jorge Zuniga's user avatar
  • 2,202
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}~(\...
qmww987's user avatar
  • 49
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 ...
Mathematician....'s user avatar
1 vote
1 answer
110 views

Practical calculation of Canterbury approximants

I'm looking for references on how to compute Canterbury approximants numerically from a practical point of view. The references on Canterbury approximants that I am aware of all appear rather abstract ...
gmvh's user avatar
  • 2,758
6 votes
0 answers
145 views

Algorithmic representation of the Spin (and Pin) group [duplicate]

Performing algorithmic computations in $\mathit{SO}_n(\mathbb{R})$ or $\mathit{O}_n(\mathbb{R})$ is easy: its elements are represented by $n\times n$ orthogonal matrices of reals so, assuming we have ...
Gro-Tsen's user avatar
  • 29.8k

1
2 3 4 5
32