The algorithms tag has no wiki summary.

**2**

votes

**1**answer

253 views

### (efficient) method to test $\{n\alpha\}\not\in [A, B]\subset [0,1]$

Suppose $\alpha$ is a fixed given irrational number with $\alpha\in [A, B]\subset [0,1]$, are there any (efficient) methods to compute the least integer $n$ such that the decimal part of $n\alpha$ ...

**18**

votes

**0**answers

313 views

### Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them.
Define the set $\mathcal{E}$ of ...

**3**

votes

**1**answer

117 views

### Is there an algorithm to compute group presentations of or find generators for the centralizer of a matrix in $GL(n, \mathbb{Z})$?

Let $M \in H \leq GL(n, \mathbb{Z})$. Is there an algorithm that computes either matrix generators or even a group presentation for $C_H(M)$ given generators or a presentation of $H$? Also is ...

**5**

votes

**5**answers

254 views

### Efficient Hamiltonian cycle algorithms for graph classes

Generally speaking finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $G$ then we can reduce the finding of a Hamiltonian cycle in $G$ to a Eurler your of $H$ ...

**3**

votes

**0**answers

144 views

### Comparing different Euclidean algorithms on a Euclidean domain

I have posted this question at stackexchange (502413), without responses until now.
In the papers by T. Motzkin: The Euclidean Algorithm, Bull. AMS 55, 1949, pp. 1142--1146 and P. Samuel: About ...

**10**

votes

**7**answers

2k views

### Is there an algorithm to solve quadratic Diophantine equations?

I was asked two questions related to Diophantine equations.
Can one find all integer triplets $(x,y,z)$ satisfying $x^2 + x = y^2 + y + z^2 + z$? I mean some kind of parametrization which gives all ...

**1**

vote

**1**answer

160 views

### Finding automorphism groups of simplicial complexes

Question:
Given a finite simplicial complex $K$, what general techniques allow one to efficiently compute (a presentation of) the group $\text{Aut}(K)$ of $K$'s automorphisms?
Since this is ...

**9**

votes

**1**answer

257 views

### Can Tarski decide constructibility in elementary geometry?

Can the decision routine for Tarski's Elementary geometry be extended to decide when an existence claim in that theory can be instantiated by a compass and straightedge construction?
The answer does ...

**21**

votes

**3**answers

1k views

### Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...

**8**

votes

**0**answers

124 views

### Naive Reidemeister-Schreier for $\mathbb Z$ quotients

I have a question about a "standard" variant of the Reidemeister-Schreier algorithm used by topologists when manipulating manifolds they either know or suspect are fibre-bundles over $S^1$.
Say you ...

**1**

vote

**0**answers

66 views

### Testing functional equivalence

We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...

**2**

votes

**1**answer

118 views

### Complexity of numerically solving systems over the reals

Basically I am interested in
What is the complexity of numerically solving systems over $\mathbb{R}$?
By solving I mean finding at least one numeric solution with given
precision.
Probably the ...

**1**

vote

**1**answer

202 views

### Algorithm to efficiently sum N boolean numbers. [closed]

I am looking for a fast algorithm to do the following task: Given $N$ numbers $a_i, i=1,..., N$, where $a_i$ can be equal to $0$ or $1$, compute the number $s \equiv \sum_{i=1}^N a_i$ in base 2. ...

**7**

votes

**1**answer

212 views

### Main problems on lattice-basis reduction algorithms (such as LLL)?

What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions:
(a) their solution would likely be of some ...

**2**

votes

**1**answer

179 views

### RefReq: Algorithms for standard operations in Algebraic Number theory

