Search

Abstract The sensitivity conjecture proposed by Nisan and Szegedy in 1994, which asserts that for any Boolean function, its sensitivity complexity is polynomially related to the block sensitivity complexity, is one of the most important and challenging problems in the study of decision tree complexity. Despite a lot of efforts, the best known upper bound of block sensitivity, as well as the certificate complexity, is still exponential in terms of sensitivity. In this paper, we give a better upper bound for certificate complexity and block sensitivity, b s (f) ≤ C (f) ≤ (8 9 + o (1)) s (f) 2 s (f) − 1 , where b s (f) , C (f) and s (f) are the block sensitivity, certificate complexity and sensitivity, respectively. The proof is based on a deep investigation on the structure of the sensitivity graph. We also provide a tighter relationship between the 0-certificate complexity C 0 (f) and 0-sensitivity s 0 (f) for functions with small 1-sensitivity s 1 (f). [ABSTRACT FROM AUTHOR]

The Small Exponent Test (SET) for exponentiation is an essential batch-verification technique that is widely applied. In this paper, we propose a simplified SET that can securely batch-verify n instances with only n − 1 randomizing exponents. We show that the structure of the proposed batch test is compact in the sense that it works with a minimal number of randomizing exponents for the SET. Thus, our test offers various advantages. Overall, compared to the original SET, the proposed simplified SET is more efficient for any sized batch instance. In particular, unlike the SET, our proposal performs well even when the size of a batch instance is small, e.g., n = 1 , 2 , 3 , and 4. This feature can be also used to significantly reduce pairing computations in a signature scheme where several pairing equations are verified. In addition, our test can be combined easily and generically with existing batch techniques such as the use of sparse exponents, the bucket test for large batch sizes, or an automated tool to generate a batch algorithm. Finally, with our simplified test, an efficient identification algorithm can be constructed to discover incorrect instances in a batch. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study two interesting variants of the classical bin packing problem, called Lazy Bin Covering (LBC) and Cardinality Constrained Maximum Resource Bin Packing (CCMRBP) problems. For the offline LBC problem, we first prove the approximation ratio of the First-Fit-Decreasing and First-Fit-Increasing algorithms, then present an APTAS. For the online LBC problem, we give a competitive analysis for the algorithms of Next-Fit, Worst-Fit, First-Fit, and a modified HARMONIC algorithm. The CCMRBP problem is a generalization of the Maximum Resource Bin Packing (MRBP) problem Boyar et al. (2006) . For this problem, we prove that its offline version is no harder to approximate than the offline MRBP problem. [Copyright &y& Elsevier]

Abstract: This paper concerns learning binary-valued functions defined on , and investigates how a particular type of ‘regularity’ of hypotheses can be used to obtain better generalization error bounds. We derive error bounds that depend on the sample width (a notion analogous to that of sample margin for real-valued functions). This motivates learning algorithms that seek to maximize sample width. [Copyright &y& Elsevier]

Abstract: This paper describes several classes of term rewriting systems (TRS’s), where narrowing has a finite search space and is still (strongly) complete as a mechanism for solving reachability goals. These classes do not assume confluence of the TRS. We also ascertain purely syntactic criteria that suffice to ensure the termination of narrowing, and include several subclasses of popular TRS’s such as right-linear TRS’s, almost orthogonal TRS’s, topmost TRS’s, and left-flat TRS’s. Our results improve and/or generalize previous criteria in the literature regarding narrowing termination. [Copyright &y& Elsevier]

Abstract: In this paper, we show how to efficiently model check a subset of properties for the Time Petri Net model (TPN model), using the state class method. The verification proceeds by augmenting the TPN model under analysis with a special TPN, called Alarm-clock, to allow the capture of relevant time events. A forward on-the-fly exploration is then applied on the resulting TPN state class space to verify a timed property. A relaxation operation on state classes is also introduced to further improve performances. Alarm-clock is the same for all properties, whereas the exploration technique is not. Three exploration techniques are presented to cover most interesting TCTL properties. We prove the decidability of our verification technique for bounded TPN models and compare it with the reachability algorithm implemented in the tool UPPAAL [G. Behrmann, J. Bengtsson, A. David, K.G. Larsen, P. Pettersson, W. Yi, Uppaal implementation secrets, in: Proc. of the 7th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, 2002]. Finally, we give some experimental results to show the efficiency of our verification technique. [Copyright &y& Elsevier]

