The algorithms tag has no wiki summary.

**1**

vote

**0**answers

88 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

240 views

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

Hello!
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 ...

**6**

votes

**1**answer

381 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

107 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

104 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

158 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

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

**8**

votes

**1**answer

361 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

844 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

244 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

415 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

281 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

318 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

215 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

152 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

**3**answers

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

**0**

votes

**2**answers

183 views

### Maximizing number of factors contributing in the sum of sorted array bounded by a value

I have a sorted array of integers of size n. These values are not unique. What I need to do is : Given a B, I need to find an i<A[n] such that the sum of ...

**6**

votes

**1**answer

241 views

### Is it possible to decide in polynomial time if a poset is a subposet of another which is given ?

I am reading some theory on partial orders and I wonder something which perhaps has a simple answer : Given two partial orders $G_1,G_2$ (by their hasse diagrams), is it possible to know in ...

**3**

votes

**1**answer

110 views

### Median-of-k elements

Hello,
Assume I am given a sequence of $n$ elements (by sequence I mean an ordered set). I want to randomly pick $k$ elements out of these $n$ elements, where $k$ is an odd number $\leq n$.
Then out ...

**2**

votes

**1**answer

233 views

### Complexity of establishing finite groups (non)-isomorphism ?

Question Given two finite groups G and H of the same order N what are the algorithms and what is their complexity (in terms of N) to check is G isomorphic to H or not ? Is there polynomial in N ...

**8**

votes

**3**answers

1k views

### Algorithm to check is representation irreducible ? Algorithm to decompose the reducible one ?

