The algorithms tag has no wiki summary.

**0**

votes

**0**answers

41 views

### all paths between two nodes of an grid structure [on hold]

i have an 5*5 matrix numbered from 1 to 25. i wanted to print all paths between any two nodes.
...

**11**

votes

**1**answer

200 views

### Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the optimal solution?

This is inspired by a recent question.
Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the ...

**20**

votes

**10**answers

9k views

### Algorithm for finding the volume of a convex polytope

It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...

**19**

votes

**4**answers

1k views

### does the “convolution theorem” apply to weaker algebraic structures?

The Convolution Theorem is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse ...

**-3**

votes

**0**answers

57 views

### Messages on rotating wheels [on hold]

The question is: Would it be possible display a message (image, logo, text, ...) on a rotating wheel so that it would become readable once rotating at a certain speed, knowing that our brain will ...

**0**

votes

**2**answers

93 views

### Generate all non-isomorphic partitions $\pi = \{ \{1, …, n-1\}, \{n\} \}$ for all graphs of order $n$

Let $G$ be any connected, undirected, and unweighted graph of order $n$.
Let $\pi = \{ \{ 1, ..., n-1 \}, \{ n \} \}$ be partitioning of $G$ such that always $n-1$ vertices are in the first cluster ...

**1**

vote

**1**answer

71 views

### Algorithm to generate a (pseudo-) random high-dimensional function

I don't mean a function that generates random numbers, but an algorithm to generate a random function.
"High dimension" means the function is multi-variable, e.g. a 100-dim function has 100 different ...

**4**

votes

**0**answers

28 views

### Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time

A digraph is called weakly connected if its underlying undirected graph is connected.
You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of ...

**0**

votes

**1**answer

180 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

**3**

votes

**1**answer

140 views

### Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...

**12**

votes

**1**answer

833 views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...

**5**

votes

**4**answers

156 views

### From a (not positive definite) Gram matrix to a (Kac-Moody) Cartan matrix

Suppose I am given a symmetric matrix $G_{ij}$ with $G_{ii} = 2$. Can I always find an invertible integer matrix $S$ such that $(S^T G S)_{ii}=2$ and $(S^T G S)_{ij} \leq 0$ for $i \neq j$? Is there a ...

**19**

votes

**1**answer

216 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**1**

vote

**1**answer

161 views

### Finding the “minimum norm” of points in projective space above a prime field

I am working on doing explicit computations finding class groups of quaternions over $\mathbb{Q}$, and the following question (with $n=3$) was a clear choking point:
Given a point $P = [x_0, \dots, ...

**9**

votes

**3**answers

349 views

### Computing minimal polynomials using LLL

I would like to use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL algorithm) to compute the minimal polynomial of a (real) algebraic number $\alpha$ from a decimal approximation ...

**-4**

votes

**1**answer

148 views

### Without the use of a calculator, how to calculate the logarithm of 2 and 3 in base 10 [closed]

Without the use of calculator how to calculate $\log_{10} ~2$, $\log_{10} ~3$?

**4**

votes

**1**answer

544 views

### Finding the vertices of a convex polyhedron from a set of planes

I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.
...

**1**

vote

**1**answer

132 views

### Using Jacobi fields to approximate parallel transport along geodesic:is the following limit true?

