Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity

A square matrix V is called rigid if every matrix \({V^\prime}\) obtained by altering a small number of entries of V has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major implications in computational complexity theory. One approach to establishing rigidity of a matrix V is to come up with a property that is satisfied by any collection of vectors arising from a low-dimensional space, but is not satisfied by the rows of V even after alterations. In this paper, we propose such a candidate property that has the potential of establishing rigidity of combinatorial design matrices over the field \({\mathbb{F}_2.}\) Stated informally, we conjecture that under a suitable embedding of \({\mathbb{F}_2^n}\) into \({\mathbb{R}^n,}\) vectors arising from a low-dimensional \({\mathbb{F}_2}\)-linear space always have somewhat small Kolmogorov width, i.e., admit a non-trivial simultaneous approximation by a low-dimensional Euclidean space. This implies rigidity of combinatorial designs, as their rows do not admit such an approximation even after alterations. Our main technical contribution is a collection of results establishing weaker forms and special cases of the conjecture above.     

Profile miniaturization and performance improvement of a rectangular patch antenna using magnetic metamaterial substrates

The idea of profile miniaturization and performance improvement of a rectangular patch antenna using a metamaterial substrate with large values in the real part of effective relative permeability is proposed in microwave frequency range. The volume profile of the antenna is minimized by tuning the effective relative permeability and thickness of the substrate material. The specific type of metamaterial which can be used as substrate material for the antenna miniaturization purpose is suggested. The proposed idea is validated through finite‐difference time‐domain (FDTD) simulations for sample rectangular patch antennas with metamaterial substrates at the frequency about 10 GHz. Improvement of the power directivity is found for the metamaterial substrate with large value in the real part of effective permeability. © 2016 Wiley Periodicals, Inc. Int J RF and Microwave CAE 26:254–261, 2016.     

Investigation of the structure of supersonic nitrogen microjets

Results of research on microjets escaping into an ambient space from nozzles with diameters of 341–10.4 μm are described. A special Pitot microtube is used for studying the structure of supersonic microjets. The main feature of this microtube is a small diameter of the intake hole (12 μm). The main parameters of supersonic underexpanded microjets are identified, including the size of shock cells and the supersonic core length of the microjet. The results show a significant increase in the supersonic core length of microjets compared to macrojets. The Reynolds numbers of the laminar–turbulent transition in microjets are found to be in the range of 1,100–2,100. In addition, a classification of supersonic underexpanded axisymmetric microjets escaping into the ambient space is proposed.     

A Polynomial Time Solution to Minimum Forwarding Set Problem in Wireless Networks under Unit Disk Coverage Model

Network-wide broadcast (simply broadcast) is a frequently used operation in wireless ad hoc networks (WANETs). One promising practical approach for energy-efficient broadcast is to use localized algorithms to minimize the number of nodes involved in the propagation of the broadcast messages. In this context, the minimum forwarding set problem (MFSP) (also known as multipoint relay (MPR) problem) has received a considerable attention in the research community. Even though the general form of the problem is shown to be NP-complete, the complexity of the problem has not been known under the practical application context of ad hoc networks. In this paper, we present a polynomial time algorithm to solve the MFSP for wireless network under unit disk coverage model. We prove the existence of some geometrical properties for the problem and then propose a polynomial time algorithm to build an optimal solution based on these properties. To the best of our knowledge, our algorithm is the first polynomial time solution to the MFSP under the unit disk coverage model. We believe that the work presented in this paper will have an impact on the design and development of new algorithms for several wireless network applications including energy-efficient multicast, broadcast, and topology control protocols for WANETs and sensor networks.     

Aeroelastic stability of heated functionally graded cylindrical shells containing fluid

The article is concerned with the analysis of panel flutter of heated circular clamped cylindrical shells made of functionally graded (FG) material, which are subject to a simultaneous action of the external supersonic gas flow and the internal flow of ideal compressible fluid. The effective properties of the material change throughout the thickness of the shell according to a power law and depend on temperature. The aerodynamic pressure is calculated based on the quasi-static aerodynamic theory. The behavior of the fluid is described in the framework of the potential theory. A mathematical formulation of the dynamic problem for elastic structure is developed based on the classical theory of shells and the principle of virtual displacements. Based on the results of numerical simulation the influence of different consistencies of the examined FG materials, thermal load, and internal flow velocity on the boundary of aeroelastic stability is analyzed.     