Abstract: Tarski’s fixed point theorem guarantees the existence of a fixed point of an order-preserving function defined on a nonempty complete lattice [B. Knaster, Un théorème sur les fonctions d’ensembles, Annales de la Société Polonaise de Mathématique 6 (1928) 133–134; A. Tarski, A lattice theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics 5 (1955) 285–309]. In this paper, we investigate several algorithmic and complexity-theoretic topics regarding Tarski’s fixed point theorem. In particular, we design an algorithm that finds a fixed point of when it is given as input and as an oracle. Our algorithm makes queries to when is a total order on . We also prove that when both and are given as oracles, any deterministic or randomized algorithm for finding a fixed point of makes an expected queries for some and . [Copyright &y& Elsevier]

This paper concerns construction of additive stretched spanners with few edges for -vertex graphs having a tree-decomposition into bags of diameter at most , i.e., the tree-length graphs. For such graphs we construct additive -spanners with edges, and additive -spanners with edges. This provides new upper bounds for chordal graphs for which . We also show a lower bound, and prove that there are graphs of tree-length for which every multiplicative -spanner (and thus every additive -spanner) requires edges. [Copyright &y& Elsevier]

Abstract: Given a sequence of real numbers and an integer parameter , the problem studied in this paper is to compute subsequences of consecutive elements with the sums of their elements being the largest, the second largest, …, and the th largest among all possible range sums of the input sequence. For any value of , , we design a fast algorithm that takes time in the worst case to compute and rank all such subsequences. We also prove that our algorithm is optimal for by providing a matching lower bound. Moreover, our algorithm is an improvement over the previous results on the maximum sum subsequences problem (where only the subsequences are requested and no ordering with respect to their relative sums will be determined). Furthermore, given the fact that we have computed the th largest sums, our algorithm retrieves the th largest sum in time, after time of preprocessing. [Copyright &y& Elsevier]

Abstract: There are various techniques for reconstructing phylogenetic trees from data, and in this context the problem of determining how distant two such trees are from each other arises naturally. Various metrics for measuring the distance between two phylogenies have been defined. Another way of comparing two trees and is to compute the so called maximum agreement forest of these trees. Informally, the number of components of an agreement forest tells how many edges from each of and need to be cut so that the resulting forests agree, after performing all forced edge contractions. This problem is -hard even when the input trees have maximum degree 2. Hein et al. [J. Hein, T. Jiang, L. Wang, K. Zhang, On the complexity of comparing evolutionary trees, Discrete Applied Mathematics 71 (1996) 153–169] presented an approximation algorithm for it, claimed to have performance ratio 3. We show that the performance ratio of the algorithm proposed by Hein et al. is 4, and we also present two new 3-approximation algorithms for this problem. We show how to modify one of the algorithms into a -approximation algorithm for trees with bounded degree , . Finally, we report on some computational experiments comparing the performance of the algorithms presented in this paper. [Copyright &y& Elsevier]

Abstract: In this paper, we give a numerical algorithm able to prove whether a set described by nonlinear inequalities is path-connected or not. To our knowledge, no other algorithm (numerical or symbolic) is able to deal with this type of problem. The proposed approach uses interval arithmetic to build a graph which has exactly the same number of connected components as . Examples illustrate the principle of the approach. [Copyright &y& Elsevier]

Abstract: Given a set of positive numbers, the max–min partition problem asks for a k-partition such that the minimum part is maximized. The min–ratio partition problem has the similar definition but the objective is to minimize the ratio of the maximum to the minimum parts. In this paper, we analyze the performances of the longest processing time (LPT) algorithm for the two problems. We show that the tight bounds of the LPT are, respectively and . [Copyright &y& Elsevier]

Many combinatorial structures can be constructed from simpler components. For example, a permutation can be constructed from cycles, or a Motzkin word from a Dyck word and a combination. In this paper we present a constructor for combinatorial structures, called shuffle on trajectories (defined previously in a non-combinatorial context), and we show how this constructor enables us to obtain a new loopless generating algorithm for multiset permutations from similar results for simpler objects. [Copyright &y& Elsevier]

Problems associated with finding strings that are within a specified Hamming distance of a given set of strings occur in several disciplines. In this paper, we use techniques from parameterized complexity to assess non-polynomial time algorithmic options and complexity for the COMMON APPROXIMATE SUBSTRING (CAS) problem. Our analyses indicate under which parameter restrictions useful algorithms are possible, and include both class membership and parameterized reductions to prove class hardness. In order to achieve fixed-parameter tractability, either a fixed string length or both a fixed size alphabet and fixed substring length are sufficient. Fixing either the string length or the alphabet size and Hamming distance is shown to be necessary, unless W[1]=FPT. An assortment of parameterized class membership and hardness results cover all other parameterized variants, showing in particular the effect of fixing the number of strings. [Copyright &y& Elsevier]

In this paper we introduce a parameterized generalization of the well known superimposed codes. We give algorithms for their construction and provide non-existential results. We apply our new combinatorial structures to the efficient solution of new group testing problems and access coordination issues in multiple access channels. [Copyright &y& Elsevier]