Given an algebraic number field $F$ (I actually don't have an idea how to implement this data already, except for splitting fields of polynomials, but there is something in SAGE) is there free code ...

**1**

vote

**1**answer

113 views

### Generating k-partite graphs

Does there exist an efficient algorithm for generating all non-isomorphic k-partite graphs up to a certain order $n$? I've read through the nauty tutorial, but it doesn't look like anything beyond ...

**7**

votes

**3**answers

633 views

### smooth manifolds as real algebraic set (continued)

There are several ways of producing manifolds,say:
1.orbits space of group action
2.connected sum of manifolds
3.underlying topological space of nonsingular algebraic set
....
here,i am ...

**2**

votes

**2**answers

195 views

### Geodesics in Graphs:Shortest Paths vs Going as Straight Ahead as Possible

According to Wikipedia http://en.wikipedia.org/wiki/Geodesic, a geodesic " is a generalization of the notion of a "straight line" to "curved spaces " and further " In the presence of an affine ...

**1**

vote

**0**answers

83 views

### Row subset selection of matrix to optimize condition number

Given a matrix $\mathbf{A} \in \mathbb{C}^{N\times M}$ with $N \gg M$. This matrix results from a linear equation system and has a certain structure (however, I do not think that details provide any ...

**1**

vote

**3**answers

156 views

### Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists.
Can someone please tell me how do I ...

**1**

vote

**1**answer

111 views

### Do there exist a way to solve inhomogeneous matrix equations Ax = b for only selected rows?

The inhomogeneous matrix equation $\mathbf{A} x = b$ can be solve in many ways, but in this particular case, I am looking for a solution to this problem on a set of constraints.
The matrix $A$ is ...

**2**

votes

**1**answer

237 views

### Finding integer points inside of a parallelogram

Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...

**4**

votes

**2**answers

152 views

### Estimate size of graph by taking random walks

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:
...

**4**

votes

**0**answers

152 views

### Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...

**3**

votes

**2**answers

300 views

### Hyperrectangle partition of set of overlapping hyperrectangles

I have a set of $n$, $d$-dimensional hyperrectangles which may be overlapping in arbitrary ways. I would like to partition the area covered by this set into a set of non-overlapping hyperrectangles. ...

**2**

votes

**1**answer

160 views

### Finding the vertices of a convex polyhedron from a set of planes

I'm new to computational geometry and advanced mathematics in general here so bear with me. I've spent a decent amount of time attempting to figure out this problem and I just can't find a solution.
...

**4**

votes

**2**answers

212 views

### Reference Request: Representing Positive Integers as Differences with Minimal Hamming Weight

Background of my reference request is an observation that I made, while I was still in school: there are two ways to calculate $x*999$: either do it directly, by applying the multiplication algorithm ...

**2**

votes

**0**answers

25 views

### In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?

I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...

**27**

votes

**3**answers

1k views

### Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...

**2**

votes

**3**answers

135 views

### Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs

From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...

**3**

votes

**1**answer

159 views

### Practical error-estimates for (adaptive) Newton-Cotes Quadrature

I am looking for practical error estimates for Newton-Cotes Quadrature rules.
Most books on numerical methods I have found mainly deal with theoretical error bounds/estimates for the respective ...

**5**

votes

**2**answers

238 views

### Covering convex polygons with inscribed disks

The following problem came up when discussing mapping software (e.g., Google maps) with computer scientists. By $B(c,r)$ I mean the planar disk (open or closed, it doesn't matter) of radius $r$ around ...

**3**

votes

**0**answers

102 views

### On understanding Discrete-Valued Stochastic Processes( time series, panel data )

It seems to me that a significant proportion of work in probability theory, statistics and machine learning are on understanding continuous-valued, relatively weakly dependent, or linear dependent ...

**4**

votes

**1**answer

102 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

299 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

158 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

74 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

128 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

604 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

151 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

177 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

436 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

180 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'), ...

**11**

votes

**4**answers

424 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

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

**4**

votes

**1**answer

375 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

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

**0**

votes

**0**answers

41 views

### Statistics applied in A/B Testing and calculating ideal test duration for statistical significance

I'm trying to get my head around the maths used here:
http://visualwebsiteoptimizer.com/ab-split-test-duration/
Can someone point me in the right direction in terms of what algorithms/mathematics ...

**8**

votes

**2**answers

198 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

98 views

### What is the Bahadur-Anderson Algorithm?

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