Acyclic chromatic index of planar graphs with triangles

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by , is the least number of colors in an acyclic edge coloring of G. Let G be a planar graph with maximum degree Δ(G). In this paper, we show that , if G contains no 4-cycle; , if G contains no intersecting triangles; and if G contains no adjacent triangles.     

Sensitivity versus block sensitivity of Boolean functions

Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with . The best known separation previously was due to Rubinstein. We also report results of computer search for functions with at most 13 variables.     

Pentagons: A weakly relational abstract domain for the efficient validation of array accesses

We introduce Pentagons (), a weakly relational numerical abstract domain useful for the validation of array accesses in byte-code and intermediate languages (IL). This abstract domain captures properties of the form of . It is more precise than the well known Interval domain, but it is less precise than the Octagon domain.The goal of is to be a lightweight numerical domain useful for adaptive static analysis, where is used to quickly prove the safety of most array accesses, restricting the use of more precise (but also more expensive) domains to only a small fraction of the code.We implemented the abstract domain in , a generic abstract interpreter for.NET assemblies. Using it, we were able to validate 83% of array accesses in the core runtime library in a little bit more than 3 minutes.     

On generalized middle-level problem

Let be the subgraph of the hypercube Q_n induced by levels between k and n-k, where n?2k+1 is odd. The well-known middle-level conjecture asserts that is Hamiltonian for all k?1. We study this problem in for fixed k. It is known that and are Hamiltonian for all odd n?3. In this paper we prove that also is Hamiltonian for all odd n?5, and we conjecture that is Hamiltonian for every k?0 and every odd n?2k+1.     

The Kolmogorov Expression Complexity of Logics

The purpose of the paper is to propose a completely new notion of complexity of logics in finite-model theory. It is the Kolmogorov variant of the Vardi'sexpression complexity. We define it by considering the value of the Kolmogorov complexityC(L[]) of the infinite stringL[] of all truth values of sentences ofLin . The higher is this value, the more expressive is the logicLin . If is a class of finite models, then the value ofC(L[]) over all ∈ is a measure of expressive power ofLin . Unboundedness ofC(L[])−C(L′[]) for ∈ implies nonexistence of a recursive interpretation ofLinL′. A version of this statement with complexities modulo oracles implies the nonexistence of any interpretation ofLinL′. Thus the valuesC(L[]) modulo oracles constitute an invariant of the expressive power of logics over finite models, depending on their real (absolute) expressive power, and not on the syntax. We investigate our notion for fragments of the infinitary logic ^ω_∞ω: least fixed point logic (LFP) and partial fixed point logic (PFP). We prove a precise characterization of 0–1 laws for these logics in terms of a certain boundedness condition placed onC(L[]). We get an extension of the notion of a 0–1 law by imposing an upper bound on the value ofC(L[]) growing not too fast with cardinality of , which still implies inexpressibility results similar to those implied by 0–1 laws. We also discuss classes in whichC(PFP^k[]) is very high. It appears that then PFP or its simple extension can define all the PSPACE subsets of .     

On edge covering colorings of graphs

An edge covering coloring of a graph G is an edge-coloring of G such that each color appears at each vertex at least one time. The maximum integer k such that G has an edge covering coloring with k colors is called the edge covering chromatic index of G and denoted by . It is known that for any graph G with minimum degree δ(G), it holds that . Based on the subgraph of G induced by the vertices of minimum degree, we find a new sufficient condition for a graph G to satisfy . This result substantially extends a result of Wang et al. in 2006.     

Multi-degree reduction of Bézier curves using reparameterization

L₂-norms are often used in the multi-degree reduction problem of Bézier curves or surfaces. Conventional methods on curve cases are to minimize , where and are the given curve and the approximation curve, respectively. A much better solution is to minimize , where is the closest point to point , that produces a similar effect as that of the Hausdorff distance. This paper uses a piecewise linear function L(t) instead of t to approximate the function φ(t) for a constrained multi-degree reduction of Bézier curves. Numerical examples show that this new reparameterization-based method has a much better approximation effect under Hausdorff distance than those of previous methods.     

Estimation of Kendall’s tau from censored data

This paper considers the nonparametric estimation of Kendall’s tau for bivariate censored data. Under censoring, there have been some papers discussing the nonparametric estimation of Kendall’s tau, such as Wang and Wells (2000), Oakes (2008) and Lakhal et al. (2009). In this article, we consider an alternative approach to estimate Kendall’s tau. The main idea is to replace a censored event-time by a proper imputation. Thus, it induces three estimators, say , , and . We also apply the bootstrap method to estimate the variance of , and and to construct the corresponding confidence interval. Furthermore, we analyze two data sets by the suggested approach, and compare these practical estimators of Kendall’s tau in simulation studies.     

Learning of event-recording automata

