Search

Abstract Most cryptographic schemes are designed in a model where perfect secrecy of the secret key is assumed. In most physical implementations, however, some form of information leakage is inherent and unavoidable. To deal with this, a flurry of works showed how to construct basic cryptographic primitives that are resilient to various forms of leakage. Dodis et al. (FOCS '10) formalized and constructed leakage resilient one-way functions. These are one-way functions f such that given a random image f (x) and leakage g (x) it is still hard to invert f (x). Based on any one-way function, Dodis et al. constructed such a one-way function that is leakage resilient assuming that an attacker can leak any lossy function g of the input. In this work we consider the problem of constructing leakage resilient one-way functions that are secure with respect to arbitrary computationally hiding leakage (a.k.a. auxiliary-input). We consider both types of leakage – selective and adaptive – and prove various possibility and impossibility results. On the negative side, we show that if the leakage is an adaptively-chosen arbitrary one-way function, then it is impossible to construct leakage resilient one-way functions. The latter is proved both in the random oracle model (without any further assumptions) and in the standard model based on a strong vector-variant of DDH. On the positive side, we observe that when the leakage is chosen ahead of time, there are leakage resilient one-way functions based on a variety of assumption. [ABSTRACT FROM AUTHOR]

We prove a necessary and sufficient condition for a function being a polynomial function over a finite, commutative, unital ring. Further, we give an algorithm running in quasilinear time that determines whether or not a function given by its function table can be represented by a polynomial, and if the answer is yes then it provides one such polynomial. [ABSTRACT FROM AUTHOR]

We consider the NP-hard m - parallel two-stage flowshop problem, abbreviated as the ( m , 2 ) -PFS problem, where we need to schedule n jobs to m parallel identical two-stage flowshops in order to minimize the makespan, i.e. the maximum completion time of all the jobs on the m flowshops. The ( m , 2 ) -PFS problem can be decomposed into two subproblems: to assign the n jobs to the m parallel flowshops, and for each flowshop to schedule the jobs assigned to the flowshop. We first present a pseudo-polynomial time dynamic programming algorithm to solve the ( m , 2 ) -PFS problem optimally, for any fixed m , based on an earlier idea for solving the ( 2 , 2 ) -PFS problem. Using the dynamic programming algorithm as a subroutine, we design a fully polynomial-time approximation scheme (FPTAS) for the ( m , 2 ) -PFS problem. [ABSTRACT FROM AUTHOR]

Given a function from Z n to itself one can determine its polynomial representability by using Kempner function. In this paper we present an alternative characterization of polynomial functions over Z n by constructing a generating set for the Z n -module of polynomial functions. This characterization results in an algorithm that is faster on average in deciding polynomial representability. We also extend the characterization to functions in several variables. [ABSTRACT FROM AUTHOR]

We study the problem of trimming visibly pushdown automata ( VPA ). We first describe a polynomial time procedure which, given a visibly pushdown automaton that accepts only well-nested words, returns an equivalent visibly pushdown automaton that is trimmed. We then show how this procedure can be lifted to the setting of arbitrary VPA . Furthermore, we present a way of building, given a VPA , an equivalent VPA which is both deterministic and trimmed. Last, our trimming procedures can be applied to weighted VPA . [ABSTRACT FROM AUTHOR]

Abstract: Within the frameworks of learning in the limit of indexed classes of recursive languages from positive data and automatic learning in the limit of indexed classes of regular languages (with automatically computable sets of indices), we study the problem of minimizing the maximum number of mind changes by a learner on all languages with indices not exceeding . For inductive inference of recursive languages, we establish two conditions under which can be made smaller than any recursive unbounded non-decreasing function. We also establish how is affected if at least one of these two conditions does not hold. In the case of automatic learning, some partial results addressing speeding up the function are obtained. [Copyright &y& Elsevier]

Abstract: A preference function is a function which selects a subset of objects based on (partial) information. As information increases, different objects may be selected. We examine conditions under which the selection of objects converges to the choice that would be made if full information were available, making use of tools from domain theory. The work is motivated by previous research on co-evolutionary algorithms in which an evolving population of agents interact with each other and, it is hoped, produce better and better quality behaviour. The formalisation of how quality can be measured in this context has introduced the concept of a convex preference function (or “solution concept”). We simplify and extend the scope of this previous work, examining the relationship between convexity and convergence properties. [Copyright &y& Elsevier]

Abstract: Let denote an -vertex and -edge graph in which is a function mapping each vertex to a positive weight and is a function mapping each edge to a positive length . Given a positive integer , the -Center problem involves finding a set with vertices of to be the locations for building facilities. The objective is to minimize the maximum weighted distance from each vertex in – to its nearest vertex in . This paper considers a practical restriction: the induced subgraph of the selected vertices must be connected. The new variant is called the Connected -Center problem (the problem). For each fixed integer , on block graphs with exactly blocks, we first show that the problem is NP-hard when (1) , for all vertices , and , for all edges , and (2) , for all vertices , and , for all edges , respectively. Second, an -time algorithm for solving the problem on block graphs with unit vertex-weights and unit edge-lengths is proposed. Then, the algorithmic result is extended to handle the situation in which some vertices in cannot be included to form feasible solutions. The complexity of the extended algorithm is also . [Copyright &y& Elsevier]

Abstract: Dense sub-graphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Most existing community detection algorithms produce a hierarchical structure of communities and seek a partition into communities that optimizes a given quality function. We propose new methods to improve the results of any of these algorithms. First we show how to optimize a general class of additive quality functions (containing the modularity, the performance, and a new similarity based quality function which we propose) over a larger set of partitions than the classical methods. Moreover, we define new multi-scale quality functions which make it possible to detect different scales at which meaningful community structures appear, while classical approaches find only one partition. [ABSTRACT FROM AUTHOR]

Abstract: We show that there exist translations between polymorphic -calculus and a subsystem of minimal logic with existential types, which form a Galois insertion (embedding). The translation from polymorphic -calculus into the existential type system is the so-called call-by-name CPS-translation that can be expounded as an adjoint from the neat connection. The construction of an inverse translation is investigated from a viewpoint of residuated mappings. The duality appears not only in the reduction relations but also in the proof structures, such as paths between the source and the target calculi. From a programming point of view, this result means that abstract data types can interpret polymorphic functions under the CPS-translation. We may regard abstract data types as a dual notion of polymorphic functions. [Copyright &y& Elsevier]

Abstract: In this paper we use the theory of accessible categories to find fixed points of endofunctors on the category of 1-bounded complete metric spaces and nonexpansive functions. In contrast to previous approaches, we do not assume that the endofunctors are locally contractive, and our results do not depend on Banach’s fixed-point theorem. Our approach is particularly suitable for constructing models of systems that feature quantitative data. For instance, using the Kantorovich metric on probability measures we construct a quantitative model for probabilistic transition systems. The metric in our model can reasonably be seen as measuring the behavioural distance between states of the system; it depends exclusively on the transition probabilities and not on an arbitrary discount factor. [Copyright &y& Elsevier]

Abstract: We study a particular aspect of the balanced allocation paradigm (also known as the “two-choices paradigm”): constant sized bins, packed as tightly as possible. Let be fixed, and assume there are bins of capacity each. To each of balls two possible bins are assigned at random. How close can be to so that with high probability each ball can be put into one of the two bins assigned to it without any bin overflowing? We show that is sufficient. If a new ball arrives with two new randomly assigned bins, we wish to rearrange some of the balls already present in order to accommodate the new ball. We show that on average it takes constant time to rearrange the balls to achieve this, for , for some constant . An alternative way to describe the problem is in data structure language. Generalizing cuckoo hashing [R. Pagh, F.F. Rodler, Cuckoo hashing, J. Algorithms 51 (2004) 122–144], we consider a hash table with positions, each representing a bucket of capacity . Keys are assigned to buckets by two fully random hash functions. How many keys can be placed in these bins, if key may go to bin or to bin ? We obtain an implementation of a dictionary that accommodates keys in buckets of size , so that key resides in bucket or . For a lookup operation, only two hash functions have to be evaluated and two segments of contiguous memory cells have to be inspected. If , a static arrangement exists with high probability. If , a dynamic version of the dictionary exists so that the expected time for inserting a new key is . [Copyright &y& Elsevier]