The algorithms tag has no wiki summary.

**8**

votes

**2**answers

230 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

126 views

### What is the Bahadur-Anderson Algorithm?

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

**1**

vote

**3**answers

223 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

808 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

290 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

433 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

141 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

843 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

346 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

229 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

277 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

116 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

784 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

97 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

150 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

364 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

120 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

87 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

63 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

219 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

183 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

128 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

147 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

525 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

604 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

192 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

123 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

48 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

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

347 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

274 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

163 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

270 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?

**1**

vote

**0**answers

95 views

### Toroidality testing

Is there a standard test for the recognition of toroidal graphs?
I have been using the Boyer-Myrvold algorithm (which has a MATLAB implementation) and would like to know if there is something ...

**4**

votes

**1**answer

285 views

### Generating non-isomorphic graphs by adding edges to a given graph

This question is in a way related to the one I posted on math.se. Since the question there did not produce any final answer I am trying my luck here!
I am given a fairly large graph $G$ and subsets ...

**6**

votes

**1**answer

400 views

### Is equality of terms for “real” numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?

If yes, how? Also, I know you can't do it for arbitrary statements about real numbers, but that's not what I'm asking, and by "real" numbers, I mean the numbers constructible from 1, -, /, and the ...

**0**

votes

**0**answers

129 views

### Examples of applications that use the Schnorr digital signature?

Hi there. It may not be the best place to ask this question, but here goes:
I have made a study on digital signatures, especially on the Schnorr digital signature, and I was just wandering if there ...

**3**

votes

**1**answer

106 views

### Search for common substructures in list of graphs

I have had the following problem on several occasions and I was wondering whether there is a general technique to solve this problem.
Given a list of graphs with property $P$. Is there a general ...

**0**

votes

**1**answer

159 views

### An Algorithm to Determine a probable profit

I 'm searching for an algorithm (and except the naive brute force solution had no luck) that efficiently ($O(n^2)$preferably) does the following:
Supposing I’m playing a game and in this game I’ll ...

**2**

votes

**1**answer

297 views

### Finding a subspace disjoint from a union of subspaces

Let $k$ be a finite field (I care about $\mathbb F_p$, especially $\mathbb F_2$) and let $V_1,...,V_N\subset k^n$ be subspaces.
I want to find a subspace $S\subset k^n$ such that $S\cap V_i=0$ for ...

**12**

votes

**1**answer

512 views

### Constructive proof of “Projective implies proper”

For every ring $A$, the structural morphism of schemes $\pi_A : {\bf P}^n_{A} \to {\rm Spec}{A}$ is a closed map. The usual proof of this fact is not constructive : given equations of a closed subset ...

**16**

votes

**3**answers

850 views

### Easy functions ?

Let $f$ be an analytic function, and suppose that we want to compute
$f(x)$. The input consists of the digits of $x$ and the output of
a rational number approximating $f(x)$. A function $f$ is called ...

**6**

votes

**1**answer

275 views

### How do you compute the primes of bad reduction?

Suppose that I am given a subscheme $Y$ of $\mathbf{P}^n_{\mathbf{Z}}$, flat over $\operatorname{Spec}\mathbf{Z}$ and with smooth generic fiber $Y_{\mathbf{Q}}$, defined by the vanishing of some ...

**4**

votes

**1**answer

450 views

### Exact arithmetic for real algebraic numbers

There was a reply to a question (that I can't find) which mentioned SARAG (Some Algorithms
in Real Algebraic Geometry) see http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html. This ...

**0**

votes

**2**answers

331 views

### Creating composite rank [closed]

Problem: Suppose that $K$ different students are ranked based on $N$ different parameters (such as Physics marks, English marks, Biology marks, IQ etc). The rank under each parameter can be repetitive ...

**7**

votes

**1**answer

330 views

### Experimental mathematics: how are floating point equations discovered/converted to exact equations?

the 2005 AMS article/survey on experimental mathematics[1] by Bailey/Borwein mentions many remarkable successes in the field including new formulas for $\pi$ that were discovered via the PSLQ ...

**2**

votes

**1**answer

234 views

### An optimization problem, non complete bipartite graph and hungarian algorithm

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like the rows in reference dataset with the ...

**4**

votes

**2**answers

154 views

### Computing Slim Extensions representing Ext

Hey Everyone
Let $A$ be an algebra over a field (group rings $k[G]$ for group cohomology, the Steenrod Algebra). We want to compute, say, $Ext_A(k,k)$, so let $F_*\to k$ be an $A$-free resolution. ...

**0**

votes

**1**answer

721 views

### Largest subarray with average $\geq$ k

I try to solve this problem. The algorithm I developped has a complexity of $O(n^2)$. When dealing with large data the program is brought to its knees. Do you have any idea that might be faster than a ...