Question 1 Given a representation of a finite group, what algorithm can be used to check is it irreducible or not ?
(Main case - complex numbers, comments on other cases are also welcome. "Given" ...

**2**

votes

**2**answers

256 views

### Lattice reduction on an orthonormal lattice?

Suppose you are given an inner product on a vector space and given a set of linearly independent vectors, and that you have been promised that the lattice they span has an orthonormal basis. Can you ...

**0**

votes

**1**answer

93 views

### Provided a list of sets, $L$, computing an array where each entry $q_i \in Q$ is the family of sets in $L$ that have intersection $k$ with $l_i \in L$

I have a set of $(l_1, ..., l_N) \in L$ smaller sets, each with $(r_1, ..., r_M) \in R$ integer elements. I would like create an ordered array of $(q_1, ..., q_N) \in Q$ sets s.t.:
(1) Each $q_i \in ...

**9**

votes

**1**answer

295 views

### Algorithm to test for discrete or quasi-Fuchsian subgroups of PSL(2,C)

Let $\Gamma = \pi_1(S)$ denote the fundamental group of a compact surface $S$ of genus $g>1$.
Given a representation $\rho : \Gamma \to \mathrm{PSL}(2,\mathbb{C})$, specified by matrix ...

**1**

vote

**1**answer

260 views

### Computing the ratio of two large integers modulo m

$P(n)$ and $D(n)$ are two large integers.
Suppose $R(n) = \frac{P(n)}{D(n)}$ is an integer.
I want to compute $R(n)\bmod m$.
$P(n)$ and $D(n)$ are too large to be computed but $P(n)\bmod m$ and ...

**0**

votes

**1**answer

538 views

### Finding the lowest cost set of disjoint paths using all nodes in a directed graph?

I have a directed graph with edges connecting nodes representing costs.
I wish to find the set of paths which
-go from node 'start' to node 'end'
-are node-disjoint (except for the start and end ...

**1**

vote

**5**answers

1k views

### The Inverse of the Euler Totient Function

How can we calculate the cardinality of the inverse of Totient function of any positive integer n ?
I tried going through this paper, but I couldn't understand the procedure.
Thanks

**1**

vote

**0**answers

123 views

### Efficient algorithm for computing the integral closure of a computable domain

what is known? even talking about efficiency relatively to the complexity of the computation of the domain itself?

**6**

votes

**2**answers

494 views

### Algorithm for reducing words in a Coxeter group

Let $W$ be a Coxeter group with set of simple reflections $S$. Suppose that I have chosen a preferred reduced decomposition for every element of $W$. Given an arbitrary word in the alphabet $S$, is ...

**1**

vote

**0**answers

90 views

### Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?

Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?
Equally interesting would be to learn about such problems with a ...

**-5**

votes

**2**answers

685 views

### why do we need algorithms, and why is non-convex optimization difficult? [closed]

A simple question, but (I'm quite sure) not a superficial one: is the basic distinction between algorithms and much of the rest of math that algorithms try to tackle problems for which we lack global ...

**9**

votes

**2**answers

679 views

### How to compute the Picard rank of a K3 surface?

I'm curious about the following question:
Given a K3 surface, how does one proceed to compute its rank?
Of course the answer may depend on the form of the input, i.e. how the K3 is "given". So
...

**15**

votes

**1**answer

2k views

### Conceptual explanation of Strassen's trick for matrix multiplication

Algorithms for fast multiplication of polynomials and integers have well-known conceptual explanations. A good survey paper is Daniel J. Bernstein's Fast Multidigit Multiplication for Mathematicians.
...

**2**

votes

**0**answers

178 views

### A natural problem on “cartesian union” of set families (hypergraphs). Does anybody know NP-complete problems related to the notion of cartesian product?

I'm curious whether the problem below is NP-complete.
I provide two simple definitions and one example at first.
Definition 1.
Let $\langle {\cal{S}}_i\rangle\substack{i\in I}$ and $\langle ...

**6**

votes

**1**answer

2k views

### Origin of square-and-multiply algorithm

I'm teaching an introductory course in cryptography and explained the square-and-multiply algorithm to the class.
http://en.wikipedia.org/wiki/Square-and-multiply_algorithm
Someone asked who ...

**0**

votes

**1**answer

252 views

### Counterexamples for this algorithm for recognizing lexicographic product of graphs?

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT
(since 2SAT is polynomial, the algorithm is polynomial).
Can't prove completeness of the algorithm and since it is ...

**10**

votes

**3**answers

470 views

### Algorithms in Invariant Theory

Let $V$ be a polynomial representation of the general linear group $\Gamma:=\DeclareMathOperator{\Gl}{Gl}\Gl_n(\newcommand{\C}{\mathbb C}\C)$.
In chapter 4.6 of his book "Algorithms in Invariant ...

**2**

votes

**3**answers

2k views

### Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...

**5**

votes

**0**answers

350 views

### Determine if a matrix is unimodular

Is deciding if an integer square matrix has determinant $\pm 1$ faster that calculating the determinant of the matrix?

**5**

votes

**0**answers

200 views

### Rigid-body matching algorithm and clustering algorithm with groups of lines in 3D

I've been struggling with this problem for weeks, and couldn't find an appropriate algorithm to solve it. Could you guys please give me some advices or suggestions in addressing this question. Or if ...

**1**

vote

**0**answers

138 views

### Randomized alternative to Buchberger's algorithm

Richard Lipton's blog describes a A New Way To Solve Linear Equations by Prasad Raghavendra.
Can the ideas in this algorithm be generalized to systems of polynomial equations to provide a randomized ...

**0**

votes

**1**answer

237 views

### Algorithm for vector space

I have $n$ vectors $e_1 \in (\mathbb Z/2 \mathbb Z)^m,\dots,e_n \in (\mathbb Z/2 \mathbb Z)^m $
and a vector $ v \in (\mathbb Z/2 \mathbb Z)^m $
I need to find the better algorithm which answers ...

**3**

votes

**2**answers

1k views

### Generation of All Path in a Directed Acyclic Graph

I am working on a very large dataset of a single DAG whose vertices have a low branching factor. I need to generate all possible (simple) paths starting from the source and write them to a file.
My ...

**1**

vote

**1**answer

193 views

### On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that
$$
A_0 = A_1 = 0;\quad A_n = ...

**2**

votes

**1**answer

133 views

### How to deconstruct a sum of intersecting upsets

A set system $\mathcal{U}\subset P([n])$ is
an upset if $B\supset A \in \mathcal{U}$ implies $B\in \mathcal{U}$,
intersecting if $A,B\in\mathcal{U}$ implies $A\cap B \ne \emptyset$.
Note that a ...

**3**

votes

**2**answers

383 views

### pseudo-random algorithm allowing O(1) computation of Nth element

It is obvious that using seed value one can easily compute next value of some (deterministic) pseudo-random algorithm - so Nth element can be computed in O(N).
But is there such PRNG that allow to ...

**0**

votes

**1**answer

237 views

### Designing a Hash function that results in minimum size and no collisions

Dear all,
I have the following problem: Consider an array of $N$ vectors $v_{i} \ i=1...N$ of size $L$ bits, where each bit is 1/0 with equal probability. I want to find a hash function $H()$ that ...

**12**

votes

**2**answers

505 views

### Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg n.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns ...

**10**

votes

**1**answer

688 views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time.
...

**15**

votes

**4**answers

783 views

### Proving univariate polynomials (defined by sums, binomial coeffs, etc.) are nonnegative: is it 'routine'?

My colleagues and I are working on a project related to an old paper of C. Borell and we have boiled it down to the following problem:
Show, for all integers $1 \leq i \leq k$, that the univariate ...