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

Effective “almost enumeration” of monotone boolean functions

Denote by M(n) the set of all monotone functions {0,1}n→{0,1}. Can M(n) be represented as M(n)={f(t)|t∈{0,1}k} such that: 1) k=log|M(n)|+O(n) 2) f∈DTIME(2O(n)) ? (I mean that f(i) is a truth table of a boolean function) Answer AttributionSource : Link , Question Author : Alexey Milovanov , Answer Author : Community

Fast matrix-vector product for structured matrices

Let $X\in\mathbb{C}^{m\times n}$ be a matrix that satisfies the Sylvester equation $$AX-XB = F,\qquad A\in\mathbb{C}^{m\times m}, \quad B\in\mathbb{C}^{n\times n},$$ where $F\in\mathbb{C}^{m\times n}$ is of low rank. In special cases as shown in http://math.mit.edu/~plamen/files/mds.pdf there are known algorithms for a fast matrix-vector product, i.e., computing $X\underline{v}$ in quasilinear complexity. These special cases include Toeplitz-like, Hankel-like, Cauchy-like, … Read more

Collapsing the Intuitionistic Bounded Arithmetics Hierarchy

Let iT be the intuitionistic first order theory with non-logical axioms of classical first order theory T. Theorem1. If Ti2⊢T2, then Ti2 proves that the polynomial time hierarchy collapses to Σpi+3. proof. See Relating the Bounded Arithmetic and Polynomial-Time Hierarchies. Corollary. There exists i∈N such that Ti2⊢T2 iff there exists j∈N such that iTj2⊢iT2. proof. … Read more

Complexity of counting colorings of co-bipartite graphs?

A graph is co-bipartite if it is the complement of bipartite graph. What is the complexity of counting colorings of co-bipartite graphs? Unlike split graphs, the chromatic polynomial isn’t of particularly simple form. Co-bipartite graphs are also known as (2,0)-colorable. Answer AttributionSource : Link , Question Author : joro , Answer Author : Community

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

Complexity of extending $P_4$-partition of cubic graphs

Surprising phenomena occurs when we want to extend a partial solution of some easy problems. We are given part of the solution and we want to decide whether we can extend it to a complete solution. Extendability problem transforms an easy problem to hard one. For instance, Konig-Hall theorem states that all cubic bipartite graphs … Read more