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.     

Algorithms for a class of infinite permutation groups

Motivated by the famous 3n+1$3n+1$ conjecture, we call a mapping from Z$\mathbb{Z}$ to Z$\mathbb{Z}$residue-class-wise affine   if there is a positive integer m$m$ such that it is affine on residue classes (mod m$m$). This article describes a collection of algorithms and methods for computation in permutation groups and monoids formed by residue-class-wise affine mappings.     

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$.     

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.     

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.     

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.     

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.     

Optimal number of annuli for maximizing the lifetime of sensor networks

The most effective way to maximize the lifetime of a wireless sensor network (WSN) is to allocate initial energy to sensors such that they exhaust their energy at the same time. The lifetime of a WSN as well as an optimal initial energy allocation are determined by a network design. The main contribution of the paper is to show that the lifetime of a WSN can be maximized by an optimal network design. We represent the network lifetime as a function of the number m$m$ of annuli and show that m$m$ has significant impact on network lifetime. We prove that if the energy consumed by data transmission is proportional to d^α+c$d^{\alpha }+c$, where d$d$ is the distance of data transmission and α$\alpha$ and c$c$ are some constants, then for a circular area of interest with radius R$R$, the optimal number of annuli that maximizes the network lifetime is m=R((α−1)/c)^1/α$m=R{((\alpha -1)/c)}^{1/\alpha }$ for an arbitrary sensor density function.     

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.     

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.     

Learning multiple languages in groups

We consider a variant of Gold’s learning paradigm where a learner receives as input n$n$ different languages (in the form of one text where all input languages are interleaved). Our goal is to explore the situation when a more “coarse” classification of input languages is possible, whereas more refined classification is not. More specifically, we answer the following question: under which conditions, a learner, being fed n$n$ different languages, can produce m$m$ grammars covering all input languages, but cannot produce k$k$ grammars covering input languages for any k>m$k>m$. We also consider a variant of this task, where each of the output grammars may not cover more than r$r$ input languages. Our main results indicate that the major factor affecting classification capabilities is the difference n−m$n-m$ between the number n$n$ of input languages and the number m$m$ of output grammars. We also explore the relationship between classification capabilities for smaller and larger groups of input languages. For the variant of our model with the upper bound on the number of languages allowed to be represented by one output grammar, for classes consisting of disjoint languages, we found complete picture of relationship between classification capabilities for different parameters n$n$ (the number of input languages), m$m$ (number of output grammars), and r$r$ (bound on the number of languages represented by each output grammar). This picture includes a combinatorial characterization of classification capabilities for the parameters n,m,r$n,m,r$ of certain types.