# 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,581 questions
Filter by
Sorted by
Tagged with
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?
• 13.8k
1 vote
45 views

• 4,014
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: ...
1 vote
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 ...
• 24.6k
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 ...
• 53
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 ...
• 527
27 views

• 4,014
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 ...
133 views

• 620
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 ...
1 vote
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 ...
• 12.8k
1 vote
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 ...
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, ...
• 129
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 ...
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 ...
• 71
37 views

1 vote
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)$). ...
• 2,591
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 ...
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 ...
• 191