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

Sub-quadratic Kolmogorov-Arnold?

The Kolmogorov-Arnold representation theorem says, essentially, that when computing a continuous function, the only multivariate function you really need is addition. (Somewhat) more precisely, it says that for any continuous function f:Rn→R, we can write f as f(x)=f(x1,…,xn)=2n∑q=0Φq(n∑p=1ϕq,p(xp)) If we count function evaluations (the additions, the Φq‘s and the ϕq,p‘s), we perform O(n2) operations. Is … Read more

Amortized complexity of P

Let P be the class of all polynomial time computable functions from {0,1}∗→{0,1}. For any f∈P, define function fA:N→{0,1}∗ by fA(n)=(f(x1),⋯,f(x2n)), where xi runs over all strings in {0,1}n. Suppose the time complexity of f with input size n is nk, we know that fA(n) can be computed in nk2n by simply compute f on … Read more

Disjoint paths in temporal graphs

Given a graph G=(V,E) and a pair of source-destination nodes s and t. Time is divided in periods with the total number of periods denoted by T. Each edge e is either operational or broken at each period τ. A path is good at period τ if all its edges are operational at period τ. … Read more