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.     

An improved lower bound on query complexity for quantum PAC learning

In this paper, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. For a concept class with VC dimension d, the lower bound is for ? accuracy and 1−δ confidence, where e can be an arbitrarily small positive number. The lower bound is very close to the best lower bound known on query complexity for the classical PAC learning model, which is .     

Invariance properties in the root sensitivity of time-delay systems with double imaginary roots

If is an eigenvalue of a time-delay system for the delay τ₀ then is also an eigenvalue for the delays τ_k?τ₀+k2π/ω, for any k∈Z. We investigate the sensitivity, periodicity and invariance properties of the root for the case that is a double eigenvalue for some τ_k. It turns out that under natural conditions (the condition that the root exhibits the completely regular splitting property if the delay is perturbed), the presence of a double imaginary root for some delay τ₀ implies that is a simple root for the other delays τ_k, k≠0. Moreover, we show how to characterize the root locus around . The entire local root locus picture can be completely determined from the square root splitting of the double root. We separate the general picture into two cases depending on the sign of a single scalar constant; the imaginary part of the first coefficient in the square root expansion of the double eigenvalue.     

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.     

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.     

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 2-dipath chromatic number of Halin graphs

A 2-dipath k-coloring f of an oriented graph is a mapping from to the color set {1,2,…,k} such that f(x)≠f(y) whenever two vertices x and y are linked by a directed path of length 1 or 2. The 2-dipath chromatic number of is the smallest k such that has a 2-dipath k-coloring. In this paper we prove that if is an oriented Halin graph, then . There exist infinitely many oriented Halin graphs such that .     

Decomposition of sparse graphs into two forests, one having bounded maximum degree

Let G be a graph. The maximum average degree of G, written Mad(G), is the largest average degree among the subgraphs of G. It was proved in Montassier et al. (2010) [11] that, for any integer k?0, every simple graph with maximum average degree less than admits an edge-partition into a forest and a subgraph with maximum degree at most k; furthermore, when k?3 both subgraphs can be required to be forests. In this note, we extend this result proving that, for k=4,5, every simple graph with maximum average degree less than mk admits an edge-partition into two forests, one having maximum degree at most k (i.e. every graph with maximum average degree less than (resp. ) admits an edge-partition into two forests, one having maximum degree at most 4 (resp. 5)).     

Spectral radius minimization for optimal average consensus and output feedback stabilization

In this paper, we consider two problems which can be posed as spectral radius minimization problems. Firstly, we consider the fastest average agreement problem on multi-agent networks adopting a linear information exchange protocol. Mathematically, this problem can be cast as finding an optimal such that x(k+1)=Wx(k), , and W∈S(E). Here, is the value possessed by the agents at the kth time step, is an all-one vector and S(E) is the set of real matrices in with zeros at the same positions specified by a network graph G(V,E), where V is the set of agents and E is the set of communication links between agents. The optimal W is such that the spectral radius is minimized. To this end, we consider two numerical solution schemes: one using the qth-order spectral norm (2-norm) minimization (q-SNM) and the other gradient sampling (GS), inspired by the methods proposed in [Burke, J., Lewis, A., & Overton, M. (2002). Two numerical methods for optimizing matrix stability. Linear Algebra and its Applications, 351-352, 117-145; Xiao, L., & Boyd, S. (2004). Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1), 65-78]. In this context, we theoretically show that when E is symmetric, i.e. no information flow from the ith to the jth agent implies no information flow from the jth to the ith agent, the solution from the 1-SNM method can be chosen to be symmetric and is a local minimum of the function . Numerically, we show that the q-SNM method performs much better than the GS method when E is not symmetric. Secondly, we consider the famous static output feedback stabilization problem, which is considered to be a hard problem (some think NP-hard): for a given linear system (A,B,C), find a stabilizing control gain K such that all the real parts of the eigenvalues of A+BKC are strictly negative. In spite of its computational complexity, we show numerically that q-SNM successfully yields stabilizing controllers for several benchmark problems with little effort.     

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 .     

Model selection with the Loss Rank Principle

A key issue in statistics and machine learning is to automatically select the “right” model complexity, e.g., the number of neighbors to be averaged over in k nearest neighbor () regression or the polynomial degree in regression with polynomials. We suggest a novel principle-the Loss Rank Principle (LoRP)-for model selection in regression and classification. It is based on the loss rank, which counts how many other (fictitious) data would be fitted better. LoRP selects the model that has minimal loss rank. Unlike most penalized maximum likelihood variants (AIC, BIC, MDL), LoRP depends only on the regression functions and the loss function. It works without a stochastic noise model, and is directly applicable to any non-parametric regressor, like .     

A Flexible Approach to Bayesian Multiple Curve Fitting

We model sparse functional data from multiple subjects with a mixed-effects regression spline. In this model, the expected values for any subject (conditioned on the random effects) can be written as the sum of a population curve and a subject-specific deviate from this population curve. The population curve and the subject-specific deviates are both modeled as free-knot b-splines with k and k^′ knots located at and , respectively. To identify the number and location of the “free” knots, we sample from the posterior using reversible jump MCMC methods. Sampling from this posterior distribution is complicated, however, by the flexibility we allow for the model’s covariance structure. No restrictions (other than positive definiteness) are placed on the covariance parameters ψ and σ² and, as a result, no analytical form for the likelihood exists. In this paper, we consider two approximations to and then sample from the corresponding approximations to . We also sample from which has a likelihood that is available in closed form. While sampling from this larger posterior is less efficient, the resulting marginal distribution of knots is exact and allows us to evaluate the accuracy of each approximation. We then consider a real data set and explore the difference between and the more accurate approximation to .     

On special families of morphisms related to δ-matching and don't care symbols

The δ-matching problem is a special version of approximate pattern-matching, motivated by applications in musical information retrieval, where the alphabet Σ is an interval of integers. We investigate relations between δ-matching and pattern-matching with don't care symbol ∗ (a symbol matching every symbol, including itself). We show that the δ-matching is reducible to k instances of pattern-matching with don't cares. We investigate how the numbers δ and k are related by introducing δ-distinguishing families of morphisms. The size of corresponds to k. We show that for minimal families we have .     

Kendall distributions and level sets in bivariate exchangeable survival models

For a given bivariate survival function , we study the relations between the set of the level curves of and the Kendall distribution. Then we characterize the survival models simultaneously admitting a specified Kendall distribution and a specified set of level curves. Attention will be restricted to exchangeable survival models.     

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.     

The approximate swap and mismatch edit distance

There is no known algorithm that solves the general case of the approximate edit distance problem, where the edit operations are insertion, deletion, mismatch, and swap, in time o(nm), where n is the length of the text and m is the length of the pattern.In the effort to study this problem, the edit operations have been analyzed independently. Karloff [10] showed an algorithm that approximates the edit distance problem with only the mismatch operation in time . Amir et al. [4] showed that if the only edit operations allowed are swap and mismatch, then the exact edit distance problem can be solved in time .In this paper, we discuss the problem of approximate edit distance with swap and mismatch. We show a randomized time algorithm for the problem. The algorithm guarantees an approximation factor of (1+?) with probability of at least .