**0**

votes

**1**answer

66 views

### Intersection graphs

Does anybody know of a paper which proves that finding the maximum independent set in geometric intersection graphs is NP hard? Even general intersection graphs?

**1**

vote

**0**answers

142 views

### Explicitly showing that a free group is LERF [closed]

Let $F$ be a free group on a finite set $X$, and let $M$ be a finitely generated subgroup.
Marshall Hall's theorem states that $M$ is closed in the profinite topology on $F$. That is, $M$ is the ...

**8**

votes

**1**answer

906 views

### Algorithm to produce random number with a gamma distribution

I'd like to produce pseudo-random numbers with different distributions for a Monte Carlo simulation.
I've got the poisson distribution working nicely with an algorithm from Knuth. I'm having trouble ...

**0**

votes

**1**answer

97 views

### Using upper bound information in graph search

I am using A* (A-Star) to search a graph. A* algorithm takes advantage of the information $h(x)$, which is a lower bound of the distance between a vertex $x$ and the destination vertex.
In other words:...

**2**

votes

**1**answer

143 views

### DL-problem on abelian variety

Let $A$ be an abelian variety over $\mathbb{F_q}$ with dimension $n$. Let $q$ be a constant.
Is there polynomial algorithm of finding discrete logarithm in $A$?
UPD: really I don't undestend: can we ...

**3**

votes

**2**answers

817 views

### Find all faces in a graph from list of edges

I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 ...

**3**

votes

**2**answers

658 views

### Solving assignment problem using Hungarian method vs min cost max flow problem

The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method.
However, it can also be reduced to a min cost max flow ...

**5**

votes

**3**answers

177 views

### Minimize distance between centroids of subsets of points

In a n-dimensional space, I want to divide a set of m points into v (non-empty) subsets.
I want to minimize the sum of the pairwise Euclidean distances between the centroids of the resulting subsets.
...

**3**

votes

**1**answer

487 views

### Polygamous stable marriage/ assignment problem

I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...

**3**

votes

**1**answer

181 views

### Existence of subgraphs when given its degree sequence

For a given simple graph $G$ with $n$ vertices $v_1,v_2,\dots v_n$, the corresponding degree sequence is $d_1,d_2,\cdots,d_n$. My qusetion is:
How to determine whether there exist subgraphs in $G$ ...

**4**

votes

**0**answers

203 views

### Navigation in a graph

The problem
Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$.
Assumptions about the graph: You may ...

**4**

votes

**0**answers

286 views

### What is God's number for the WrapSlide puzzle?

