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

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

State-complexity hierarchies of uniform languages of alphabet-size length

We study the state complexity of certain simple languages. If A$A$ is an alphabet of k$k$ letters, then a k$k$-language   is a nonempty set of words of length k$k$, that is, a uniform language of length k$k$. We show that the minimal state complexity of a k$k$-language is k+2$k+2$, and the maximal, (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. We prove constructively that, for every i$i$ between the minimal and maximal bounds, there is a language of state complexity i$i$. We introduce a class of automata accepting sets of words that are permutations of A$A$; these languages define a complete hierarchy of complexities between k²−k+3$k^2-k+3$ and 2^k+1$2^k+1$. The languages of another class of automata, based on k$k$-ary trees, define a complete hierarchy of complexities between 2^k+1$2^k+1$ and (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. This provides new examples of uniform languages of maximal complexity.     

Approximately optimal trees for group key management with batch updates

We investigate the group key management problem for broadcasting applications. Previous work showed that, in handling key updates, batch rekeying can be more cost effective than individual rekeying. One model for batch rekeying is to assume that every user has probability p$p$ of being replaced by a new user during a batch period with the total number of users unchanged. Under this model, it was recently shown that an optimal key tree can be constructed in linear time when p$p$ is a constant and in O(n⁴)$O\left(n^4\right)$ time when p→0$p\to 0$. In this paper, we investigate more efficient algorithms for the case p→0$p\to 0$, i.e., when membership changes are sparse. We design an O(n)$O\left(n\right)$ heuristic algorithm for the sparse case and show that it produces a nearly 2-approximation to the optimal key tree. Simulation results show that its performance is even better in practice. We also design a refined heuristic algorithm and show that it achieves an approximation ratio of 1+?$1+?$ for any fixed ?>0$?>0$ and n$n$, as p→0$p\to 0$. Finally, we give another approximation algorithm for any p∈(0,0.693)$p\in (0,0.693)$ which is shown to be quite good by our simulations.     

Expanders and time-restricted branching programs

The replication number   of a branching program is the minimum number R$R$ such that along every accepting computation at most R$R$ variables are tested more than once; the sets of variables re-tested along different computations may be different. For every branching program, this number lies between 0$0$ (read-once programs) and the total number n$n$ of variables (general branching programs). The best results so far were exponential lower bounds on the size of branching programs with R=o(n/logn)$R=o(n/logn)$. We improve this to R≤?n$R\le ?n$ for a constant ?>0$?>0$. This also gives an alternative and simpler proof of an exponential lower bound for (1+?)n$(1+?)n$ time branching programs for a constant ?>0$?>0$. We prove these lower bounds for quadratic functions of Ramanujan graphs.     

A parameterized view on matroid optimization problems

Matroid theory gives us powerful techniques for understanding combinatorial optimization problems and for designing polynomial-time algorithms. However, several natural matroid problems, such as 3-matroid intersection, are NP-hard. Here we investigate these problems from the parameterized complexity point of view: instead of the trivial n^O(k)$n^{O\left(k\right)}$ time brute force algorithm for finding a k$k$-element solution, we try to give algorithms with uniformly polynomial (i.e., f(k)⋅n^O(1)$f\left(k\right)\cdot n^{O\left(1\right)}$) running time. The main result is that if the ground set of a represented linear matroid is partitioned into blocks of size ?$?$, then we can determine in randomized time f(k,?)⋅n^O(1)$f(k,?)\cdot n^{O\left(1\right)}$ whether there is an independent set that is the union of k$k$ blocks. As a consequence, algorithms with similar running time are obtained for other problems such as finding a k$k$-element set in the intersection of ?$?$ matroids, or finding k$k$ terminals in a network such that each of them can be connected simultaneously to the source by ?$?$ disjoint paths.     

Modular Las Vegas algorithms for polynomial absolute factorization

Let f(X,Y)∈Z[X,Y]$f(X,Y)\in \mathbb{Z}[X,Y]$ be an irreducible polynomial over Q$\mathbb{Q}$. We give a Las Vegas absolute irreducibility test based on a property of the Newton polytope of f$f$, or more precisely, of f$f$ modulo some prime integer p$p$. The same idea of choosing a p$p$ satisfying some prescribed properties together with LLL$LLL$ is used to provide a new strategy for absolute factorization of f(X,Y)$f(X,Y)$. We present our approach in the bivariate case but the techniques extend to the multivariate case. Maple computations show that it is efficient and promising as we are able to construct the algebraic extension containing one absolute factor of a polynomial of degree up to 400.     

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.