The algorithms tag has no usage guidance.

**10**

votes

**2**answers

364 views

### Continued Fractions from Digit Streams

let $x=\sum_{i=1}^{\infty}\delta_i2^{-i},\ \delta_i\in\{0,1\}$.
Is there an algorithm that converts the sequence $(\delta_0,\ \delta_1,\ ...)$ of the binary digits of $x$ to the sequence ...

**4**

votes

**0**answers

40 views

### Algorithm to express a point from a H-polyhedron as convex combination of extreme points

Let $P\subset\mathbb{R}^n$ be a convex polyhedron described as an intersection of hyperspaces, that is,
$$P:=\{\boldsymbol{x}: A\boldsymbol{x} \leq \boldsymbol{b}\}$$
Let $\boldsymbol{x} \in P$. We ...

**0**

votes

**0**answers

55 views

### Probability two random intervals overlap

I'm working on an algorithm for orthogonal line intersection detection and am trying to analyze some things about it. For simplicity, we can consider the problem as follows:
Given N randomly ...

**5**

votes

**0**answers

73 views

+50

### Biggest (or large) rectangle in a polytope

I need an efficient method to construct a (hyper)rectangle inside a polytope with a lot of dimensions (say $100 < d < 1000$). Ideally I'd want the biggest possible rectangle, but as I don't ...

**0**

votes

**1**answer

135 views

### A three variable linear diophantine promise problem

Given $a,b,c,s\in\Bbb N$ such that $(a,b,c)=1$ with promise that we have at most one triple $x,y,z\in\Bbb N$ such that $ax+by+cz=s$, what is a good algorithm that runs in $O(\log(abcs))$ time to find ...

**-1**

votes

**0**answers

51 views

### bound on the size of a circuit [closed]

I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested ...

**2**

votes

**1**answer

252 views

### Is there an algorithm to test whether a vector is an eigenvector of a power of a matrix?

Given a square matrix $A\in k^{n\times n}$ and a vector $x\in k^n$ over some field $k$, is there an algorithm to test whether there are $s\in\mathbb{N}$ and $\lambda\in k$ such that $A^sx=\lambda x$? ...

**0**

votes

**0**answers

77 views

### Coxeter Subgroups of Coxeter Groups

Is there an algorithm to determine all the Coxeter subgroups of a given Coxeter group? If we only want the Coxeter subgroups of finite index does that make the question easier? If we only want a ...

**7**

votes

**1**answer

106 views

### Determine if an $n$-dimensional mesh of simplices is a non-manifold

In an $n$-dimensional space I have a set of simplices where each simplex consists of facets. Some of the simplices are 'connected' by sharing facets. Each facet is made up on edges, each consisting ...

**21**

votes

**2**answers

736 views

### Groups where word problem is solvable, but not quickly?

Are there finitely generated groups whose word problem is solvable, but not quickly? It would be great to have specific examples, but existence results would also be helpful.
All of the groups that ...

**5**

votes

**0**answers

68 views

### Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...

**0**

votes

**0**answers

45 views

### Best measure for curve similarity

I would like to measure similarity between two curves represented by two arrays of points.
The similarity measure should not depend on the size of these shapes. Two similar shapes but have different ...

**5**

votes

**4**answers

349 views

### Deceptive linear algebra problem

Does anyone recognize this problem? There are $2p$ equations and $2p$ unknowns, and it feels like a classic, but I've never encountered it before:
Given $d_1, d_2, \ldots d_p$, find $a_1, a_2, \ldots ...

**2**

votes

**0**answers

219 views

### Partitioning graph for Graph Isomorphism

Motivation: I am studying graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases .
Construction:
$G$ is a $r$ regular graph, $k$ connected( not a complete , ...

**2**

votes

**1**answer

54 views

### Maximal opening angle of a polygon from a point [closed]

I'm looking for an algorithm that given a 2D convex polygon and point outside it, returns the two points of the polygon which are the two extremities of the polygon when viewed from that point.
One ...

**2**

votes

**1**answer

67 views

### Equality of Euclidean numbers / constructible numbers

Euclidean numbers are those real number that can be constructed from the natural numbers by a finite chain of +,-,*,/ and $\sqrt{}$. They are also called Constructible Numbers.
I am now interested in ...

**5**

votes

**1**answer

85 views

### Resource Constrained Routing with Refueling

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...

**2**

votes

**0**answers

194 views

### Does knowing $g, g^r, g^{r^2}, g^{r^3}, \dotsc$ sometimes offer a significant advantage in finding $r$?

Is there a cyclic group $\mathcal G$ with generator $g$ for which the discrete log problem is assumed to be hard, but knowing $g, g^r, g^{r^2}, g^{r^3}, \dotsc$ for random $r$ makes finding $r$ easy?
...

**10**

votes

**6**answers

960 views

### Algorithms for calculating R(5,5) and R(6,6)

Calculating the Ramsey numbers R(5,5) and R(6,6) is a notoriously difficult problem. Indeed Erdős once said:
Suppose aliens invade the earth and threaten to obliterate it in a year's time unless ...

**12**

votes

**1**answer

267 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 ...

**0**

votes

**2**answers

114 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 ...

**4**

votes

**0**answers

40 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 ...

**1**

vote

**1**answer

174 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, ...

**5**

votes

**4**answers

167 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 ...

**-4**

votes

**1**answer

156 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$?

**1**

vote

**1**answer

141 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

115 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 ...

**0**

votes

**0**answers

59 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$ ...

**7**

votes

**2**answers

147 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 ...

**5**

votes

**0**answers

160 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, ...

**3**

votes

**1**answer

110 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

137 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, ...

**2**

votes

**0**answers

68 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

343 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 ...

**4**

votes

**2**answers

262 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 ...

**3**

votes

**2**answers

168 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 ...

**4**

votes

**1**answer

237 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 ...

**9**

votes

**3**answers

359 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

**0**answers

167 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 ...

**3**

votes

**1**answer

156 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 ...

**11**

votes

**1**answer

481 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 ...

**4**

votes

**0**answers

140 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 ...

**5**

votes

**2**answers

202 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 ...

**4**

votes

**0**answers

143 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 ...

**0**

votes

**1**answer

108 views

### Is there a closed form for tan(q*pi) with q rational? [closed]

I'm looking for a closed-form expression for tan (q*pi) for q rational, or an algorithm that generates one, or some other means of compactly describing the closed-form without referencing an infinite ...

**1**

vote

**2**answers

207 views

### Algorithm for fast factorization of polynomial over $\mathbb Z$ or over $\mathbb F_p$

I want to fast decompose polynomial over ring of integers (original polynomial has integer coefficients and all of factors have integer coefficients) and also over ring of integers modulo prime ...

**4**

votes

**1**answer

64 views

### Smallest sum $S \geq k > 0$ using one element from each of several sets of nonnegative integers

Does there exist a way to efficiently solve the following problem?
Given some constant $k$ and several sets of non-negative integers:
...

**3**

votes

**1**answer

102 views

### What is the Complexity Class of the “Function Variant” of the Integer Factorization Problem?

I've been reading up a lot Prime Factorization and it's complexity, including a fair number of questions on this very site. However, I still feel there is a question still left unanswered.
So, ...

**0**

votes

**0**answers

32 views

### Complexity of optimizing a bi-objective function with integer constraints

I have two different objective functions, each of which can be solved optimally in polynomial time. Does this mean, I can optimize a linear combination of these objective functions in polynomial time ...

**2**

votes

**0**answers

89 views

### Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)

Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of ...