The algorithms tag has no wiki summary.

**4**

votes

**1**answer

108 views

### Algorithm to detect if an element of a (commutative) ring is in a subring?

For rings finitely-generated over a field, the theory of Groebner bases gives us quite an efficient algorithm for determining whether an element of the ring is in a given ideal of the ring.
Is there ...

**7**

votes

**2**answers

331 views

### Quickly finding optimal subset of pairs of numerator and denominator terms for special objective functions

Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the ...

**3**

votes

**0**answers

186 views

### Beating Kadane's Algorithm

I am seeking some reference on already existing work for the following problem.
Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...

**1**

vote

**1**answer

84 views

### computing $c_5$ in “Primality testing with Gaussian periods”

As far as I know, the April 2011 version of #143 on this page has not been improved upon.
On page 10 of that paper, the authors give an algorithm that uses a constant $\:c_{\hspace{.01 in}5}\:$.
...

**1**

vote

**1**answer

137 views

### What algorithms do you know for beltway reconstruction?

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of ...

**6**

votes

**3**answers

674 views

### Square Root Algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?

**2**

votes

**1**answer

161 views

### Algorithm to find if an element X can be represented with the sum of one number of each subset in $O(n^2)$?

Here is the problem:
I have 3 subsets ( called $S_1$, $S_2$ and $S_3$) that each have $N$ elements (arbitrary elements).
So I have one element $X$. I want to know if I can get $X$ making the sum of ...

**2**

votes

**1**answer

195 views

### Algorithm for representing a polynomial as a composition of lower degree polynomials

Let $q$ be a large prime and $e$ an integer such that $GCD(e,q-1)=1$. Let $p(x)$ be a polynomial of degree $e^n$ with coefficients in $\mathbb Z_q$ such that there exists a progression of polynomials ...

**5**

votes

**1**answer

462 views

### Difference Sets

Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...

**6**

votes

**2**answers

201 views

### Recovering a Weighted Graph from Shortest Path Distances

