The tag has no wiki summary.

learn more… | top users | synonyms

-2
votes
0answers
17 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
1answer
56 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
1answer
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, ...
0
votes
0answers
15 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 ...
2
votes
0answers
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 ...
-1
votes
0answers
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 ...
1
vote
2answers
96 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 ...
12
votes
1answer
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
1answer
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 ...
1
vote
0answers
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
0answers
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
4answers
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
0answers
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
1answer
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 ...
8
votes
0answers
236 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 ...
5
votes
0answers
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 ...
2
votes
1answer
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
1answer
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 ...
5
votes
1answer
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 ...
1
vote
1answer
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
0answers
56 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 ...
1
vote
1answer
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 ...
4
votes
2answers
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 ...
2
votes
0answers
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 ...
22
votes
0answers
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
1answer
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
1answer
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 ...
7
votes
0answers
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
2answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
8
votes
4answers
711 views

What does it mean when we say we have computed a number to a certain accuracy using a probabilistic algorithm?

My intention is to ask a general question about probabilistic (Monte Carlo) algorithms. But to keep things simple, I will focus on a few specific examples. Let me start the discussion with ...
1
vote
2answers
207 views

Regular paths along surface of sphere

I'm trying to create a program where a small ball is supposed to move along the surface of a sphere, which is given by its radius $r$ and the center $c$. The movement should be repetitive, so that ...
1
vote
0answers
89 views

Can we find structure constants of Lie Algebra for Lie Symmetry of ODE without solving determining equations?

Let's consider (for example) one scalar ODE. We are searching for Lie Symmetries of it. There is well-known result, that we can find size of Symmetry Group without solving determining equations. ...
0
votes
0answers
26 views

how to efficiently compute the mean function for non-homogeneous poisson process?

Suppose that I know all intensity functions lambda(t) during given period [0,t], how can I compute the mean function m(t) for non-homogeneous Poisson process? Basically, m(t) in the integral of ...
2
votes
0answers
47 views

finding dominating cycles in $2K_2$-free graphs

A cycle $C$ in a connected graph $G$ is called dominating if its complement $V(G)-V(C)$ is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in ...
3
votes
1answer
133 views

How to generate $n$ FP32 rationals s.t. no two distinct k-el. subsets have same sum?

First some Background: I have lots and lots of integer matrices, whose rows are $k$-combinations (without repetitions and sorted) of numbers from the set $S:=\{1,...,n\}$ and needed to be compared ...
11
votes
1answer
169 views

Fastest algorithm to compute the width of a poset

An colleague recently came to me with a problem concerning the scheduling of tasks in the presence of constraints (of the kind: task $x$ can't begin until task $y$ has been completed). It turned out ...
5
votes
2answers
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) = ...
1
vote
0answers
99 views

NP hard problems on geometric graphs

I have posted this question before but i don't feel i expressed my confusion clearly enough. So i would like to try and explain again. This is a proof of the minimum vertex cover for unit disk graphs ...
1
vote
0answers
62 views

Max flow with minimal requirements algo problem

While applying the algorithm to solve the max flow of the network with minimal requirements on edges, I have encountered a problem. The algorithm states: For graph G create an edge from target to ...
4
votes
1answer
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$ ...
4
votes
1answer
169 views

Resolvent of a triangular matrix

Suppose $A$ is a triangular matrix. What is the most efficient known algorithm to compute the polynomial (in $x$) matrix $(xI-A)^{-1}$? Of course, $(xI-A)^{-1}= N(x)/p_A(x)$, where $p_A$ is the ...
-2
votes
1answer
94 views

how to reduce 3-colorable graph to this? [closed]

suppose we have a finite set X and a set S of subsets of X and we want to determine is there a subset S' of S such that all members of X belong to exactly one set in S' I think the best problem to ...
0
votes
0answers
118 views

E- and A-algorithms for finite arithmetic prime progressions and other sets

(EDIT from scratch). Let $\ \mathbf a := (a_1\ \ldots\ a_n)\ $ be an increasing non-constant arithmetic progression of odd positive numbers. The goal here is to resolve efficiently one of the two ...
4
votes
1answer
156 views

Decomposing representations of finite groups of Lie type via computer

This is related to my previous question here. Let me remind you what that question asked: Let $\text{St}_n(\mathbb{F}_q)$ be the Steinberg module (over $\mathbb{C}$) for ...
0
votes
1answer
58 views

Intersection graphs

Does anybody know of a paper which proves that finding the maximum independent set in geometric intersection graphs is NP hard? Even general intersection graphs?
1
vote
0answers
116 views

Explicitly showing that a free group is LERF [closed]

Let $F$ be a free group on a finite set $X$, and let $M$ be a finitely generated subgroup. Marshall Hall's theorem states that $M$ is closed in the profinite topology on $F$. That is, $M$ is the ...
8
votes
1answer
299 views

Algorithm to produce random number with a gamma distribution

I'd like to produce pseudo-random numbers with different distributions for a Monte Carlo simulation. I've got the poisson distribution working nicely with an algorithm from Knuth. I'm having trouble ...
0
votes
0answers
114 views

Trilateration issues, when circles don't intersect

I'm working on Indoor localization where I've deployed multiple iBeacons in my environment. I'm taking distances from all the beacons through their RSSI values. They are not 100% accurate though. Now ...