# Tagged Questions

**7**

votes

**3**answers

225 views

### Embedding planar graphs into the grid

I've seen the following lemma in a paper. The result is by Valiant.
A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**2**

votes

**0**answers

80 views

### Computing the density of a set of multiples

Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...

**8**

votes

**3**answers

468 views

### Is the Number of Carries in Integer-Addition Associative?

Is it true that the number of carries, when calculating the sum of a finite set of finite positive integers, is constant (i.e. independent of their permutation and the order in which the additions ...

**2**

votes

**0**answers

89 views

### Worst case performance of a simple averaging algorithm

Let $u_1,\ldots,u_n$ be a sequence of rationals with finite binary expansion.
Consider the following simple averaging algorithm:
while the sequence is not monotone increasing, pick $i$ with ...

**7**

votes

**1**answer

139 views

### Shortest vector problem over polynomials

In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult.
Is there a polynomial analog of this problem ...

**0**

votes

**0**answers

45 views

### Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include:
All vectors in $S$
All vectors in $T$
All vectors that can be ...

**7**

votes

**2**answers

443 views

### What is wrong with this deterministic algorithm efficiently generating large primes?

According to PolyMath
(Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in ...

**1**

vote

**0**answers

221 views

### Reduction to some physical interpretation of this formula

Problem Given N 3-dimensional points which are {$p_1,p_2,..,p_n$} where $p_i = (x_i,y_i,z_i) $ . I have to find the value of the formula
$$ \sum \limits_{i=0}^n \sum \limits_{j=i+1}^n \frac{ \mid ...

**2**

votes

**0**answers

36 views

### Algorithm to get lower peak of bimodal histogram [closed]

I have a set of data, when tabulated in histogram, it looks like bimodal histogram.
With naked eyes, we can see the value for lower peak is about -1.35, however, what algorithm I can use to ...

**3**

votes

**3**answers

103 views

### Algorithm to determine isomorphism of 2 maximal planar graphs

I read on wikipedia that there are efficient algorithms to answer the question whether 2 (maximal) planar graphs F and G are isomorphic. However, after some (IMHO) substantial searching I don't seem ...

**2**

votes

**1**answer

103 views

### Mestre-type algorithm for higher-genus curves?

Is there an analogous algorithm for genus $g>2$ curves that, given a complete set of invariants, outputs a curve with those invariants?
(I'm interested in particular in $g=3$.)
Any references ...

**10**

votes

**3**answers

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

**5**

votes

**0**answers

70 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

213 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

111 views

### 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

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

**2**

votes

**1**answer

278 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

101 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

110 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

797 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

85 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

134 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

389 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

274 views

### Partitioning graph for Graph Isomorphism [closed]

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

**2**

votes

**1**answer

59 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

73 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

104 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

199 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

1k 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 ...

**10**

votes

**1**answer

643 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

130 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

44 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

182 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

202 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

169 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

166 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

137 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

76 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

164 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

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

**1**

vote

**1**answer

132 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

152 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

73 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

360 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

381 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

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

**6**

votes

**1**answer

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

**10**

votes

**4**answers

506 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

174 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

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