The algorithms tag has no wiki summary.

**-2**

votes

**0**answers

15 views

### What is the most efficient algorithmic implementation of maximum overlap discrete wavelet transform? [on hold]

What is the most efficient algorithmic implementation of maximum overlap discrete wavelet transform (MODWT)?

**4**

votes

**3**answers

524 views

### Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...

**0**

votes

**1**answer

171 views

### Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...

**10**

votes

**8**answers

4k 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 ...

**2**

votes

**1**answer

107 views

### Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...

**3**

votes

**1**answer

715 views

### Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq ...

**4**

votes

**1**answer

55 views

### Smallest sum $S \geq k > 0$ using one element from each of several sets of nonnegative integers

Does there exist a way to efficiently solve the following problem?
Given some constant $k$ and several sets of non-negative integers:
...

**3**

votes

**1**answer

79 views

### What is the Complexity Class of the “Function Variant” of the Integer Factorization Problem?

I've been reading up a lot Prime Factorization and it's complexity, including a fair number of questions on this very site. However, I still feel there is a question still left unanswered.
So, ...

**2**

votes

**0**answers

76 views

### Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)

Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of ...

**0**

votes

**0**answers

14 views

### Complexity of optimizing a bi-objective function with integer constraints

I have two different objective functions, each of which can be solved optimally in polynomial time. Does this mean, I can optimize a linear combination of these objective functions in polynomial time ...

**11**

votes

**1**answer

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

**7**

votes

**1**answer

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

**-1**

votes

**0**answers

17 views

### $f(n)=3f(\frac{n}{3})+O(logn)$ [migrated]

I was asked to figure out the time complexity analysis for the following recurrence relation:
$f(n)=3f(\frac{n}{3})+O(logn)$
I worked it out as O(nlgn), Would like to know if this is right or ...

**12**

votes

**1**answer

347 views

### Computer software for periods

Kontsevich and Zagier define a period as an integral of a rational function (over $\mathbb{Q}$) defined on a $\mathbb{Q}$-semialgebraic set. They conjecture that if two periods are equal, then the ...

**1**

vote

**2**answers

95 views

### Curves similarity metric [closed]

I am working on an optical character recognition algorithm that takes vector data (i.e. polylines) as input rather than raster picture. E.g., we have N polyline samples, and when certain polyline is ...

**13**

votes

**4**answers

7k views

### Finding a cycle of fixed length

Is there any result about the time complexity of finding a cycle of fixed length k in a general graph?
All I know is that Noga Alon et al. use the techinique called "color-coding",
which has a running ...

**1**

vote

**1**answer

47 views

### Hamiltonian Path through $n$-bit strings with maximum number of $0\mapsto 1$ transitions

Let $G_n$ be the complete graph whose vertices are the $2^n$ $n$-bit strings. Let $H_n$ denote the Hamiltonian path through $G_n$ that uses the maximum number of edges that correspond to a single bit ...

**2**

votes

**3**answers

799 views

### Is there a simple criterion to determine if two parallelograms intersect?

Assume we are given two parallelograms in the plane. How can I check if their intersection is nonempty?
Note that I do not need to actually find the intersection.

**3**

votes

**1**answer

114 views

### Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...

**4**

votes

**1**answer

387 views

### How to test if the power of some algebraic number is the rational combination of two specific algebraic numbers?

Suppose we are given three algebraic numbers $\alpha,\beta,\gamma$ by presenting their minimal polynomial (degree less than $m$), the goal is to compute all positive integers $n$ such that $\alpha^n$ ...

**10**

votes

**4**answers

2k 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" ...

**1**

vote

**0**answers

45 views

### Select n vectors from k vectors (in 3D) such that each component of the resultant vector >= each component of a given vector M

this was left unanswered for 1 week on MStackExchange, so I thought MOverflow would be more appropriate. Thanks :)
Let $R = (R_x, R_y, R_z)$ be the resultant vector of the n vectors and $M = (M_x, ...

**1**

vote

**0**answers

28 views

### Can we give efficiently the solution of a bilinear system of equations over a finite field?

Consider a finite field $F$ and suppose we have a system of equations
$$h_1(\alpha,\beta)=0,h_2(\alpha,\beta)=0,...,h_t(\alpha,\beta)=0$$
where $\alpha=(\alpha_1,...,\alpha_s)$ and ...

**6**

votes

**4**answers

356 views

### Expected value of a function over random sets

I am doing an analysis on the complexity of some set-related algorithm where the input is a random set. One of my setbacks can be formulated as follows:
Pick $k$ distinct numbers out of numbers ...

**2**

votes

**0**answers

154 views

### Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning? [closed]

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics).
It seems to me that much ...

**2**

votes

**1**answer

66 views

### Is there any algorithm can find local minima of nonconvex objective function in guaranteed polynomial time?

More precisely, The setting could be formulated as,
$min. F_{\lambda}(p)$ over permutation matrices $P$
Here $F_{\lambda}(p)$=$\lambda *F_{0}(p)+(1-\lambda)F_{1}(p)$
where both $F_{0}(p)$ and ...

**3**

votes

**2**answers

746 views

### algorithm for solving systems of linear Diophantine inequalities