In regular inference, a regular language is inferred from answers to a finite set of membership queries, each of which asks whether the language contains a certain word. One of the most well-known regular inference algorithms is the L^∗ algorithm due to Dana Angluin. However, there are almost no extensions of these algorithms to the setting of timed systems. We extend Angluin’s algorithm for on-line learning of regular languages to the setting of timed systems. Since timed automata can freely use an arbitrary number of clocks, we restrict our attention to systems that can be described by deterministic event-recording automata (DERAs). We present three algorithms, , and , for inference of DERAs. In and , we further restrict event-recording automata to be event-deterministic in the sense that each state has at most one outgoing transition per action; learning such an automaton becomes significantly more tractable. The algorithm builds on , by attempts to construct a smaller (in number of locations) automaton. Finally, is a learning algorithm for a full class of deterministic event-recording automata, which infers a so called simple DERA, which is similar in spirit to the region graph.     

On the average cost of order-preserving encryption based on hypergeometric distribution

Order-preserving encryption (OPE) is a deterministic encryption scheme whose encryption function preserves numerical ordering of the plaintexts. The first provably-secure OPE scheme was constructed by Boldyreva, Chenette, Lee, and O?Neill. The BCLO scheme is based on a sampling algorithm for the hypergeometric distribution and is known to call the sampling algorithm at most times on average where M is the size of the plaintext-space. We show that the BCLO scheme actually calls the sampling algorithm less than times on average.     

A hybrid token-based distributed mutual exclusion algorithm using wraparound two-dimensional array logical topology

In token-based distributed mutual exclusion algorithms a unique object (token) is used to grant the right to enter the critical section. For the movement of the token within the computer network, two possible methods can be considered: perpetual mobility of the token and token-asking method. This paper presents a distributed token-based algorithm scheduling mutually exclusive access to a critical resource by the processes in a distributed network. This network is composed of N nodes that communicate by message exchanges. The proposed hybrid algorithm imposes a logical structure in the form of wraparound two-dimensional array on the network. It applies the concept of perpetual mobility of the token in columns and token-asking in rows of the array. The major purpose of the algorithm is to increase the scalability property and decrease overhead due to additional communication in a system with at least one unresponded critical section request at any given time. In this status, typically, the number of message exchanges is between and under light demand and reduces to message exchanges under heavy demand. Therefore, it outperforms lots of well known algorithms in terms of number of messages exchanged. The algorithm satisfies safety and liveness properties.     

Finding frequent items over sliding windows with constant update time

In this paper, we consider the problem of finding ?-approximate frequent items over a sliding window of size N. A recent work by Lee and Ting (2006) [7] solves the problem by giving an algorithm that supports query and update time, and uses space. Their query time and memory usage are essentially optimal, but the update time is not. We give a new algorithm that supports O(1) update time with high probability while maintaining the query time and memory usage as .     

Convex invariant sets for discrete-time Lur’e systems

In this paper, a method to estimate the domain of attraction of a class of discrete-time Lur’e systems is presented. A new notion of invariance, denoted -invariance, is introduced. An algorithm to determinate the largest -invariant set for this class of systems is proposed. Moreover, it is proven that the -invariant sets provided by this algorithm are polyhedral convex sets and constitute an estimation of the domain of attraction of the non-linear system. It is shown that any contractive set for the Lur’e system is contained in the -invariant set obtained applying the results of this paper. Two illustrative examples are given.     

A compact data structure for representing a dynamic multiset

We develop a data structure for maintaining a dynamic multiset that uses bits and O(1) words, in addition to the space required by the n elements stored, supports searches in worst-case time and updates in amortized time. Compared to earlier data structures, we improve the space requirements from O(n) bits to bits, but the running time of updates is amortized, not worst-case.     

The size and depth of layered Boolean circuits

We consider the relationship between size and depth for layered Boolean circuits and synchronous circuits. We show that every layered Boolean circuit of size s can be simulated by a layered Boolean circuit of depth . For synchronous circuits of size s, we obtain simulations of depth . The best known result so far was by Paterson and Valiant (1976) [17], and Dymond and Tompa (1985) [6], which holds for general Boolean circuits and states that , where C(f) and D(f) are the minimum size and depth, respectively, of Boolean circuits computing f. The proof of our main result uses an adaptive strategy based on the two-person pebble game introduced by Dymond and Tompa (1985) [6]. Improving any of our results by polylog factors would immediately improve the bounds for general circuits.     

How strong is Nisan?s pseudo-random generator?

We study the resilience of the classical pseudo-random generator (PRG) of Nisan (1992) [6] against space-bounded machines that make multiple passes over the input. Nisan?s PRG is known to fool log-space machines that read the input once. We ask what are the limits of this PRG regarding log-space machines that make multiple passes over the input. We show that for every constant k Nisan?s PRG fools log-space machines that make passes over the input, using a seed of length , for some k^′>k. We complement this result by showing that in general Nisan?s PRG cannot fool log-space machines that make nO(1) passes even for a seed of length . The observations made in this note outline a more general approach in understanding the difficulty of derandomizing BPNC¹.     

Upper bound for algebraic immunity on a subclass of Maiorana McFarland class of bent functions

Studying algebraic immunity of Boolean functions is recently a very important research topic in cryptography. It is recently proved by Courtois and Meier that for any Boolean function of n-variable the maximum algebraic immunity is . We found a large subclass of Maiorana McFarland bent functions on n-variable with a proven low level of algebraic immunity . To the best of our knowledge we provide for the first time a new upper bound for algebraic immunity for a nontrivial class of Boolean functions. We also discuss that this result has some fascinating implications.