Skip to main content

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
2 votes
1 answer
85 views

On square root modulo $2^t-1$

Is there a way to compute an $x$ satisfying $$x^2\equiv a\bmod(2^t-1)$$ where $a,t$ are integers given to us and factorization of $2^t-1$ is not given to us?
Turbo's user avatar
  • 13.8k
1 vote
1 answer
45 views

Does Monotone (linear) convergence of iterates imply monotone (linear) convergence of function values?

I am considering a proof that would require a certain connection between convergence of iterates and corresponding function values: Consider an algorithm with iterates $\left\{{\mathbf{x}}^k\right\}_{...
AY Wer's user avatar
  • 11
12 votes
3 answers
665 views

When does $2$ arise when using the Euclidean algorithm to compute greatest common divisors?

When using the standard Euclidean algorithm to compute the greatest common divisor of a pair of relatively prime positive integers, the integer $2$ sometimes arises and sometimes does not. For example,...
Joel Louwsma's user avatar
2 votes
0 answers
95 views

Another (unique) algorithm for the A329369

Let $a(n)$ be A329369 (i.e, number of permutations of ${1,2,...,m}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \leqslant k ...
Notamathematician's user avatar
3 votes
2 answers
300 views

Algorithm to evaluate "connectedness" of a binary matrix

I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix: ...
Fabius Wiesner's user avatar
1 vote
0 answers
81 views

Non-vanishing of product of zero divisors in quotients modulo $n$

This might be of practical importance and even partial answer will help. Let $n$ be odd squarefree integer with known factorization $n=\prod p_i$ with $N$ prime factors. Later we are not asking about ...
joro's user avatar
  • 24.6k
0 votes
0 answers
168 views

On the integer solutions of the equation $y^2 = x^3 + n$

Let $n$ be a nonzero integer. I am interested in the integer solutions $(x, y)$ to the equation $y^2 = x^3 + n$. Let $S$ be the set of all integer solutions $(x, y)$ to this equation. I am wondering ...
lolipop's user avatar
  • 53
0 votes
1 answer
150 views

How to determine if a set is a sumset

Let $G$ be a commutative group (assume whatever you want on $G$ if needed. I am mainly interested in $G = \mathbb{Z}/n\mathbb{Z}$). Let $k$ be a fixed integer. Let $(a_1, \dots, a_{k^2})$ be a list of ...
user10676's user avatar
  • 527
0 votes
0 answers
27 views

Solving sparse bilinear systems with a relatively large number of variables

I'm trying to solve a bilinear system of equations over a finite field. (More specifically: I'm trying to find a single solution, if one exists.) The system consists of equations of the form $$y^T A_i ...
Sic Vis's user avatar
  • 101
0 votes
3 answers
95 views

Calculating variance-minimal perfect matchings

Question: are there any algorithms, resp. what can be recommended, for calculating perfect matchings with the property that the variance of their edge's weights is minimal?
Manfred Weis's user avatar
  • 12.8k
0 votes
0 answers
10 views

Enumerating the directed vertex-disjoint cycle covers of digraphs

A directed cycle-cover of a digraph $D$ is in the sense of this post equivalent to a perfect matching in the related undirected biadjacency graph $B$ in which the edges connect a vertex $u$ of $D$ in ...
Manfred Weis's user avatar
  • 12.8k
0 votes
0 answers
68 views

Touring a sequence of convex polygons with minimal energy

There is a known problem of touring a sequence of $n$ polygons: given a starting point $s$, an ending point $t$ and a sequence of polygons $P_1,\dots,P_k$ with a total of $n$ vertices, find points $...
ssss nnnn's user avatar
3 votes
0 answers
125 views

Fast and simple algorithm for the A329369

Let $a(n)$ be A329369 (i.e., number of permutations of $\{1,2,\cdots,m\}$ with excedance set constructed by taking $m-i$ ($0 < i < m$) if $b(i-1) = 1$ where $b(k)b(k-1)\cdots b(1)b(0)$ ($0 \...
Notamathematician's user avatar
2 votes
0 answers
237 views

Least number of circles required to cover a continuous function on $[a,b]$

I asked this question on MSE here. Given a continuous function $f :[a,b]\to\mathbb{R}$, what is the least number of closed circles with fixed radius $r$ required to cover the graph of $f$? It is ...
pie's user avatar
  • 453
2 votes
1 answer
111 views

On a efficient algorithm for factoring bivariate polynomials modulo composite modulus assuming the solution is unique

We found and implemented in sage efficient algorithm for factoring bivariate polynomials modulo composite modulus assuming the solution is unique up to a constant factor. More formally let $K=\mathbb{...
joro's user avatar
  • 24.6k
1 vote
1 answer
198 views

Correctness of the algorithm for the A329369, A347205 and related sequences

Let $a(n)$ be A347205. It is enough for us to know that $$ a(2^m(2k+1)) = \sum\limits_{j=0}^{m}a(2^jk), \\ a(0) = 1 $$ Let $b(n)$ be A329369. It is enough for us to know that $$ b(2^m(2k+1)) = \sum\...
Notamathematician's user avatar
2 votes
0 answers
168 views

NP-hardness of a string transformation problem with k templates

Given strings $x$ and $y$, a template length $l$, and a maximum number of different templates $k$, the task is to determine if it's possible to convert $x$ into $y$ using no more than $k$ different ...
Paul Calvi 's user avatar
0 votes
0 answers
133 views

Questions on integer matrix multiplication

Question 1: Given two integer matrices $A$ and $B$, and let $C$ be $AB$. $C$ can be very big in pratice, so what is the fastest way to compute the statistical data of $C$? For example, $$A=\begin{...
user369335's user avatar
0 votes
0 answers
44 views

Initial guess in shifted QR algorithm

I'm comparing timings of two implementations of algorithms for the computation of Gauss-Legendre nodes. 1 - The first is a Newton algorithm to find the roots of the Gauss-Legendre polynomials. Quite ...
G. Fougeron's user avatar
2 votes
0 answers
191 views

Finding specific coefficients of product of high-dimensional Fourier series faster than FFT

I need a fast algorithm to perform a specific Fourier-type computation in my physics research. Suppose I have the following two Fourier series in three dimensions $$ a(t_1,t_2,t_3)=\sum_{j=-n}^{n}\...
groupoid's user avatar
  • 620
4 votes
1 answer
237 views

Fibonacci and matrix modular exponentiation

I'm interested in a few problems that are related enough that I decided to put them all in one question. What are the fastest known algorithms for finding large Fibonacci numbers modulo $p^k$, and ...
TheBestMagician's user avatar
1 vote
1 answer
52 views

Complexity of maximum weight-sum matching for cycle graphs

I need to determine a matching with maximal weight-sum for a cycle graph with positive, negative and zero edge-weights. Question: What is the fastest way of calculating such a matching? Because of ...
Manfred Weis's user avatar
  • 12.8k
1 vote
0 answers
37 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 ...
Sebastian Monnet's user avatar
4 votes
1 answer
164 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, ...
Agile_Eagle's user avatar
4 votes
0 answers
41 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 ...
mashedcarrots's user avatar
2 votes
1 answer
262 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 ...
Ood's user avatar
  • 71
0 votes
0 answers
37 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
0 votes
0 answers
68 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.8k
1 vote
0 answers
64 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
  • 361
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$ ...
Birdy Nam Nam's user avatar
2 votes
0 answers
94 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,284
1 vote
0 answers
94 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
48 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
1 answer
104 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
37 votes
4 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,460
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.8k
2 votes
1 answer
139 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
169 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,591
4 votes
3 answers
301 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
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 ...
GSofer's user avatar
  • 191
5 votes
1 answer
196 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
14 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
86 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
155 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
200 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.8k
0 votes
0 answers
35 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
483 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
67 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

1
2 3 4 5
32