Algorithms for near solutions to polynomial equations

Let F(x,y)$F(x,y)$ be a polynomial over a field K$K$ and m$m$ a nonnegative integer. We call a polynomial g$g$ over K$K$ an m$m$-near solution of F(x,y)$F(x,y)$ if there exists a c∈K$c\in K$ such that F(x,g)=cx^m$F(x,g)=c{x}^m$, and the number c$c$ is called an m$m$-value of F(x,y)$F(x,y)$ corresponding to g$g$. In particular, c$c$ can be 0. Hence, by viewing F(x,y)=0$F(x,y)=0$ as a polynomial equation over K[x]$K\left[x\right]$ with variable y$y$, every solution of the equation F(x,y)=0$F(x,y)=0$ in K[x]$K\left[x\right]$ is also an m$m$-near solution. We provide an algorithm that gives all m$m$-near solutions of a given polynomial F(x,y)$F(x,y)$ over K$K$, and this algorithm is polynomial time reducible to solving one variable equations over K$K$. We introduce approximate solutions to analyze the algorithm. We also give some interesting properties of approximate solutions.     

Claw finding algorithms using quantum walk

The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f$f$ and g$g$, with domain sizes N$N$ and M$M$(N≤M)$(N\le M)$, respectively, and the same range, the goal of the problem is to find x$x$ and y$y$ such that f(x)=g(y)$f\left(x\right)=g\left(y\right)$. This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of k$k$ functions for any constant integer k>1$k>1$, where the domain sizes of the functions may be different.     

The number of roots of a lacunary bivariate polynomial on a line

We prove that a polynomial f∈R[x,y]$f\in \mathbb{R}[x,y]$ with t$t$ non-zero terms, restricted to a real line y=ax+b$y=ax+b$, either has at most 6t−4$6t-4$ zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial y−ax−b∈K[x,y]$y-ax-b\in K[x,y]$ divides a lacunary polynomial f∈K[x,y]$f\in K[x,y]$, where K$K$ is a real number field. The number of bit operations performed by the algorithm is polynomial in the number of non-zero terms of f$f$, in the logarithm of the degree of f$f$, in the degree of the extension K/Q$K/\mathbb{Q}$ and in the logarithmic height of a$a$, b$b$ and f$f$.     

Paths and trails in edge-colored graphs

This paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices s$s$ and t$t$ in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s−t$s-t$ path/trail problem have polynomial solutions including the shortest path/trail case. We give polynomial algorithms for finding a longest properly edge-colored path/trail between s$s$ and t$t$ for a particular class of graphs and characterize edge-colored graphs without properly edge-colored closed trails. Next, we prove that deciding whether there exist k$k$ pairwise vertex/edge disjoint properly edge-colored s−t$s-t$ paths/trails in a c$c$-edge-colored graph G^c$G^c$ is NP-complete even for k=2$k=2$ and c=Ω(n²)$c=\Omega \left(n^2\right)$, where n$n$ denotes the number of vertices in G^c$G^c$. Moreover, we prove that these problems remain NP-complete for c$c$-edge-colored graphs containing no properly edge-colored cycles and c=Ω(n)$c=\Omega \left(n\right)$. We obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs.     

Non-reducible descriptions for conditional Kolmogorov complexity

Assume that a program p$p$ on input a$a$ outputs b$b$. We are looking for a shorter program q$q$ having the same property (q(a)=b$q\left(a\right)=b$). In addition, we want q$q$ to be simple conditional to p$p$ (this means that the conditional Kolmogorov complexity K(q|p)$K\left(q\right|p)$ is negligible). In the present paper, we prove that sometimes there is no such program q$q$, even in the case when the complexity of p$p$ is much bigger than K(b|a)$K\left(b\right|a)$. We give three different constructions that use the game approach, probabilistic arguments and algebraic arguments, respectively.     

Origami fold as algebraic graph rewriting

We formalize paper fold (origami) by graph rewriting. Origami construction is abstractly described by a rewriting system (O,?)$(\mathbb{O},?)$, where O$\mathbb{O}$ is the set of abstract origamis and ?$?$ is a binary relation on O$\mathbb{O}$, that models fold  . An abstract origami is a structure (Π,∽,?)$(\Pi ,\backsim ,?)$, where Π$\Pi$ is a set of faces constituting an origami, and ∽$\backsim$ and ?$?$ are binary relations on Π$\Pi$, each representing adjacency and superposition relations between the faces.     

Spanners for bounded tree-length graphs