I am interested in the following problem (A) and its related formulation (B).
(A) Suppose that $G = (V,E,w)$ is an unknown weighted graph on the vertex set $V$ and that one has access to $d_G(v,v'), ...

**14**

votes

**5**answers

555 views

### Mathematics of privacy?

I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics?
Can we ...

**3**

votes

**1**answer

214 views

### Is the prime ideal principal which is in 256-th cyclotomic ring lying over 257?

As we known, the integer ring R of 256-th cyclotomic field is not a Principal Ideal Domain.
And rational prime 257 is split completely in R.
Suppose prime ideal P of R is an arbitrary ideal lying ...

**5**

votes

**1**answer

594 views

### Any reference to an algorithm for finding the largest empty circle on a sphere (with great-circle distance)?

Given a set $S$ of 2D points in the plane, there are known algorithms for finding the largest empty circle ($LEC$) of the set of points.
The $LEC$ problem is stated in this way: find a $LEC$ whose ...

**4**

votes

**1**answer

300 views

### Checking if a binary vector lies in the affine span of given binary vectors

Let $x_1,\ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors in ${\mathbb R}^D$, assumed affinely independent. Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ is in ...

**4**

votes

**1**answer

204 views

### convex polyhedron in the unit cube

Let $P$ be a given finite set of points within the $n$-dimensional unit cube. A finite set $Q$ of points within the $n$-dimensional unit cube covers $P$ if $\operatorname{conv}(Q) \supseteq P$ where ...

**8**

votes

**2**answers

217 views

### Ideal Membership without Certificate?

I have a homogeneous ideal $I=\langle f_1,\ldots,f_r\rangle$ of the polynomial ring $\mathbb C[X_1,\ldots,X_n]=:R$ where each of the $f_i$ is actually over $\mathbb Z$. My computations are usually ...

**0**

votes

**1**answer

117 views

### What is the Bahadur-Anderson Algorithm?

What is the Bahadur-Anderson Algorithm, and which book could one read to learn it?

**1**

vote

**2**answers

1k views

### Trilateration problem

When trying to develop an algorithm for a program, I got with the following problem:
Determine the approximate location of $O$, if you can take finite samples $P_n$ from known locations and always ...

**1**

vote

**3**answers

217 views

### Strategic vertex labeling

We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0(all vertices with ...

**5**

votes

**2**answers

782 views

### Solve for $A$ and $B$ in $AXB=Y$

Let $R = \mathbb{Z}[x_{1}, \dots, x_{r}]$.
Let $X$ be $n \times n$ matrix with entries in $R$.
Let $Y$ be $m \times m$ matrix with entries in $R$ formed from $\mathbb{Z}$-linear or $\mathbb{R}$-linear ...

**4**

votes

**0**answers

274 views

### Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids

Given two matroids $M$ and $M'$ over the same universe $E$, and some element $x \in E$, I am interested in the importance of $x$ for the intersection (the common independent sets) of $M$ and $M'$.
It ...

**26**

votes

**1**answer

428 views

### Decidability of equality of expressions built using 1,+,-,*,/,^

Consider expressions built using number $1$, arithmetical operators $+, -, *, /$ and exponentiation ^ (in case of multiple values, the principal value is assumed, the same way as it implemented in ...

**7**

votes

**0**answers

136 views

### How quickly can we test if a graph is distance-regular?

A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ ...

**3**

votes

**3**answers

722 views

### L-systems and Sierpinski Triangle

I was just shocked when I saw these consecutive outcomes of an L-system converging to the Sierpinski triangle (shown in the picture below).
I'm interested to know how could one arrange the rules of ...

**3**

votes

**1**answer

343 views

### Fastest Digit Extraction for Any Irrational Number

I believe the current lowest-memory algorithm for computing the $n^{th}$ binary digit of $\pi$ requires $O(log(n))$ bytes and $O(n^2 log(n))$ days (I pick Bellard over Bailey–Borwein–Plouffe for ...

**0**

votes

**1**answer

212 views

### Giving a general term of a recursive function, and upper bound for it

Let a constant $B \ge 1$, and let $l_1 = 0$, $b_1 = 0$ be the values of $l$ and $b$ (respectively) at time $t = 1$.
Let $l_{t+1} = l_t + 1$ if $b_i < B$, and $l_{t+1} = l_t$ otherwise
Let ...

**2**

votes

**3**answers

270 views

### existence of equivalence checking algorithm

Set D : Set of decision algorithms
X∈D if and only if
X is an Turing machine algorithm with finite length
takes one input i, binary number
X(i)=0 or X(i)=1 or X(i) runs ...

**1**

vote

**1**answer

108 views

### Separation of Anti-Hole Inequality

Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent.
An induced subgraph $H$ of $G$ is called an odd-antihole ...

**6**

votes

**2**answers

749 views

### Approximate number of primes below a given integer?

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...

**0**

votes

**2**answers

95 views

### Fitting algebraic expression to a number [algorithm]

I know that it may turn out useless, but this is precisely the reason why I'm asking.
Does any one know of an existing piece of code that would find me the best approximation to a given irrational ...

**3**

votes

**1**answer

145 views

### Using Fourier Transform to speed up calculation of forces following an inverse square law

Suppose I have $n$ electric point charges in, say, two dimensions. Is there any algorithm (and I have a hunch that it might be related to the Fourier transform) to compute the net forces that act on ...

**2**

votes

**1**answer

344 views

### At what point does Miller-Rabin become faster than trial division?

I've read in various places (and know) that Miller-Rabin is a much faster primality test than trial division for large $N$, but is much slower than trial division for small $N$.
My question is: how ...

**0**

votes

**0**answers

107 views

### max*min/(max+min) vs max*min/(max-min)

While working on a genetic algorithm, I needed to devise a fitness function for each chromosome. Each chromosome has 2 attributes: maximum accuracy and minimum accuracy.
The fitness should increase ...

**0**

votes

**0**answers

82 views

### Maximal Zero Sums Partition

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...

**0**

votes

**2**answers

61 views

### Maximize 2-tuple efficiently

Hello I am lookin for an algorithm that efficiently finds all Tuples ${(x,y)$$\varepsilon U|\forall (u,w) \epsilon U \rightarrow (x>=u \vee y>=w)$.
I could of course check all tuples against ...

**3**

votes

**0**answers

201 views

### (Co)limit computations for diagrams of Vector Spaces

Fix a field $K$ and consider a finite directed graph $\Gamma$ where multiple edges between a pair of vertices are allowed so long as the total number of edges is finite. Associate to each vertex $v$ a ...

**2**

votes

**1**answer

169 views

### Reducing the error of Algorithms by assigning variables formulas instead of values

Let me first give the intuition for my question: Suppose that you want to use a ruler to mark $n$ points in a line on a page, with 1 cm distance between neighbor points. There are two ways:
1- Mark ...

**1**

vote

**0**answers

120 views

### regular hyper graph construction

Is there any algorithm to generate 3-uniform k-regular hypergraph with n vertices?? Any help is appreciated. Thanks.

**1**

vote

**0**answers

134 views

### Optimize a convex hull on a 2D histogram so the selected points match a target shape

I have an image (can be 2D or 3D), and compute a 2D histogram of the image (for example, the pixel intensity and gradient along certain direction). There is a known target region $R^*$ in the image. I ...

**2**

votes

**1**answer

437 views

### Removing cycles from an undirected connected bipartite graph in a special manner

Consider an undirected connected bipartite graph (with cycles) $G = (V_1,V_2,E)$, where $V_1,V_2$ are the two node sets and $E$ is the set of edges connecting nodes in $V_1$ to those in $V_2$. We ...

**9**

votes

**2**answers

601 views

### When polynomial f(x^2) can be factored as g(x)·g(-x) ?

In relation to my question Expression for the sum of square roots of zeros of a polynomial
How to characterize polynomials $f(x)$ with rational coefficients such that $f(x^2)=g(x)\cdot g(-x)$ where ...

**2**

votes

**1**answer

174 views

### algorithmic almost equitable partitioning

Let $G$ be a graph -- possibly infinite, but I will be glad to learn a positive result even in the finite case. Then the trivial partition (i.e., one cell coinciding with the whole $G$) is clearly ...

**0**

votes

**0**answers

121 views

### Find polynomial in finite field

We have $A$, $B \in GF(q^k)$
We want to find polynomial $h \in GF(q)[x]$ where
$h(A) = B$
What is the lowest degree of $h$?
How to find $h$ with the lowest degree and what is complexity of this ...

**2**

votes

**0**answers

46 views

### Most efficient algorithm for computing norm of the residual for the least squares problem in the rank deficient case

I have a large $m\times n$ data matrix $A$, $m>n$, and response $m$-vector $b$. I need to calculate $E = ||Ax-b||_2$ as quickly as possible, where $x$ is the least squares solution. I don't need ...

**2**

votes

**5**answers

988 views

### Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

The question is close to the Sokoban game (thanks to Dima Pasechnik !), but a little different in details.
Consider a directed graph (multi-graph). Consider some set of marked chips (chip1, ...

**1**

vote

**1**answer

306 views

### Find root in finite field

What efficient algorithms exist for the solving $x^N = a$ in GF(q)?
What are their complexities?

**1**

vote

**1**answer

272 views

### calculate function from its divizor

There is elliptic curve $C (y^2 = x^3 + Ax + B)$ over $GF(q)$.
There is algebraic function f on C.
We have div(f).
How calculate f as rational function ( $f = (f_1(x) + yf_2(x)) / (g_1(x) + ...

**2**

votes

**0**answers

189 views

### Choosing a base where a given digit of a given number appears the most times

Is there an algorithm for choosing a base where a given digit of a given number appears the most times, that works better then trial and error? (see also this)

**0**

votes

**0**answers

158 views

### Condition and algorithm for Decomposition of formal power series

$$F(x)= \Sigma_0^{\infty} a_i x^i$$ is formal power series, $a_i\in N\bigcup 0$,N is the set of natural number,under what condition may it be decomposed into a system of equations terms of which are ...

**0**

votes

**2**answers

249 views

### Enlcosing a set of ellipses within one ellipse

Hello,
Is there an algorithm that takes in a set of ellipses and gives back and ellipse that encloses the set?