WrapSlide is a slide-puzzle (reminding of Rubik's Cube) consisting of a 6x6 grid of coloured tiles which are separated into four quadrants of 3x3 tiles. When it is unmixed all the tiles in a quadrant ...

**14**

votes

**2**answers

346 views

### Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?

Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by $\pi.(\sigma_1,\...

**1**

vote

**0**answers

97 views

### Is there an efficient algorithm for sampling from the negative hypergeometric distribution? [closed]

I'm writing a small statistics library currently. One of the algorithms I'm implementing has two variants: one that samples the hypergeometric distribution and one that samples the negative ...

**2**

votes

**0**answers

100 views

### Containing a “fuzzy” ellipsoid within an ordinary ellipsoid

Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...

**1**

vote

**2**answers

159 views

### Combinatorial optimization problem involving infinite spin system

In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity.
...

**2**

votes

**1**answer

109 views

### enumeration of connected blocks in finite size square

Given a square of size n by m, how many ways could we choose sites, such that all the sites are connected?
By "connected" we mean "connected" by adjacent sites. We will illustrate by example, say, we ...

**2**

votes

**0**answers

163 views

### Complexity of an algorithm to solve linear diophantine equations

A friend of mine ask me yesterday a problem, however, the interesting part for me it is not his problem, but what I will ask here.
I want to know the optimal complexity of an algorithm (I mean the ...

**7**

votes

**1**answer

323 views

### Modular polynomials for elliptic curves point counting

The Schoof-Elkies-Atkin (SEA) algorithm (for counting points on elliptic curves over a finite field) performs computations over polynomials modulo some modular polynomials. Originally the "classical" ...

**0**

votes

**1**answer

76 views

### Paper on unit disk graphs

I was wondering if anybody knows of a 'link' to the paper by Marathe 1995 et al on analysis of the greedy algorithm for finding a Max independent set in Unit Disk Graphs?

**3**

votes

**1**answer

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

**6**

votes

**1**answer

237 views

### Constructing sums of squares identities

Recall that a sum of squares formula for $[r,s,n]$ over a field $F$ is an identity of the form
$$ ( x_{1}^{2} + \cdots + x_{r}^{2})( y_{1}^{2} + \cdots + y_{s}^{2})
= ( z_{1}^{2} + \cdots + z_{n}^{2})...

**10**

votes

**3**answers

662 views

### Square filling self avoiding walk

I want to create an algorithm that fills a square grid with a random Hamiltonian path starting at a particular point. See this example.
One approach is to try a free direction as a next step, and ...

**2**

votes

**4**answers

969 views

### Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...

**3**

votes

**1**answer

293 views

### Solution to generalized Sylvester equation

I am interested in solving generalized Sylvester equations (for $X$) of the form:
$$ \sum_{j=1}^k A_j X B_j^T = F, $$
where $A_j,B_j,X,F\in\mathbb{C}^{n\times n}$ and $k$, $n$ are integers. I will ...

**4**

votes

**2**answers

263 views

### What's the current state of one-rule semi-Thue system termination problem?

What's the current state of one-rule semi-Thue system termination problem? Search produces a lot of references, but it's hard to find out if decidability of this problem has been proven or not.

**3**

votes

**0**answers

128 views

### Recognizing Simplicial (Quasi)Fibrations

Let's say we are given two finite simplicial complexes, which I will suggestively call $E$ and $B$. We'd like an algorithm for the following decision problem:
Does there exist a simplicial map $p:...

**8**

votes

**2**answers

234 views

### Is this problem on weighted bipartite graph solvable in polynomial time or it is NP-Complete

I encounter this problem recently and I want to know whether it is NP-Complete or solvable in polynomial time:
Given a undirected weighted bipartite graph $G = (V, E)$ where $V$ can be partitioned ...

**-4**

votes

**1**answer

336 views

### An algorithm and symbolic manipulation for IF-THEN-ELSE [closed]

CONCLUSION (so far) Look at the parentheses theorem and at the comments below the question(s) :-) As for now, only Dan Peterson has truly addressed the issue.
Q1 Does there exists an ...

**4**

votes

**2**answers

450 views

### Are there any patterns in simple continued fraction expansions of algebraic real numbers?

As we know there are patterns in simple continued fraction expansion of quadratic algebraic numbers,are there any patterns in simple continued fraction expansions of other algebraic real numbers?...

**2**

votes

**0**answers

257 views

### Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate
polynomial which counts the number of colorings of $G$
with $x$ colors for natural $x$.
Graph is not $k$ colorable iff $P(G,k)=0$.
The ...

**3**

votes

**1**answer

179 views

### An efficient method to find the MLE of the combination of two point processes

I have a point process defined in two parts as follows. Consider first the main process which we call $A$ which is homogeneous Poisson process with conditional intensity
$$\lambda(t) = \mu$$
For ...

**3**

votes

**0**answers

149 views

### Algorithm to compute a common denominator of a finite set of rational numbers

Let $x_1,\dots,x_n \in \mathbb{Q} \cap (0,1)$ be fixed, but unknown, and assume that we know a number $K \in \mathbb{N}$ such that there is a number $N \in \{1,\dots,K\}$ such that $x_1 N,\dots,x_n N \...

**3**

votes

**0**answers

52 views

### Algorithm to construct metric space endomorphism with controlled square

Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be $K$-...

**4**

votes

**2**answers

331 views

### Finding the set of all $0$-$1$ vectors in an affine subspace

We are given a $0$-$1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0$-$1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z}...

**7**

votes

**0**answers

262 views

### Algorithms for computing the Resilience of Graphs

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...

**-4**

votes

**1**answer

184 views

### Bipartite graph [closed]

First of all, thank you for your time to reading my post.
I am a researcher but not a mathematician, i have some difficulties in solving a math problem, that why i am here to ask your help. I just ...

**4**

votes

**2**answers

369 views

### How to tell if two or more knots are linked

Given a number of knots, I would like to know if they are linked. I know that the linking number can tell if two knots are linked.
There is any method that completely solves this problem?

**5**

votes

**1**answer

211 views

### Estimate the rank of a vector

Consider {0,1}-vectors $v$ with $n$ elements. For each $i\in[n]$ we are given $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent. We can therefore associate a probability to each of the $...

**1**

vote

**0**answers

31 views

### Minimal rectangular confidence regions

For a given multivariate pdf $f$ (mainly the gaussian one) I'm looking to compute a minimal rectangular confidence region for a given level $\alpha$. For example, I would like to solve problems of the ...

**1**

vote

**0**answers

222 views

### Is finding a single vector in the null space as difficult as discovering the whole null space?

Let $A \in \mathbb R^{k\times n}$ be a matrix of rank $k$, where $k \ll n$. One can use Gaussian eliminations to discover $\operatorname{null}(A)$ at the cost of $O(nk^2)$. My question is:
Is the ...

**7**

votes

**1**answer

1k views

### Can the Legendre symbol be calculated in polynomial time?

Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre ...

**6**

votes

**1**answer

575 views

### Shortcut from discrete Fourier transform F{x} to zero-padded F{x:0…0}

Summary:
Given $X$ (the discrete Fourier transform of some unknown vector $x$ of length $N$), is there any shortcut to computing $X'$ (the Fourier transform of $x$ after padding it with $N$ zeros)?
...

**2**

votes

**2**answers

127 views

### Sampling from maximally skewed stable distribution

I am reading a paper which refers to a maximally skewed stable distribution $F(x;1,-1,\pi/2,0)$ . Is there an efficient way to sample from this distribution?
If $X$ has distribution $F(x;\alpha,\...

**1**

vote

**1**answer

61 views

### How to select a subset of points from a universal to minimize the distance from outside to inside?

Here is the detailed problem.
I have a set of N points in K-dimension space, called U, and I want select M points of them, called S. For each point p in U, we define the distance from p to S as
$$ d(...

**6**

votes

**1**answer

362 views

### Fast construction of straight line programs?

Given a group $G$ and a set of generators $A$, we can ask ourselves (and do ask ourselves all the time) to bound the diameter of $G$ with respect to $A$. The diameter, let us recall, is defined to be ...

**26**

votes

**2**answers

437 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

60 views

### Heuristic for choosing n-vectors from n-sets

my given problem is:
choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm ...

**4**

votes

**0**answers

141 views

### A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...

**10**

votes

**1**answer

349 views

### Explicit algorithm for composing permutations in factorial notation

Given two permutations p1 and p2 in factorial notation, is there an algorithm which computes their composition directly, i.e. without translating to a different notation (like Cauchy's 2-line notation,...