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.     

Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

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.     

Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor

We consider a two-edge connected, undirected graph G=(V,E)$G=(V,E)$, with n$n$ nodes and m$m$ non-negatively real weighted edges, and a single source shortest paths tree (SPT) T$T$ of G$G$ rooted at an arbitrary node r$r$. If an edge in T$T$ is temporarily removed, it makes sense to reconnect the nodes disconnected from the root by adding a single non-tree edge, called a swap edge  , instead of rebuilding a new optimal SPT from scratch. In the past, several optimality criteria have been considered to select a best possible swap edge. In this paper we focus on the most prominent one, that is the minimization of the average distance between the root and the disconnected nodes. To this respect, we present an O(mlog²n)$O\left(m{log}^{2}n\right)$ time and O(m)$O\left(m\right)$ space algorithm to find a best swap edge for every edge of T$T$, thus improving for m=o(n²/log²n)$m=o(n^2/{log}^{2}n)$ the previously known O(n²)$O\left(n^2\right)$ time and space complexity algorithm.     

Optimal lower bounds for rank and select indexes

We develop a new lower bound technique for data structures. We show an optimal Ω(nlglgn/lgn)$\Omega (nlglgn/lgn)$ space lower bounds for storing an index that allows to implement rank and select queries on a bit vector B$B$ provided that B$B$ is stored explicitly. These results improve upon [Peter Bro Miltersen, Lower bounds on the size of selection and rank indexes, in: Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms, 2005, pp. 11–12]. We show Ω((m/t)lgt)$\Omega ((m/t)lgt)$ lower bounds for storing rank/select index in the case where B$B$ has m$m$ 1$1$-bits in it and the algorithm is allowed to probe t$t$ bits of B$B$. We also present an improved data structure that implements both rank and select queries with an index of size (1+o(1))(nlglgn/lgn)+O(n/lgn)$(1+o\left(1\right))(nlglgn/lgn)+O(n/lgn)$, that is, compared to existing results we give an explicit constant for storage in the RAM model with word size lgn$lgn$. An advantage of this data structure is that both rank and select indexes share the most space consuming part of order Θ(nlglgn/lgn)$\Theta (nlglgn/lgn)$ making it more practical for implementation.     

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.     

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.     

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.     

An efficient method of DFT/LDA band-gap correction

It has been shown that the underestimated by DFT/LDA(GGA) band-gap can be efficiently corrected by an averaging procedure of transition energies over a region close to the direct band-gap transition, which we call the Δ(EIG)$\Delta \left(EIG\right)$ method (the differences in the Kohn–Sham eigenvalues). For small excitations the averaging appears to be equivalent to the Δ(SCF)$\Delta \left(SCF\right)$ approach (differences in the self-consistent energies), which is a consequence of Janak’s theorem and has been confirmed numerically. The Gaussian distribution in k$k$-space for electronic excitation has been used (occupation numbers in the Δ(SCF)$\Delta \left(SCF\right)$ or eigenenergy sampling in the Δ(EIG)$\Delta \left(EIG\right)$). A systematic behavior of the k$k$-space localization parameter _σk${\sigma }_k$ correcting the band-gap has been observed in numerical experiments. On that basis some sampling schemes for band-gap correction have been proposed and tested in the prediction of the band-gap behavior in I_nxG_a(1−x)N$I{n}_{x}G{a}_{(1-x)}N$ semiconducting alloy, and a very good agreement with independent calculations has been obtained. In the context of the work the issue of electron localization in the r$r$-space has been discussed which, as it has been predicted by Mori-Sánchez et al. [P. Mori-Sánchez, A.J. Cohen, W. Yang, Phys. Rev. Lett. 100 (2008) 146401], should reduce the effect of the convex behavior of the LDA/GGA functionals and improve the band-gap prediction within DFT/LDA(GGA). A scheme for electron localization in r$r$-space has been suggested.     

Adaptive timeliness of consensus in presence of crash and timing faults

The Δ$\mathrm{\Delta }$-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: every correct process terminates its execution within a constant time Δ$\mathrm{\Delta }$ (Δ$\mathrm{\Delta }$-timeliness), and no two processes decide differently (uniformity). In this paper, we consider the Δ$\mathrm{\Delta }$-timed uniform consensus problem in presence of _fc$f_{\mathrm{c}}$ crash processes and _ft$f_{\mathrm{t}}$ timing-faulty processes, and propose a Δ$\mathrm{\Delta }$-timed uniform consensus algorithm. The proposed algorithm is adaptive in the following sense: it solves the Δ$\mathrm{\Delta }$-timed uniform consensus when at least _ft+1$f_{\mathrm{t}}+1$ correct processes exist in the system. If the system has less than _ft+1$f_{\mathrm{t}}+1$ correct processes, the algorithm cannot solve the Δ$\mathrm{\Delta }$-timed uniform consensus. However, as long as _ft+1$f_{\mathrm{t}}+1$ processes are non-crashed, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ$\mathrm{\Delta }$-timed uniform consensus algorithm tolerating up to _ft$f_{\mathrm{t}}$ timing-faulty processes requires that the system has at least _ft+1$f_{\mathrm{t}}+1$ correct processes. This impossibility result implies that the proposed algorithm attains the maximum resilience about the number of faulty processes. We also show that any Δ$\mathrm{\Delta }$-timed uniform consensus algorithm tolerating up to _ft$f_{\mathrm{t}}$ timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than _ft+1$f_{\mathrm{t}}+1$ non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness.     

A new self-stabilizing maximal matching algorithm

The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given several self-stabilizing algorithms that solve the problem for both the adversarial and the fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it has the same time complexity as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best time complexities for the distributed adversarial daemon from O(n²)$O\left(n^2\right)$ and O(δm)$O\left(\delta m\right)$ to O(m)$O\left(m\right)$ where n$n$ is the number of processes, m$m$ is the number of edges, and δ$\delta$ is the maximum degree in the graph.     

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.     

Efficient pebbling for list traversal synopses with application to program rollback

We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lgn)$O(lgn)$ memory for a list of size n$n$, the i$i$’th back-step from the farthest point reached so far takes O(lgi)$O(lgi)$ time in the worst case, while the overhead per forward step is at most ?$?$ for arbitrary small constant ?>0$?>0$. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: k$k$ vs. kn^1/k$k{n}^{1/k}$ and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n^1/k$n^{1/k}$-ary, tree that can only be traversed in a pre-order fashion.