Weighted Median Filtering

Let’s begin with a little review of unweighted median filtering. Suppose I have a list of N real-valued numbers, x=x1,…,xN. Let mi be the median of K consecutive values: mi= median(xi,…,xi+K). Let m=(m1,…,mN−K+1). The act of transforming x to m is called (unweighted) median filtering. We usually imagine N≫K, and frequently we assume that K … Read more

What is the influence of unreliable comparisons on the results of sorting

Considering sorting algorithms based solely on binary comparisons of the elements to be sorted(algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when those comparisons are unreliable? We assume the elements of the sequence x=(x1,x2,…,xn) to be sorted are distinct. We assume further that the only comparisons subject … Read more

How to enumerate a discrete group of matrices by their Frobenius norm?

Suppose I have a discrete group G<SL2(C), and it is finitely generated by some known generators. That is, G=⟨g1,…,gn⟩. The Frobenius norm of a matrix m=(abcd) is ‖. The set of elements in G having the same Frobenius norm is a discrete subset of a compact set, and therefore is finite. I’m interested in algorithms … Read more

Efficient CW structures on squarefree semi-algebraic set

General Setup Given a collection of $k$ polynomials (with real coefficients) in $n$ real variables, say $f_i(x_1,\ldots,x_n)$, let $V \subset \mathbb{R}^n$ correspond to those $x$-values for which every $f_i \geq 0$. If $V$ is compact, then there is an algorithm, doubly exponential in $n$, to impose a CW structure on $V$ via the so-called cylindrical … Read more

Optimal instructions for the modular construction of rectlinear Lego structures

Let X be a compact (or periodic) union of integer translates of unit cubes such that the interior of X is connected. (If it makes any difference, suppose that the dimension n of X is 3.) I am interested in finding a minimal (or at least reasonably small) and preferably “nice” decomposition of X into … Read more

In what range can we find diophantine approximations using the LLL-algorithm?

Let α1,…,αn be Q-linearly independent real numbers. I want to show that for all x1,…,xn∈Z, |xi|<N we have some lower bound for |∑xiαi|. For how many n and what range for N can this be done in reasonable time? Should I use specialized software or standard computer algebra packages? Note that I am not interested … Read more

Efficient algorithm to construct path augmented graphs with smallest diameter?

I am interested in special graph constructions that have the smallest diameter. We have a path graph $P_n$ ($N$ is even). We add new set of edges $C$ between path nodes such that set $C$ forms a perfect matching. The output graph is the union of path $P_n$ and perfect matching $C$ on the path … Read more

Parity of number of primes

In https://arxiv.org/abs/1009.3956 is it shown there is a c>0 such that π(x)mod2 can be computed in o(x^{\frac12}) time (more precisely number of primes \bmod 2 for an interval of length at most O(x^{\frac12+c}) in [x,2x] can be computed in time O(x^{\frac12-c}))? If so is there a good estimate known for c and is \frac12-c=o(1) believed … Read more

Finding short linear combinations in abelian groups

Let M be a finitely generated abelian group. Assume we are given a presentation of M, that is M=⨁ri=1Zgi∑sj=1Zrj where the gi are the generators and the rj are the relations. Let x be an element of M, given as a linear combination of the generators. I want to express x as a linear combination … Read more