The algorithms tag has no wiki summary.

**2**

votes

**1**answer

130 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

354 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

193 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

437 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

583 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

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

**8**

votes

**0**answers

514 views

### Recent Fast Multiplication Algorithms for Large Integers

The STOC 2008 paper "Fast Integer Multiplication using Modular Arithmetic" by De et al
http://arxiv.org/abs/0801.1416 shows how to use $p$-adic numbers instead of $\mathbb C$ used in Furer's ...

**2**

votes

**2**answers

203 views

### How can I get all the good items using quantum search algorithm?

One can get a superposition of all good item using quantum search algorithm in $O$($\sqrt{N}$ ) time, but how one can get all the good items using quantum search algorithm?
I found that all the good ...

**1**

vote

**1**answer

184 views

### Special case of testing integer polynomials for irreducibility

How much easier is testing polynomials of the form x^n + ax + b for irreducibility (in Z[x]) than testing polynomials in general? I am especially interested in the case where n is prime, which may be ...

**5**

votes

**1**answer

627 views

### How much does a quantum oracle to find a needle in a haystack really cost?

Among the basic algorithms of quantum computations Lov Grover's result on quantum search stands out, both in regards to its intrinsic interest, and for its undisputable elegance.
Grover's algorithm ...

**4**

votes

**0**answers

155 views

### Differential operators that preserve real-rootedness

Is there some description of polynomial differential operators, $\mathcal{D}=\sum f_i(x) D_x^i$ such that, if $h$ is a polynomial all of whose roots are in $[0,1]$, then so are all the roots of ...

**3**

votes

**2**answers

164 views

### Determination of rationality and computing a rational parametrization

Suppose I have a hypersurface in $\mathbb{C}P^n$ given by some $f(z_1, \dots, z_{n+1}) = 0.$ Is there an algorithm which returns a rational parametrization if there is one, and "not rational" ...

**1**

vote

**2**answers

139 views

### Approximate version of a balanced incomplete block diagram

Let $S$ be a set of some size $n$. I'm interested in knowing about combinatorial designs that are approximately balanced incomplete block designs, that I want a collection of subsets $C$ of $S$ such ...

**17**

votes

**1**answer

2k views

### How fast can we *really* multiply matrices?

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.8})$ for the multiplication of two $n \times n$ matrices. However, the constant is so large that ...

**3**

votes

**3**answers

422 views

### Are there any neat algorithm to factor a homogenous polynomial, given we know this polynomial factors into linear forms?

Are there any neat algorithm to factor a multivariable (more than 2 variables) homogenous polynomial, given we know this polynomial factors into linear forms?

**1**

vote

**0**answers

76 views

### Deciding / Approximating Parity of Small Depth Decision Trees

Let C be a circuit such that:
C: $\{0,1\}^n$ to $\{0,1\}$
the top most gate is a parity gate
all the inputs to the parity gate are small depth decision trees
there is a total of $2^{ log^k n}$ ...

**5**

votes

**0**answers

243 views

### Testing isomorphism of finitely generated algebras

Let $A=\mathbf{Q}[x_1,\ldots,x_n]$ be the polynomial ring in $n$ variables over the rational numbers. Let $B=\mathbf{Q}[f_1,\ldots,f_r]$ and
$C=\mathbf{Q}[g_1,\ldots,g_s]$ be two finitely generated ...

**1**

vote

**2**answers

174 views

### Simultaneous Smith Normalization of a Composable Matrix Sequence

Let $\mathsf{R}$ be a PID and consider a collection of free, finitely generated $\mathsf{R}$-modules $V_1,\ldots,V_n$ along with module maps $m_j:V_j \to V_{j+1}$. That is, we have the following ...

**2**

votes

**1**answer

2k views

### FFT and Butterfly Diagram

Wikipedia presents butterfly as "a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into ...

**2**

votes

**0**answers

125 views

### Additional Constraint Baum Welch for HMMs

I'm trying to derive a special form of the Baum Welch algorithm where there is an additional constraint that the sum of emission probabilities over all states sums to one for each output symbol. ...

**1**

vote

**3**answers

1k views

### How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}
Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.
Example:
Input ...

**0**

votes

**0**answers

180 views

### Maximum subset of set of Integers with minimum distance

Hi, i have a set of integers for example: {0,1,3,100,102} and i am looking for a maximum subset in which all elements have a minimum distance to all elements (or the "next" doesnt matter i guess) for ...

**2**

votes

**3**answers

275 views

### Generating a set of integer passwords that can be securely authenticated

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it.
My question is as follows.
Given a positive integer $k$, determine a set of properties ...

**10**

votes

**1**answer

240 views

### Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...

**2**

votes

**1**answer

104 views

### A Parameter related to fractional chromatic number and Kneser Graphs

Let $t \gt 0$ be an integer and $G$ is a simple graph with $\chi_f(G) = t$. Then $t$= inf $\{ \frac{n}{k}| G \rightarrow KG(n,k)\}$ where $KG(n,k)$ is the Kneser graph.
Does there exist a $k$ such ...

**1**

vote

**1**answer

226 views

### Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph

I've posted a question on Stack Overflow regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem.
One of the respondents cited Professor David Speyer's Math ...

**1**

vote

**2**answers

762 views

### The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function

I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function.
Preliminary: Mertens function and the ...

**3**

votes

**1**answer

416 views

### Does a product of matrices have eigenvalue 1

Start by fixing invertible matrics $A_1, \ldots, A_m \in \mathbb{Z}^{n \times n}$.
For a sequence $i_1, \ldots, i_k$ we construct $A = A_{i_1} \cdots A_{i_k}$. We would like to know "Is 1 an ...

**2**

votes

**1**answer

324 views

### An algorithm for checking if a nonlinear function f is always positive

