# Tagged Questions

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

796 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

650 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

477 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

180 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

158 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

158 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

319 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

236 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

653 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

956 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

290 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

260 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

127 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

232 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

330 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

448 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

256 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

51 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

261 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

367 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

219 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

568 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

126 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

140 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

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

**2**

votes

**1**answer

139 views

### Galois Connections: algorithmic generation

Given two finite posets $P,Q$, is it known any algorithm to count and/or generate every Galois Connection between $P$ and $Q$ ?
I'm looking for references about this problem.

**3**

votes

**2**answers

145 views

### All Integers from the Smallest Digit Stream with a Window Filter

Let's represent integers with D digits where each digit has B values
(i.e., the base is B and we effectively work only with integers between
1 and B^D). Is it possible to choose a single cyclic/...

**8**

votes

**3**answers

542 views

### Changing combination lock [closed]

Suppose you have a combination lock (n digits, m symbols) that is unlocked by one specific n-digit key sequence. However, trying a wrong key changes it according to an fixed but unknown function: new ...

**37**

votes

**1**answer

2k views

### improving known bounds for Pierce expansions; cash prize

Here's a problem that I thought of back in 1978 or so, and only a little progress has been made on it since then. I still think about it from time to time, but probably not that many people have ...