I apologize if this is not a research level question (already tried asking http://math.stackexchange.com/questions/1303288/relation-between-parallel-transport-and-jacobi-field-iion stack exchange with ...

**8**

votes

**1**answer

98 views

### Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|)$ time

I have the book "Handbook of Computational Group Theory", by Derek Holt, and in it is a section on finding the transversal of a subgroup. Recall a transversal of a subgroup $H$ of $G$ is a single ...

**12**

votes

**4**answers

4k views

### Fast computation of multiplicative inverse modulo q

Given a large number $q$ (say, a prime) and a number $a$ between 2 and $q-1$ what is the fastest algorithm known for computing the inverse of $a$ in the group of residue classes modulo $q$?

**7**

votes

**2**answers

139 views

### Isomorphism problem on the class of induced subgraphs of a hypercube

A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic.
Now it feels to me that this class of graphs is "too ...

**0**

votes

**0**answers

52 views

### Finding a “special” non singular submatrix

Given a square integer matrix $A \in M_n(Z)$ and two subsets $I, J \subset \{ 1, \ldots, n\}$, we define $A_{I,J}$ as the sub-matrix of $A$ containing the rows (resp. columns) whose index is in $I$ ...

**5**

votes

**0**answers

155 views

### Is there a reasoned derivation of the coherence conditions for symmetric rig categories?

I know what the coherence conditions are, I can look them up in
M. Laplaza, Coherence for distributivity, Lecture Notes in Mathematics 281, Springer Verlag, Berlin, 1972, pp. 29-72.
In theory, ...

**2**

votes

**2**answers

161 views

### Paper of Denis Simon on quadratic equations in dimensions 4, 5?

In several places I have come across references to a 2005-6 preprint of Denis Simon entitled
Quadratic equations in dimensions 4, 5, and more
This paper gives fast algorithms to find isotropic ...

**7**

votes

**3**answers

3k views

### Solving a system of linear inequalities — what is the dimension of the solution set?

It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$?
For the applications I have in mind the ...

**5**

votes

**2**answers

190 views

### Ordered lattice point enumeration

I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community.
Setup: Let ...

**5**

votes

**1**answer

3k views

### Determine if you can build a polygon from segments [closed]

Is there a way to determine whether it is possible to build a polygon from given n segments?
Maybe triangle inequality generalized?

**4**

votes

**2**answers

239 views

### Breaking a rectangle into smaller rectangles with small diagonals

Say I am given a rectangle with dimensions $a \times b$ and an integer $n$. I'd like to break this rectangle into $n$ smaller rectangles $R_i$, and I'd like to make the maximum diagonal of any of ...

**23**

votes

**5**answers

2k views

### What is a good method to find random points on the n-sphere when n is large?

As part of a more complex algorithm, I need a fast method to find random points of the n-sphere, $S^n$, starting with a RNG (random number generator). A simple way to do this (in low dimensions at ...

**7**

votes

**2**answers

291 views

### Minimum number of unit fractions to sum up a given positive rational

For any positive $p,q\in\mathbb{N}$ there is a finite subset $S$ of $\{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $\sum_{s\in S} s=\frac{p}{q}$, see this article by Paul Erdös and Sherman Stein ...

**2**

votes

**1**answer

101 views

### Positive rational numbers as sum of unit fractions [duplicate]

Let $U = \{\frac{1}{n}: n\in\mathbb{N}, n>0\}$ be the set of unit fractions. For integers $m,n>0$ there is always a finite subset $S\subseteq U$ such that $\frac{m}{n} = \sum_{u\in S} u$, see ...

**8**

votes

**0**answers

130 views

### Complete list of exceptions and efficient algorithm for Waring's problem

2 weeks ago, Samir Siksek http://arxiv.org/abs/1505.00647 proved more than 150-years-old conjecture that every positive integer other than 15, 22, 23, 50, 114, 167, 175, 186, 212, 231, 238, 239, 303, ...

**8**

votes

**1**answer

693 views

### When the Lovász theta-function saturates its upper bound

The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, ...

**2**

votes

**0**answers

63 views

### A basic minimization problem over finite fields

Let $p$ be a prime, and suppose we are given $n$ values mod $p$: $a_1,...,a_n\in Z_p$. Is there a fast algorithm for finding $\alpha\in Z_p$ which minimizes the value $\max_i (\alpha\cdot a_i$ mod ...

**5**

votes

**1**answer

319 views

### Finding a basis for the (linear combinations) span of a matrix group, efficiently?

I have an algorithm whose bottleneck is the following task:
Let $\mathbb{F}$ be a finite field.
Given a set of $k$ invertible matrices $g_1,\dots,g_k\in GL_n(\mathbb{F})$, let
$G=\langle ...

**5**

votes

**1**answer

336 views

### How many random matrices does it take to generate a matrix algebra?

Let $\mathbb{F}$ be a finite field.
Let $A\le \mbox{Mat}_n(\mathbb{F})$ be a matrix algebra.
Is there a good bound on the number $k$ of random elements $a_1,\dots,a_k\in A$
that one needs to take ...

**5**

votes

**2**answers

506 views

### Find minimum-area ellipse which encloses two ellipses

I need an efficient algorithm to find the ellipse with the smallest possible area which encloses two given ellipses. The given ellipses are constrained to have coincident centers at the origin but can ...

**2**

votes

**0**answers

202 views

### Find minimum-area ellipse enclosing a set of ellipses, all centered at the origin

Given a set of N > 2 (two-dimensional and coplanar) ellipses, all centered at the origin, how do I find the ellipse with the minimum area which encloses all of them?
Background:
Thanks to Will Jagy ...

**4**

votes

**0**answers

163 views

### What is the complexity of intersecting two matrix algebras over a finite field?

The following question arose in a joint project with Arkadius Kalka and Adi Ben-Zvi.
Let $\mathbb{F}$ be a finite field, and $M_n(\mathbb{F})$ be the $n\times n$ matrices over $\mathbb{F}$.
For a ...

**4**

votes

**1**answer

201 views

### Constructing the oracle for Grover's algorithm

For a final project in my class, I decided to try to simulate a quantum computer and implement Grover's algorithm. I followed this excellently written blog post by Craig Gidney, and was successful in ...

**18**

votes

**2**answers

2k views

### Distinct numbers in multiplication table

Consider multiplication table for numbers $1,2,\cdots, n$. How many different numbers are there? That is how many different numbers of the form $ij$ with $1 \le i, j \le n$ are there?
I'm interested ...

**1**

vote

**1**answer

185 views

### Can we find structure constants of Lie Algebra for Lie Symmetry of ODE without solving determining equations?

Let's consider (for example) one scalar ODE.
We are searching for Lie Symmetries of it.
There is well-known result, that we can find size of Symmetry Group without solving determining equations.
...

**3**

votes

**1**answer

122 views

### Computionally efficient vertex enumeration for (convex) polytopes

Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be ...

**1**

vote

**1**answer

167 views

### Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier

Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$.
Q1. What is the least time complexity
possible/known for recreating the
...

**11**

votes

**1**answer

457 views

### Can Shor's Algorithm be modified to run efficiently on a classical computer?

Shor's algorithm is an algorithm which factors integers in polynomial time on a quantum computer. If one tries to run it on a classical computer, one runs into the problem that the state vector that ...

**18**

votes

**3**answers

616 views

### Is there a way of canonically labelling permutation groups?

When working with large numbers of graphs, a canonical labelling routine is essential as, after the initial cost of canonically labelling each graph, it permits isomorphism checks to be replaced with ...

**4**

votes

**1**answer

295 views

### Generating non-isomorphic graphs by adding edges to a given graph

This question is in a way related to the one I posted on math.se. Since the question there did not produce any final answer I am trying my luck here!
I am given a fairly large graph $G$ and subsets ...

**4**

votes

**0**answers

134 views

### Minimum number of real multiplications to multiply two quaternions [closed]

Karatsuba multiplication of two complex numbers can be performed with just three real multiplications (instead of four) as follows:
$$(a+bi)(c+di) = (ac-bd) + i ((a+b)(c+d) - ac-bd)$$
We only need the ...

**4**

votes

**0**answers

107 views

### What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...

**4**

votes

**2**answers

764 views

### Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq ...