The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
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
2answers
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
1answer
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
2answers
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
1answer
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
4answers
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
2answers
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
2answers
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
1answer
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
3answers
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
0answers
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
0answers
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
2answers
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
1answer
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
0answers
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
3answers
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
0answers
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
3answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
3answers
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
0answers
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
1answer
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
2answers
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
0answers
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
3answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
3answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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 ...