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,564
questions
3
votes
1
answer
194
views
Checking presence of a specific term in product polynomial
I have a multivariate polynomial $P$ which is a product of $M$ low degree polynomials $p_i$
$$P(x_1, x_2, \dotsc, x_n) = \prod_{i=1}^M p_i(x_1, x_2, \dotsc, x_n)$$
where the maximum degree of each $...
- 103
17
votes
1
answer
951
views
Catalan's constant fast convergent series
NOTE. UPDATE 2 introduces proven series for Catalan's constant that is possibly the fastest currently known.
Working with some conjectured continued fractions that were published here, I have found ...
- 2,210
3
votes
0
answers
130
views
determine degree of boolean polynomial given as black box
I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
- 103
1
vote
1
answer
135
views
Interpreting optimal matchings as permutations
If $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ is the cost-matrix of an assignment problem, then the usual statement of the problem of finding an optimal assignment is to identify $n$ elements $a_{i,\,\...
- 12.7k
12
votes
1
answer
368
views
Euclid's algorithm as a combinatorial game
Consider the following two player game based on the Euclidean algorithm: Positions are given by $(a,b)$ in $\mathbb N^2\setminus\{(0,0)\}$ (where $\mathbb N=\{0,1,2,\ldots\}$) defining a greatest ...
- 17.5k
4
votes
0
answers
151
views
Two-player item picking game
Two players $A$ and $B$ play this game: There are $n$ items, where the $i$th item is of value $a_i$ to player $A$ and is of value $b_i$ to player $B$. Two players take turns picking items, and each ...
- 41
3
votes
3
answers
117
views
An efficient generalized algorithm to obtain an arbitrary element of a lexicographically ordered tuple of all balanced $l$-bit binary sequences
Assuming that $l>1$ is even, an $l$-bit binary sequence $b$ is balanced if and only if the number of zeroes in $b$ is equal to $l/2$.
Let $T_l$ denote a lexicographically ordered tuple of all ...
- 959
0
votes
1
answer
65
views
Maximum number of teams of fixed size over a score threshold
I am wondering if there is any literature on the following combinatorial optimization problem:
Input: $n, k, T\in \mathbb{N}$ and positive integers $s_1, \ldots, s_n$.
For intuition, we may think ...
1
vote
0
answers
71
views
Forming rational numbers using unique Egyptian fractions
Question: For a given rational number $r\in (0,1)$, does there exists a finite, ordered set $S\subset \mathbb{N}$ such that the product of the first $k$ elements of $S$ do not divide the $k+1$th ...
- 121
2
votes
1
answer
150
views
Verify if array is orthogonal
This is a repost from the computer science stackexchange. The question has been offered a bounty, but received no answers. Therefore, I would like to ask this question here.
Orthogonal arrays often ...
- 482
1
vote
1
answer
341
views
What is the minimum number of multiplications for $2\times 3$ and $3\times 2$ multiplication?
Strassen demonstrated a seven multiplication algorithm for $2\times 2$ matrix multiplication and Winograd showed its optimality.
Let $A$ be $2\times k$ and $B$ be $k\times 2$.
What is the minimum ...
- 13.7k
15
votes
1
answer
517
views
Make $n$ numbers equal using pairwise averages
Given $n$ rational numbers. Every time you can delete $2$ numbers, and add 2 numbers which are equal to $\frac{a+b}{2}$ (assume the number you delete is $a$ and $b$). How to judge whether it is ...
- 151
17
votes
4
answers
6k
views
Why is fast matrix multiplication impractical?
I am wondering why fast matrix multiplications are impractical, especially for Boolean matrix multiplication.
I read some content saying fast matrix multiplications are impractical because of large ...
- 279
8
votes
1
answer
252
views
Algorithmically handling the Spin groups in larg(ish) dimensions
Question: Is there a reasonably efficient algorithmic representation of $\mathit{Spin}_n$? By this I mean, a way to store its elements and operate on them (multiply, inverse, maybe compute ...
- 30.2k
1
vote
1
answer
117
views
Is there an efficient generalized algorithm to generate a set of binary words satisfying a particular cross-correlation property?
In this question, the term “word” implies a binary word, i.e. a sequence of bits.
Let $W(w)$ denote the number of non-zero bits in a word $w$.
Assuming that $l \geq 2$ is even, an $l$-bit word $w$ is ...
- 959
3
votes
0
answers
105
views
Tight bounds on the iterates of the Clenshaw algorithm for Chebyshev polynomials
I'm trying to bound the iterates of the Clenshaw algorithm when applied to the Chebyshev series, related to a question I'm running into related to the stability of this algorithm. Recall that, for $p(...
- 101
1
vote
2
answers
94
views
Minimum edge-weighted directed subgraph in polynomial time
I am looking for an algorithm with polynomial complexity where, given a strongly connected edge-weighted digraph I can find the minimal subgraph which connects some root vertex v to a known set of ...
- 13
4
votes
2
answers
274
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 259
10
votes
0
answers
423
views
Fast method to verify if a point belongs to a given convex $d$-polytope
We are given a $d$-dimensional convex polytope $P\in\mathbb{R}^d$. Assume we have all the supporting hyperplanes describing $P$ and its vertices. Let $S$ be a sequence of $n\gg 1$ points $\mathbb{R}^d$...
- 1,677
3
votes
1
answer
185
views
Algorithm to find a minimal normal subgroup of given group $G$ by matrix group representation
Given a matrix group $G$ by its generators i.e. $G =\langle A_1,A_2,...,A_k \rangle \leq GL_n(q)$, where each $A_i$'s are matrix in $GL_n(q)$
Q. Does there exist a polynomial time (polynomial in ...
- 151
7
votes
1
answer
346
views
Finding maximal prefix of a simple curve
Let $S$ be a simple curve. I want to determine maximal prefix of $S$ contained in a unit circle. Is this possible, or has it perhaps already been solved in the past, and I am just unable to find an ...
- 71
10
votes
1
answer
311
views
Can you get any natural number from 4 by performing given operations?
You can perform the following operations on numbers:
divide the number by 2,
add 0 or 4 at the end of the number.
Can you get any natural number from 4 by performing only these operations?
So far I ...
- 119
1
vote
0
answers
51
views
Standard test for the recognition of toroidal graphs
Is there a standard test for the recognition of toroidal graphs? I have been using the Boyer–Myrvold planarity algorithm, which has a MATLAB and C++ implementation.
- 11
1
vote
1
answer
58
views
Generate all strongly connected tournament
I want to generate all strongly connected tournament of size $n \in \{4, 11\}$.
As a strongly connected tournament has an hamiltonian path I may assume that $v_i v_{i+1}$ is always an arc, and $v_n ...
- 247
0
votes
0
answers
76
views
Get a specific number of points from a density distribution area to minimize the average distances
Assuming that an area $A$ on the plane has a known density distribution function $\rho (x, y)\geqslant 0$, now the goal is to obtain $n$ points $p_1, p_2, ..., p_n$ on the area so that $\iint_{}^{} \...
- 143
2
votes
2
answers
761
views
Efficiently finding the largest divisor of N less than sqrt(N)
Suppose you have a number
$$
N = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}
$$
and are looking for the largest divisor $d|N$ such that $d^2<N$ (that is, A060775$(N)$.) How can I efficiently find this $d$?
...
- 8,994
0
votes
0
answers
57
views
Impact of reducing the number of distinct elements in the Count distinct problem
I am dealing with the Count distinct problem and Space saving algorithm. The problem goes like that:
I have a stream of $N$ elements. The number of distinct elements is $D$. Space saving algorithm is ...
- 11
1
vote
1
answer
592
views
Efficient algorithm for edge-coloring complete graphs
Edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color with an optimal number of colors. Two edges are said to be adjacent if ...
- 1,130
1
vote
1
answer
293
views
Runtime for Terrible "Sorting Algorithm"?
Before I begin, I apologize for the bad wording. Consider the following "sorting algorithm":
Suppose there are $n$ books on the bookshelf labeled $1$-$n$, and ordered from left to right in a ...
- 59
7
votes
2
answers
890
views
Product of complex numbers on the unit circle with largest real part
Let $T = \{z_1, \ldots z_n\}$ be a finite set of complex numbers on the unit circle. I would like an algorithm which can quickly compute the nonempty subset $S \subset T$ which maximizes $$\left| \...
- 1,703
13
votes
2
answers
1k
views
Is irreducibility of polynomials $\in \mathbb{Z} [X]$ over $\mathbb{Q}$ an undecidable problem?
There are a number of criteria for determining whether a polynomial $\in \mathbb{Z} [X]$ is irreducible over $\mathbb{Q}$ (the traditional ones being Eisenstein criterion and irreducibility over a ...
- 230
6
votes
3
answers
759
views
Algorithm to calculate edge orbits of a graph
Vertex orbits are a well-known concept in Graph Theory: these are the equivalence classes of vertices under the automorphism group $Aut(G)$ of a graph $G$. In the example, circled vertices are ...
6
votes
1
answer
369
views
Groups in which Computational Diffie Hellman is in $P$ but Discrete Logarithm is not known to be in $P$
The Computational Diffie Hellman (CDH) problem is to compute $g^{XY}$ given $g^X$ and $g^Y$ where $g$ generates the group. The Discrete Logarithm (DLOG) problem is to compute $X$ given $g^X$. The ...
- 13.7k
2
votes
1
answer
185
views
Algorithm for compact polynomial expressions
Sometimes an ugly polynomial (perhaps in several variables) can be expressed as a small sum of much simpler polynomials. Can this be done algorithmically? More precisely:
Is there a reasonable
...
- 17.5k
1
vote
0
answers
490
views
How to describe all integer solutions to $x^2+y^2=z^3+1$?
The question is to find all integer solutions to the equation
$$
x^2+y^2=z^3+1.
$$
This equation obviously has infinitely many integer solutions (take, for example, $(x,y,z)=(1,u^3,u^2)$ for any ...
- 5,957
3
votes
1
answer
145
views
Binary cellular automata: How slowly can an eroder remove $1$'s?
Consider some deterministic, monotonic, eroding binary cellular automata on some lattice $\mathbb{Z}^d$, and consider the set of initial states $I(L)$ in which all of the vertices are $0$ except for ...
- 469
0
votes
1
answer
39
views
Reconstructing a 2-factor from its edge set
Let $G(V,E)$ be a symmetric graph with $n$ vertices and $m$ edges that has a $2\text{-factor}$ with edge set $F$, i.e. $F$ are the edges of an undirected vertex-disjoint cycle cover of $G$.
Question:
...
- 12.7k
1
vote
1
answer
248
views
Louvain method: Why do they drop coefficient 1/m in the official implementation?
Intro
I'm referring to the original paper Fast unfolding of communities in large
networks by Blondel et al. in this question and adopt their notation. Explanation for the used symbols is on page 4 ...
- 113
9
votes
1
answer
548
views
Is there a polynomial time algorithm for finding primes?
I was wondering if, given $k$, there is a deterministic polynomial time algorithm (polynomial in $k$) which finds a prime number with $k$ digits.
There is clearly a probabilistic one: just take random ...
- 1,241
3
votes
0
answers
362
views
Conversion of proofs between HoTT and ZFC
HoTT provides a foundation of math that remains mysterious for
many mathematicians including me. Hence this question.
There are several implementations of math based on ZFC, an
example being MetaMath. ...
- 5,038
2
votes
0
answers
49
views
Do there (or might there) exist computable invariants for Aut(G)-invariant subgraphs of a graph G?
I am interested in algorithms for computing all subgraphs (not necessarily induced) of a graph $G$ up to $Aut(G)$ isomorphism. I had the idea of partitioning the edges of the graph like so
$$\{F|E(G)\...
- 161
15
votes
1
answer
351
views
Are hyperbolic $n$-manifolds recursively enumerable?
Fixing a dimension $n \ge 4$, is the class of closed hyperbolic $n$-manifolds recursively enumerable?
Since hyperbolic manifolds are triangulable I can reformulate this in the following more explicit ...
- 3,349
2
votes
0
answers
49
views
Calculating permanents via Branch and Bound
Permanents can be interpreted as counting directed cycle covers of an asymmetric graph with unit cost edge weights.
That interpretation leads to a branch and bound algorithm for calculating the ...
- 12.7k
1
vote
1
answer
65
views
Steiner tree subject to edge capacity constraint
Given a network of routes modeled as a graph where each edge $e$ has a capacity $c_e$. We have a source node $s$ and a set of destination nodes $t_i$ ($1\le i\le k$). We need to transport $q_i$ ...
- 436
1
vote
2
answers
562
views
Does having the discrete logarithm of prime factors of $n$ allow us to calculate any discrete log more efficiently?
Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $\varphi(n)$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\...
- 221
1
vote
0
answers
94
views
Automated, algorithmic construction of bijective proofs of combinatorial identities
Let $a_n$ and $b_n$ be two different expressions in natural $n$ with values in the set of all nonnegative integers such that we have the identity $a_n=b_n$ for all $n$. As a simplest example, we may ...
- 118k
6
votes
0
answers
196
views
Where to cut off a double sum?
I have to compute a double infinite sum to within a given accuracy $\epsilon$. Let us say the sum is of the form
$$\sum_{m\geq 1} \sum_{n\geq 1} \frac{a_{m,n}}{m^2 n^2 \max(m,n)},$$
where $|a_{m,n}|\...
- 19.4k
2
votes
3
answers
296
views
Matrix-free linear solve for nullspace
I'm looking for an algorithm to solve for the classic:
$$A\mathbf{x} = \mathbf{b}$$
I cannot compute $A$ directly, but rather can compute matrix-vector products $A\mathbf{v}$ for any $\mathbf{v}$.
At ...
- 141
1
vote
1
answer
172
views
Construct a rooted plane tree with nodes labelled
A rooted tree is a tree with a distinguished root node. When a rooted tree is embedded in a plane, a cyclic ordering is induced on the subtrees of the root. Such trees are called rooted plane trees.
...
- 1,130
5
votes
1
answer
305
views
Inserting points into a polygon
I want to insert $n$ points into arbitrary polygon $P$ described by ordered list of its vertexes $v_1, v_2, ..., v_m$. Each inserted point must distanced from the others on distance at least $d$. In ...
