# 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,417 questions
Filter by
Sorted by
Tagged with
14 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
57 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 ...
117 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 ...
34 views

### Find number of overlapping edges in a one-dimensional graph

I have a set of edges $(v_1, v_2), (v_2, v_3),(v_2, v_4)$ where each edge has a weight. Say the weights are 1, 2 and 3 respectively. Then we can visualise it as 3 threads, where the the thread from ...
190 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 ...
364 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 ...
3k 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 ...
167 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 ...
1 vote
97 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 ...
57 views

51 views

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_{}^{} \... 1 vote 2 answers 190 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$? ... 0 votes 0 answers 44 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 ... 2 votes 1 answer 63 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 vote 1 answer 259 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 ... 7 votes 2 answers 773 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| \... 13 votes 2 answers 554 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 ... 4 votes 3 answers 217 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 236 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 ... 2 votes 1 answer 99 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 ... 1 vote 0 answers 378 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 ... 3 votes 1 answer 114 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 ... 0 votes 1 answer 36 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: ... 0 votes 1 answer 174 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 ... 4 votes 0 answers 163 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 ... 3 votes 0 answers 185 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. ... 0 votes 0 answers 64 views ### Do there exist methods for determining the orbits of a group action on the cartesian product of sets? Suppose that we have some group G acting on some set \Omega. Then G acts on \Omega^n = \Omega \times \cdots \times \Omega (n times) naturally. I wonder, is there an iterative algorithm to ... 2 votes 0 answers 40 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)\... 12 votes 0 answers 232 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 ... 2 votes 0 answers 45 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 ... 1 vote 1 answer 47 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$... 1 vote 2 answers 160 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$\...
1 vote
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 ...