Is there an algorithm to check if a given (possibly nonlinear) function f is always positive?
The idea that I currently have is to find the roots of the function (using newton-raphson algorithm or ...

**3**

votes

**3**answers

415 views

### How to find the minimum number of hyperplanes to define a convex hull?

I have the following problem:
I have a convex hull $\Omega$ defined by a set of n-dimensional hyperplanes $S = [(n_1,d_1), (n_2,d_2),...,(n_k,d_k)]$ such that a point $p \in \Omega$ if $n_i^T p \geq ...

**1**

vote

**0**answers

66 views

### An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label).
We need to select one point of every color, so as to minimize the cost of a planar MST of selected points ...

**4**

votes

**1**answer

304 views

### Polyline Averaging

I'm trying to find a method that can take a collection of polylines, each described by a list of connected points on a plane, and find an "average" path through them. The input lines do not loop.
...

**4**

votes

**2**answers

182 views

### Extension of conjugacy problem

Let $F = \langle a,b \rangle$ be a non-abelian free group.
Question: Is there an algorithm that takes as input $x,y,z \in F$ and answers the question whether $x$ is a product of conjugates of $y$ ...

**4**

votes

**0**answers

280 views

### Matching a binary matrix

Given a MxN 0-1 matrix D, with the property that
both M and N are odd numbers
its row sums and column sums in the $\mathbb{Z}_2$ field are all equal to the same number (0 or 1).
How do we find M ...

**9**

votes

**3**answers

921 views

### Mertens' function in time $O(\sqrt x)$

This MathOverflow question seems to indicate that the state of the art in computing
$$
M(x)=\sum_{n\le x}\mu(n)
$$
takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. ...

**6**

votes

**0**answers

470 views

### Is Logical Min-Cut Problem, NP-Complete?

Logical Min Cut (LMC) Problem: Suppose that G = (V, E) is an unweighted digraph, s,t are two vertices of V, and t is reachable from s. LMC Problem states that how we can make t unreachable from s by ...

**2**

votes

**1**answer

454 views

### #P version of SUBSET SUM

The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...

**2**

votes

**1**answer

560 views

### practical algorithm for constrained triangulation in two dimensions?

I'm looking for an algorithm that is easy to implement in practice (resulting in small amount of code), preferably incremental. As far as I know, the biggest problem with incremental constrained ...

**2**

votes

**1**answer

104 views

### Do you know a shortes path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?

Title says it all. I have a weighted Graph G={V,E,ETW} where V is the node set, E the edge set and ETW is a set of edge time windows. A edge time window is a 3-Tuple (edge, starttime, endtime) with ...

**2**

votes

**1**answer

165 views

### Covering set problem

All the references I can find to Covering Set appear to be algorithmic. Is there are any reference for the simple existential question ---
Suppose we have $k$ sets $X_1,…,X_k$ which are subsets of a ...

**1**

vote

**0**answers

162 views

### Finding the smallest subset whose intersection is empty

Given a (finite) set $S$ of (finite) sets such that $\bigcap S = \emptyset$, how can I find all the smallest subsets $S' \subseteq S$ such that $\bigcap S' = \emptyset$?
Of course, I could just ...

**4**

votes

**1**answer

193 views

### Consistency of systems of inequalities involving only differences

I have a very large number (670 billion) of systems of inequalities of the form:
$C_1 - C_2 < C_4 - C_3 \wedge C_3 - C_2 < C_5 - C_3 \wedge ...$
where the $C_i > 0$. Ie. each system of ...

**1**

vote

**1**answer

694 views

### Multiple disjoint subset sum problem

Given two sets of nonnegative integer numbers:
$X = {x_1, x_2, ... x_n}$
$Y = {y_1, y_2, ... y_m}$
Need to find partition of $X$ on $m$ disjoint subsets, such as sum of elements in $i$-th subset ...

**12**

votes

**0**answers

306 views

### Best known constant for parallel sorting

I recently found myself talking about Szemerédi's mathematics, and briefly discussed his famous sorting network, discovered with Ajtai and Komlós. Apparently their algorithm is not practical because ...

**12**

votes

**3**answers

475 views

### Recognizing the 4-sphere and the Adjan--Rabin theorem

The problem of recognizing the standard $S^n$ is the following:
Given some simplicial complex $M$ with rational vertices representing a closed manifold,
can one decide (in finite time) if $M$ is ...

**5**

votes

**1**answer

313 views

### Fastest algorithm to compute (a^(2^N))%m?

Hi.
There are well-known algorithms for cryptography to compute modular exponentiation $a^b\%c$ (like Right-to-left binary method here : http://en.wikipedia.org/wiki/Modular_exponentiation).
But do ...

**9**

votes

**1**answer

916 views

### Groebner basis for Sudoku

I'm trying to write a program that solves sudoku's using a Groebner basis.
I introduced 81 variables $x_1$ to $x_{81}$, this is a linearisation of the sudoku board.
The space of valid sudokus is ...

**6**

votes

**2**answers

497 views

### Two groups acting on a set.

Suppose we are given a set S of points on which two different groups G and G' (given by sets of generating permutations) act. Is there an efficient algorithm for finding generators the largest pair ...

**1**

vote

**1**answer

191 views

### Shortest absolute value of path in graph

Suppose we have a weighted, acyclic digraph, with positive and negative edge weights.
Is there an algorithm that determines whether there is a path of weight zero between vertices A and B? The ...

**8**

votes

**0**answers

382 views

### Shortest path in Cayley graphs

The standard way to find the shortest path between 2 vertices, $v_1$ and $v_2$, of an undirected graph is BFS (breadth first search) which takes time $O(|E|)$ and space $O(|V|)$ (where $E$ is the set ...