So, I posted on stack overflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem ...

**5**

votes

**0**answers

198 views

### When does a “stable” assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods.
We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...

**8**

votes

**0**answers

235 views

### Is it decidable whether a finite type scheme is proper?

Let $k$ be a field and let $X$ be a finite type scheme over $k$, explicitly given by finitely many affine patches which are $\mathrm{Spec}$ of finitely generated $k$-algebras, glued along other affine ...

**2**

votes

**1**answer

74 views

### Future-Proof Encrypt for Multiple Independent Parties

I have a secret message which I want to encrypt such that any of several different keys can open it independently. The keys can't know about each other and it has to be able to work completely ...

**3**

votes

**1**answer

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

**5**

votes

**1**answer

153 views

### Find subset of collection of sets whose intersection has minimum average value

Let $a_1,\ldots,a_n>0$, and let $S_1,\ldots,S_d\subset\{1,\ldots,n\}$ (all non-empty).
For any $I\subseteq\{1,\ldots,d\}$, define $S(I)=\bigcap_{i\in I} S_i$.
Given some $1\leq s < d$, consider ...

**12**

votes

**1**answer

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

**1**

vote

**1**answer

87 views

### Finding Laurent Series of a function [closed]

I've been assigned to write a computer program which then calculates the Laurent series of a function. Of course I'm familiar with the concept, but I've always calculated the Laurent series in an ad ...

**0**

votes

**0**answers

55 views

### Generating alternating cycles on a perfect matching

Given a perfect matching $M$ in a regular bipartite graph $G$, is there an efficient algorithm to randomly generate self-avoiding alternating cycles with uniform distribution? Ideally, such an ...

**4**

votes

**2**answers

206 views

### An algorithm to compare two representations of a simple Lie algebra?

I have two representations of a simple (complex or real) finite-dimensional Lie algebra $S$, both given in terms of their structure constants on a given basis.
the first one is the adjoint ...

**1**

vote

**1**answer

93 views

### Computation Complexity for Golden Section method

I need to provide computational complexity for the algorithms in my work. One of the algorithms I have used is Golden Section method for line search. I took a look at "Nonlinear Programming" book by ...

**22**

votes

**0**answers

643 views

### On certain representations of algebraic numbers in terms of trigonometric functions

Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...

**2**

votes

**0**answers

49 views

### Computing maximal ideals of a Lie algebra

Would you know an algorithm (or an automatic method) that computes all maximal ideals $J$ of a given Lie algebra?
Or an algorithm that computes all maximal ideals $J$ containing a given minimal ideal ...

**4**

votes

**2**answers

310 views

### Finding the set of all $0$-$1$ vectors in an affine subspace

We are given a $0$-$1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0$-$1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or ...

**2**

votes

**1**answer

203 views

### Minimally intersecting subsets of fixed size

The question I have, is how to generate the following collection of subsets:
Given a set $S$ of size $n$. I want to find a sequence of $k$ subsets of fixed size $m$, $0<m<n$, such that at each ...

**1**

vote

**1**answer

76 views

### QR decomposition of matrix [closed]

I have matrix $M = \begin{pmatrix} A & B \\ B^T & 0\end{pmatrix}$, where $A$ is $N\times N$, $B$ is $N\times 2$ and I have $Q$, $R$ such that $A = QR$. What is the fastest way to find $Q'$ and ...

**5**

votes

**2**answers

202 views

### Compute adjugate matrix over commutative ring

Let $A$ be a $n\times n$ matrix over a commutative ring. I'm looking for a good method to compute its adjugate matrix.
My current approach is to use the Cayley-Hamilton theorem:
$$\text{adj}(A) = ...

**20**

votes

**12**answers

7k views

### What are the Applications of Hypergraphs

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...

**16**

votes

**3**answers

1k views

### does the “convolution theorem” apply to weaker algebraic structures?

The Convolution Theorem is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse ...

**7**

votes

**0**answers

136 views

### Is there an infinite increasing sequence of naturals for which Landau's function can be efficiently computed?

Landau's function
$g(n)$ is the largest order of an element of the symmetric group $S_n$.
Equivalently, $g(n)$ is the largest least common multiple (lcm) of any partition of $n$.
In general $g(n)$ is ...

**5**

votes

**2**answers

184 views

### Minimum number of unit fractions to sum up a given positive rational

For any positive $p,q\in\mathbb{N}$ there is a finite subset $S$ of $\{\frac{1}{n}:n\in\mathbb{N}, n\geq 1\}$ such that $\sum_{s\in S} s=\frac{p}{q}$. Let $m(p,q)$ denote the minimal cardinality of ...

**3**

votes

**1**answer

90 views

### Sorting interleaved sorted lists

By interleaving two lists I mean to combine them into a single list in any way that maintains the relative order of the elements coming from each list. For example, interleaving $(x_1,x_2,x_3)$ and ...

**0**

votes

**0**answers

67 views

### Parallelism degree of a DAG

Let me first give a motivation. Suppose a connected DAG G with one source X and one sink Y. The goal is to find some "bottleneck" node between X and Y, i.e. node through which every path from X to Y ...

**23**

votes

**5**answers

1k views

### Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...