Microstructure,Phase Composition,and Thermal Stability of Two Zirconium Alloys Subjected to High‐Pressure Torsion at Different Temperatures

The structure, phase composition, and thermal stability of the industrial zirconium alloys, namely, E110 (Zr–1% Nb) and E635 (Zr–1% Nb–0.3% Fe–1.2% Sn), which are subjected to high‐pressure torsion (HPT) at room temperature (RT), 200, and 400 °С have been studied. HPT of Zr‐alloys at RT (10 revolutions) leads to the formation of grain–subgrain nano‐sized structure and to increase the microhardness by 2.1…2.8 times. The increase in the HPT temperature to 200–400 °С leads to the increase in the structural‐element average size. The structural‐element size in the complexly alloyed E635 alloy in all cases is lower compared with the E110 alloy. The hardening of the alloys after HPT at RT and 200 °С is close, and at 400 °С is much less. HPT initiates the α‐Zr → (ω‐Zr + β‐Zr) transformation, which is the main factor for alloys hardening. The α‐Zr → (ω‐Zr + β‐Zr) transformation in the E635 alloy occurs less quickly. The maximum amount (ω‐Zr + β‐Zr) phase in the structure of the alloys is observed after HPT at RT and 200 °C, and the minimum ? at 400 °C. During heating, the alloys undergo the reverse (ω‐Zr + β‐Zr) → α transformation which depends on both the alloy composition and HPT temperature.

     

Beyond Market Baskets: Generalizing Association Rules to Dependence Rules

One of the more well-studied problems in data mining is the search for association rules in market basket data. Association rules are intended to identify patterns of the type: A customer purchasing item A often also purchases item B. Motivated partly by the goal of generalizing beyond market basket data and partly by the goal of ironing out some problems in the definition of association rules, we develop the notion of dependence rules that identify statistical dependence in both the presence and absence of items in itemsets. We propose measuring significance of dependence via the chi-squared test for independence from classical statistics. This leads to a measure that is upward-closed in the itemset lattice, enabling us to reduce the mining problem to the search for a border between dependent and independent itemsets in the lattice. We develop pruning strategies based on the closure property and thereby devise an efficient algorithm for discovering dependence rules. We demonstrate our algorithm's effectiveness by testing it on census data, text data (wherein we seek term dependence), and synthetic data.     

Stabilization and tracking in the nonholonomic integrator via sliding modes

In this paper we use an approach based on sliding mode control to design a feedback which stabilizes the origin for the so-called nonholonomic integrator or Heisenberg system, a particular case of a canonical class of nonlinear driftless control systems of the form

which fail Brockett's necessary condition for the existence of a smooth stabilizing feedback.     

Local ISS of large-scale interconnections and estimates for stability regions

We consider interconnections of locally input-to-state stable (LISS) systems. The class of LISS systems is quite large, in particular it contains input-to-state stable (ISS) and integral input-to-state stable (iISS) systems.Local small-gain conditions both for LISS trajectory and Lyapunov formulations guaranteeing LISS of the composite system are provided in this paper. Notably, estimates for the resulting stability region of the composite system are also given. This in particular provides an advantage over the linearization approach, as will be discussed.     

A generic complete dynamic logic for reasoning about purity and effects

For a number of programming languages, among them Eiffel, C, Java, and Ruby, Hoare-style logics and dynamic logics have been developed. In these logics, pre- and postconditions are typically formulated using potentially effectful programs. In order to ensure that these pre- and postconditions behave like logical formulae (that is, enjoy some kind of referential transparency), a notion of purity is needed. Here, we introduce a generic framework for reasoning about purity and effects. Effects are modelled abstractly and axiomatically, using Moggi’s idea of encapsulation of effects as monads. We introduce a dynamic logic (from which, as usual, a Hoare logic can be derived) whose logical formulae are pure programs in a strong sense. We formulate a set of proof rules for this logic, and prove it to be complete with respect to a categorical semantics. Using dynamic logic, we then develop a relaxed notion of purity which allows for observationally neutral effects such writing on newly allocated memory.