We give the first two algorithms to enumerate all binary words of {0,1}^𝓁 (like Gray codes) while ensuring that the delay and the auxiliary space is independent from 𝓁, i.e., constant time for each word, and constant memory in addition to the 𝓁 bits storing the current word. Our algorithms are given in two new computational models: tape machines and deque machines. We also study more restricted models, queue machines and stack machines, and show that they cannot enumerate all binary words with constant auxiliary space, even with unrestricted delay. A tape machine is a Turing machine that stores the current binary word on a single working tape of length 𝓁 (which never increases), using no other tape. The machine has a single head and must edit its tape to reach all possible words of {0,1}^𝓁, and output them (in unit time, by entering special output states), with no duplicates. Hence a tape machine uses constant auxiliary space by definition (up to the head position). We construct a tape machine that achieves this task with constant delay between consecutive outputs, so that the machine implements a so-called skew-tolerant quasi-Gray code. We then construct a more involved tape machine that implements a Gray code. A deque machine stores the current binary word on a double-ended queue of length 𝓁, and stores a constant-size internal state. It works as a tape machine, except that it modifies the content of the deque by performing push and pop operations on the endpoints. Hence again a deque machine uses constant auxiliary space by definition. We construct deque machines that enumerate all words of {0,1}^𝓁 with constant-delay. The main technical challenge in this model is to correctly detect when enumeration has finished.

In this paper, we propose a method to build molecular cages designed to capture a specific substrate. We model a cage as a graph of atoms with coordinates in space, and several constraints on their edges (degree, length and angle). We use a simple method to place binding patterns which are able to interact with certain parts of the substrate. We then propose an algorithm which considers all possible ways of connecting these binding patterns and try to construct the smallest possible molecular paths realizing these connections. We investigate many variants of our method in order to obtain the most efficient algorithm, able to build cages of more than a hundred atoms.

Abstract The quality of enumeration algorithms is often measured by their delay, that is, the maximum time spent between the output of two distinct solutions. If the goal is to enumerate t distinct solutions for any given t , another relevant measure is the maximum time needed to output t solutions divided by t , a notion we call the amortized delay of the algorithm, since it can be seen as the amortized complexity of enumerating t elements of the set. In this paper, we study the relationship between these two notions of delay. We present several schemes that transform an algorithm with polynomial amortized delay, accessible only as a black box, into an algorithm with polynomial delay. We complement these results with several lower bounds and impossibility theorems in the black-box model.

We present a generic strategy improvement algorithm (GSIA) to find an optimal strategy of simple stochastic games (SSG). We prove the correctness of GSIA, and derive a general complexity bound, which implies and improves on the results of several articles. First, we remove the assumption that the SSG is stopping, which is usually obtained by a polynomial blowup of the game. Second, we prove a tight bound on the denominator of the values associated to a strategy, and use it to prove that all strategy improvement algorithms are in fact fixed parameter tractable in the number r of random vertices. All known strategy improvement algorithms can be seen as instances of GSIA, which allows to analyze the complexity of converge from below by Condon [Condon, 1993] and to propose a class of algorithms generalising Gimbert and Horn’s algorithm [Gimbert and Horn, 2008; Gimbert and Horn, 2009]. These algorithms terminate in at most r! iterations, and for binary SSGs, they do less iterations than the current best deterministic algorithm given by Ibsen-Jensen and Miltersen [Ibsen-Jensen and Miltersen, 2012].

The best algorithm so far for solving Simple Stochastic Games is Ludwig's randomized algorithm which works in expected $2^{O(\sqrt{n})}$ time. We first give a simpler iterative variant of this algorithm, using Bland's rule from the simplex algorithm, which uses exponentially less random bits than Ludwig's version. Then, we show how to adapt this method to the algorithm of Gimbert and Horn whose worst case complexity is $O(k!)$, where $k$ is the number of random nodes. Our algorithm has an expected running time of $2^{O(k)}$, and works for general random nodes with arbitrary outdegree and probability distribution on outgoing arcs.

In this paper we address the problem of generating all elements obtained by the saturation of an initial set by some operations. More precisely, we prove that we can generate the closure of a boolean relation (a set of boolean vectors) by polymorphisms with a polynomial delay. Therefore we can compute with polynomial delay the closure of a family of sets by any set of "set operations": union, intersection, symmetric difference, subsets, supersets $\dots$). To do so, we study the $Membership_{\mathcal{F}}$ problem: for a set of operations $\mathcal{F}$, decide whether an element belongs to the closure by $\mathcal{F}$ of a family of elements. In the boolean case, we prove that $Membership_{\mathcal{F}}$ is in P for any set of boolean operations $\mathcal{F}$. When the input vectors are over a domain larger than two elements, we prove that the generic enumeration method fails, since $Membership_{\mathcal{F}}$ is NP-hard for some $\mathcal{F}$. We also study the problem of generating minimal or maximal elements of closures and prove that some of them are related to well known enumeration problems such as the enumeration of the circuits of a matroid or the enumeration of maximal independent sets of a hypergraph. This article improves on previous works of the same authors.

We present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It is based on a new Gap theorem which allows to test whether P(X)=∑kj=1 αjXαj(1+X)βjis identically zero in polynomial time. The algorithm we obtain is more elementary than the one by Kaltofen and Koiran (ISSAC'05) since it relies on the valuation of polynomials of the previous form instead of the height of the coefficients. As a result, it can be used to find some linear factors of bivariate lacunary polynomials over a field of large finite characteristic in probabilistic polynomial time.

Polynomial identity testing and arithmetic circuit lower bounds are two central questions in algebraic complexity theory. It is an intriguing fact that these questions are actually related. One of the authors of the present paper has recently proposed a "real {\tau}-conjecture" which is inspired by this connection. The real {\tau}-conjecture states that the number of real roots of a sum of products of sparse univariate polynomials should be polynomially bounded. It implies a superpolynomial lower bound on the size of arithmetic circuits computing the permanent polynomial. In this paper we show that the real {\tau}-conjecture holds true for a restricted class of sums of products of sparse polynomials. This result yields lower bounds for a restricted class of depth-4 circuits: we show that polynomial size circuits from this class cannot compute the permanent, and we also give a deterministic polynomial identity testing algorithm for the same class of circuits.

Since their introduction in denoising, the family of non local methods, whose Non-Local Means (NL-Means) is the most famous member, has proved its ability to challenge other powerful methods such as wavelet based approaches or variational techniques. Though simple to implement and efficient in practice, the classical NL-Means suffers from ringing artifacts around edges. In this paper, we present an easy to implement and time efficient modification of the NL-means based on a better reprojection from the patches space to the original (image) pixel space. We illustrate the performance of our method on a toy example and on some classical images.