A permuted factors approach for the linearization of polynomial matrices

In Antoniou and Vologiannidis (Electron J Linear Algebra 11:78–87, 2004; 15:107–114, 2006), a new family of companion forms associated with a regular polynomial matrix T (s) has been presented, using products of permutations of n elementary matrices, generalizing similar results presented in Fiedler (Linear Algebra Its Appl 371:325–331, 2003) where the scalar case was considered. In this paper, extending this “permuted factors” approach, we present a broader family of companion-like linearizations, using products of up to n(n−1)/2 elementary matrices, where n is the degree of the polynomial matrix. Under given conditions, the proposed linearizations can be shown to consist of block entries where the coefficients of the polynomial matrix appear intact. Additionally, we provide a criterion for those linearizations to be block symmetric. We also illustrate several new block symmetric linearizations of the original polynomial matrix T (s), where in some of them the constraint of nonsingularity of the constant term and the coefficient of maximum degree are not a prerequisite.     

Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling ℒ _all gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling ℒ _up labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted M _up (T) and S _up (T) for ℒ _up and M _all (T) and S _all (T) for ℒ _all . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,…,deg (v)−1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for M _up (T), S _up (T) and S _all (T) but NP-hard for M _all (T) (even for 3-regular planar graphs). We show that for every graph G and port labeling there exists a spanning tree T for which S _up (T)=O(nlog log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port labeling. We conclude by discussing some applications for our tree representation schemes. A preliminary version of this paper has appeared in the proceedings of the 7th International Workshop on Distributed Computing (IWDC), Kharagpur, India, December 27–30, 2005, as part of Cohen, R. et al.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lecture Notes of Computer Science, vol. 3741, pp. 13–24 (2005). R. Cohen supported by the Pacific Theaters Foundation. P. Fraigniaud and D. Ilcinkas supported by the project “PairAPair” of the ACI Masses de Données, the project “Fragile” of the ACI Sécurité et Informatique, and by the project “Grand Large” of INRIA. A. Korman supported in part by an Aly Kaufman fellowship. D. Peleg supported in part by a grant from the Israel Science Foundation.     

Rotationally Invariant Multipartite States

We construct a class of multipartite states possessing rotational SO(3) symmetry – these are states of K spin-j _A particles and K spin-j _B particles. The construction of symmetric states follows our two recent papers devoted to unitary and orthogonal multipartite symmetry. We study basic properties of multipartite SO(3) symmetric states: separability criteria and multi-PPT conditions. Presented at the 38th Symposium on Mathematical Physics “Quantum Entanglement & Geometry”, Toruń, June 4–7, 2006.     

A general scheme for formalizing defaults using the predicateab(I, S)

In common sense reasoning two typical types of defaults are encountered.One is of the form “all birds can fly excepts b1,b2,…,and bm(m≥1)”,and the other “All birds can fly,but there exist exceptions”.The type of defaults is readily formalized but the other,as some researchers have noticad,is difficult to deal with.This paper establishes a general scheme for formalizing defaults of the two types,the key to which is the introduction of a two-argument predicate ab(I,S) to represent exceptional objects.     

Lower Bounds for Kernelizations and Other Preprocessing Procedures

We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P≠NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563–574, Springer, Berlin, 2008; Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), ACM, New York, pp. 133–142, 2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a “linear OR” and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with |y|=k ^O(1)⋅|x|^1−ε (here ε is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of preprocessing procedures, namely the various notions of kernelizations, self-reductions and compressions.     

A study of orthogonal,balanced and symmetric multi-wavelets on the interval

1 Introduction Wavelet on the real axis has been applied in a great deal of fields. However, in many practical applications, people are often interested in the problems which are limited in a finite region K, such as the differential equation solving, image processing and so on. The approximate space L2(R) does not match the signal space L2(K) if we use L2(R) wavelet to solve these problems. “Border effect” is arising [1,2] and the results are not so good. From the viewpoint of approxima…     

Connecting Polygonizations via Stretches and Twangs

We show that the space of polygonizations of a fixed planar point set S of n points is connected by O(n ²) “moves” between simple polygons. Each move is composed of a sequence of atomic moves called “stretches” and “twangs,” which walk between weakly simple “polygonal wraps” of S. These moves show promise to serve as a basis for generating random polygons.     

Simultaneous cognitive origin of life and information

Shannon’s information quantity I(E) = log(1/P(E)) is defined under an assumption of the existence of a “cognitive subjective entity” capable of judging yes/no or occurred/not-occurred of an event E (which occurs with a probability P(E)). The final acceptor/user of information is a living individual, although first and/or intermediate sender(s) and/or acceptor(s) of information may be either living individual(s) or nonliving element(s) or man-made machine(s). Therefore we can conclude that information is a most essential character of living individuals, and that information and life must have emerged simultaneously as a “minimum cognitive system” (MCS). Since then, living individuals/lives must have evolved as “self-revising learning neural network machines” capable of “active evolution”. How MCS could have emerged was discussed.     

Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure

In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves O(n ²) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Ω(n ²) entries of this matrix, no better bounds are possible for this class of algorithms. This work has been partially supported by the Sixth Framework Programme of the EU under contract number 507613 (Network of Excellence “EuroNGI: Designing and Engineering of the Next Generation Internet”), and number 001907 (“DELIS: Dynamically Evolving, Large Scale Information Systems”), and by the Italian Ministry of University and Research (Project “ALGO-NEXT: Algorithms for the Next Generation Internet and Web: Methodologies, Design and Experiments”). Portions of this paper have been presented at the 41st Annual Symp. on Foundations of Computer Science, 2000.     

A Fourth Order Hermitian Box-Scheme with Fast Solver for the Poisson Problem in a Square

A new fourth order box-scheme for the Poisson problem in a square with Dirichlet boundary conditions is introduced, extending the approach in Croisille (Computing 78:329–353, 2006). The design is based on a “hermitian box” approach, combining the approximation of the gradient by the fourth order hermitian derivative, with a conservative discrete formulation on boxes of length 2h. The goal is twofold: first to show that fourth order accuracy is obtained both for the unknown and the gradient; second, to describe a fast direct algorithm, based on the Sherman-Morrison formula and the Fast Sine Transform. Several numerical results in a square are given, indicating an asymptotic O(N ²log ₂(N)) computing complexity.     

The Method of Levels of Abstraction

The use of “levels of abstraction” in philosophical analysis (levelism) has recently come under attack. In this paper, I argue that a refined version of epistemological levelism should be retained as a fundamental method, called the method of levels of abstraction. After a brief introduction, in section “Some Definitions and Preliminary Examples” the nature and applicability of the epistemological method of levels of abstraction is clarified. In section “A Classic Application of the Method of Abstraction”, the philosophical fruitfulness of the new method is shown by using Kant’s classic discussion of the “antinomies of pure reason” as an example. In section “The Philosophy of the Method of Abstraction”, the method is further specified and supported by distinguishing it from three other forms of “levelism”: (i) levels of organisation; (ii) levels of explanation and (iii) conceptual schemes. In that context, the problems of relativism and antirealism are also briefly addressed. The conclusion discusses some of the work that lies ahead, two potential limitations of the method and some results that have already been obtained by applying the method to some long-standing philosophical problems.

Relations between Average-Case and Worst-Case Complexity

The consequences of the worst-case assumption NP=P are very well understood. On the other hand, we only know a few consequences of the analogous average-case assumption “NP is easy on average.” In this paper we establish several new results on the worst-case complexity of Arthur-Merlin games (the class AM) under the average-case complexity assumption “NP is easy on average.”

Weak Derandomization of Weak Algorithms: Explicit Versions of Yao��s Lemma

A simple averaging argument shows that given a randomized algorithm A and a function f such that for every input x, Pr[A(x) = f(x)] ≥ 1 − ρ (where the probability is over the coin tosses of A), there exists a non-uniform deterministic algorithm B “of roughly the same complexity” such that Pr[B(x) = f(x)] ≥ 1 − ρ (where the probability is over a uniformly chosen input x). This implication is often referred to as “the easy direction of Yao’s lemma” and can be thought of as “weak derandomization” in the sense that B is deterministic but only succeeds on most inputs. The implication follows as there exists a fixed value r′ for the random coins of A such that “hardwiring r′ into A” produces a deterministic algorithm B. However, this argument does not give a way to explicitly construct B.     

Zero-Automatic Networks

We continue the study of zero-automatic queues first introduced in Dao-Thi and Mairesse (Adv Appl Probab 39(2):429–461, 2007). These queues are characterized by a special buffering mechanism evolving like a random walk on some infinite group or monoid. The simple M/M/1 queue and Gelenbe’s G-queue with positive and negative customers are the two simplest 0-automatic queues. All stable 0-automatic queues have an explicit “multiplicative” stationary distribution and a Poisson departure process (Dao-Thi and Mairesse, Adv Appl Probab 39(2):429–461, 2007). In this paper, we introduce and study networks of 0-automatic queues. We consider two types of networks, with either a Jackson-like or a Kelly-like routing mechanism. In both cases, and under the stability condition, we prove that the stationary distribution of the buffer contents has a “product-form” and can be explicitly determined. Furthermore, the departure process out of the network is Poisson.

Expressing uniformity via oracles

We study under what circumstances different uniformity notions for Boolean circuits of logarithmic depth lead to the same complexity class. Our investigations are based on a characterization of uniformity in terms of oracle access to tally sets that is proved in the present paper:A-uniform circuits of logarithmic depth are of the same computational power asDLOGTIME-uniform circuits of logarithmic depth with oracle access to tally sets inA. This characterization does not only apply to classesA such as logarithmic space or polynomial time, but to all in some sense “well-behaved” classes and especially to all standard complexity classes. We present many applications for this characterization, among them upward separations, depth-uniformity tradeoffs, and inclusion-completeness results for tally languages. The first two authors were partially supported by DFG-La 618/1-1 and the third author was supported by DFG-SFB 0342 “KLARA.”     

Tree Expressions for Information Systems

The discernibility matrix is one of the most important approaches to computing positive region, reduct, core and value reduct in rough sets. The subject of this paper is to develop a parallel approach of it, called ＂tree expression＂. Its computational complexity for positive region and reduct is O（m^2 × n） instead of O（m × n^2） in discernibility-matrix-based approach, and is not over O（n^2） for other concepts in rough sets, where rn and n are the numbers of attributes and objects respectively in a given dataset （also called an ＂information system＂ in rough sets）. This approach suits information systems with n ≥ m and containing over one million objects.     

Efficient design/simulation algorithms for simultaneous switching noise in leadframe packages

 Two new modeling and simulation approaches for Simultaneous Switching Noise (SSN) are described and compared to “brute force” simulation by SPICE. Both simulation accuracy and simulation run-time are considered. The two new approaches are: 1) the “effective inductance” method, in which an approximate, very efficient method of extracting an SSN L _eff  is utilized; and 2) the “macromodel” method, in which the complex inductance network responsible for SSN is represented by only a few dominant poles in the frequency domain and the time domain response is obtained by an efficient convolution algorithm. Both approaches are shown to be accurate and fast, but only the effective inductance algorithm is robust in numerical convergence. Received: 19 March 1997 / Accepted: 25 March 1997     

Design of nonlinear controllers for active vehicle suspension with state constraints

Design of active vehicle suspension has tradeoffs between three main performance metrics (passenger comfort, suspension deflection and road holding ability). It has been known that each performance can be achieved by H _∞ controller and they can be gathered by LPV (Linear Parameter Varying) method. However, because the suspension deflection limit was not explicitly considered, this limit may be exceeded. In this paper, the authors propose a “reference shaping“ based method in order to improve the control performance. In this approach, a “virtual reference” signal is imposed to the system such that the suspension deflection is kept small. The effectiveness of the approach is examined by numerical simulations. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008