This paper concerns construction of additive stretched spanners with few edges for n$n$-vertex graphs having a tree-decomposition into bags of diameter at most δ$\delta$, i.e., the tree-length δ$\delta$ graphs. For such graphs we construct additive 2δ$2\delta$-spanners with O(δn+nlogn)$O(\delta n+nlogn)$ edges, and additive 4δ$4\delta$-spanners with O(δn)$O\left(\delta n\right)$ edges. This provides new upper bounds for chordal graphs for which δ=1$\delta =1$. We also show a lower bound, and prove that there are graphs of tree-length δ$\delta$ for which every multiplicative δ$\delta$-spanner (and thus every additive (δ−1)$(\delta -1)$-spanner) requires Ω(n^1+1/Θ(δ))$\Omega \left(n^{1+1/\Theta \left(\delta \right)}\right)$ edges.     

Extension of the decidability of the marked PCP to instances with unique blocks

In the Post Correspondence Problem (PCP) an instance (h,g)$(h,g)$ consists of two morphisms h$h$ and g$g$, and the problem is to determine whether or not there exists a nonempty word w$w$ such that h(w)=g(w)$h\left(w\right)=g\left(w\right)$. Here we prove that the PCP is decidable for instances with unique blocks using the decidability of the marked PCP. Also, we show that it is decidable whether an instance satisfying the uniqueness condition for continuations has an infinite solution. These results establish a new and larger class of decidable instances of the PCP, including the class of marked instances.     

Minimum cost source location problem with local 3-vertex-connectivity requirements

Let G=(V,E)$G=(V,E)$ be a simple undirected graph with a set V$V$ of vertices and a set E$E$ of edges. Each vertex v∈V$v\in V$ has a demand d(v)∈_Z+$d\left(v\right)\in Z_{+}$ and a cost c(v)∈_R+$c\left(v\right)\in R_{+}$, where _Z+$Z_{+}$ and _R+$R_{+}$ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G$G$ requires finding a set S$S$ of vertices minimizing _∑v∈Sc(v)${\sum }_{v\in S}c\left(v\right)$ such that there are at least d(v)$d\left(v\right)$ pairwise vertex-disjoint paths from S$S$ to v$v$ for each vertex v∈V−S$v\in V-S$. It is known that if there exists a vertex v∈V$v\in V$ with d(v)≥4$d\left(v\right)\ge 4$, then the problem is NP-hard even in the case where every vertex has a uniform cost. In this paper, we show that the problem can be solved in O(|V|⁴log²|V|)$O\left({\left|V\right|}^4{log}^2\left|V\right|\right)$ time if d(v)≤3$d\left(v\right)\le 3$ holds for each vertex v∈V$v\in V$.     

Choosing starting values for certain Newton–Raphson iterations

We aim at finding the best possible seed values when computing a^1/p$a^{1/p}$ using the Newton–Raphson iteration in a given interval. A natural choice of the seed value would be the one that best approximates the expected result. It turns out that in most cases, the best seed value can be quite far from this natural choice. When we evaluate a monotone function f(a)$f(a)$ in the interval [_amin,_amax]$[a_{\min },a_{\max }]$, by building the sequence _xn$x_n$ defined by the Newton–Raphson iteration, the natural choice consists in choosing _x0$x_0$ equal to the arithmetic mean of the endpoint values. This minimizes the maximum possible distance between _x0$x_0$ and f(a)$f(a)$. And yet, if we perform n$n$ iterations, what matters is to minimize the maximum possible distance between _xn$x_n$ and f(a)$f(a)$. In several examples, the value of the best starting point varies rather significantly with the number of iterations.     

Large independent sets in random regular graphs

We present algorithmic lower bounds on the size _sd$s_d$ of the largest independent sets of vertices in random d$d$-regular graphs, for each fixed d≥3$d\ge 3$. For instance, for d=3$d=3$ we prove that, for graphs on n$n$ vertices, _sd≥0.43475n$s_d\ge 0.43475n$ with probability approaching one as n$n$ tends to infinity.     

Faster algorithms for computing Hong’s bound on absolute positiveness

We show how to compute Hong’s bound for the absolute positiveness of a polynomial in d$d$ variables with maximum degree δ$\delta$ in O(nlog^dn)$O\left(n{log}^{d}n\right)$ time, where n$n$ is the number of non-zero coefficients. For the univariate case, we give a linear time algorithm. As a consequence, the time bounds for the continued fraction algorithm for real root isolation improve by a factor of δ$\delta$.