Time evolving meteorological variables of daily observations from multiple sources can be represented as simple 3-node tensors. Powerful analytic tools such as canonical polyadic (cp) tensor decomposition are available to factor streaming tensors into tensor approximations associated with dominant components. We show the potential of tensor decomposition for meteorological analysis by presenting multi-year experiments for inferring Planetary Boundary Layer Heights (PBLH) by employing cp tensor decomposition analytics applied to streaming ceilometer base Lidar data sets. The experiment compares the PBLH obtained from the 3 nodes tensor consisting of 5 minutes streams of hourly Lidar based aerosol backscatter profiles each day from 3 distinctly located ceilometers distributed along the East coast for a 1.5 years period from May 7, 2021-June 30, 2022. We compare the PBLH derived from the ceilometers with those inferred from a WRF model simulation for the same period with two nested intervals over the CONUS at 2 deg. and 0.9 deg., interpolated to the same locations as the ceilometers. The WRF model integration is forced by the interpolated hourly NOAA GFS reanalysis data set and annual averaged aerosols distributions specified geographically over the CONUS grid. We present graphs of the time dependence of the dominant tensor components of PBLH as well as the error of the dominant tensors for various assumptions of tensor rank. These dominant components show the correlations of PBLH over 24 hours over multiple regions.

COVID-19 is an air-borne viral infection, which infects the respiratory system in the human body, and it became a global pandemic in early March 2020. The damage caused by the COVID-19 disease in a human lung region can be identified using Computed Tomography (CT) scans. We present a novel approach in classifying COVID-19 infection and normal patients using a Random Forest (RF) model to train on a combination of Deep Learning (DL) features and Radiomic texture features extracted from CT scans of patient’s lungs. We developed and trained DL models using CNN architectures for extracting DL features. The Radiomic texture features are calculated using CT scans and its associated infection masks. In this work, we claim that the RFs classification using the DL features in conjunction with Radiomic texture features enhances prediction performance. The experiment results show that our proposed models achieve a higher True Positive rate with the average Area Under the Receiver Curve (AUC) of 0.9768, 95% Confidence Interval (CI) [0.9757, 0.9780].

COVID-19 is a novel infectious disease responsible for over 1.2 million deaths worldwide as of November 2020. The need for rapid testing is a high priority and alternative testing strategies including x-ray image classification are a promising area of research. However, at present, public datasets for COVID-19 x-ray images have low data volumes, making it challenging to develop accurate image classifiers. Several recent papers have made use of Generative Adversarial Networks (GANs) in order to increase the training data volumes. But realistic synthetic COVID-19 x-rays remain challenging to generate. We present a novel Mean Teacher + Transfer GAN (MTT-GAN) that generates COVID-19 chest x-ray images of high quality. In order to create a more accurate GAN, we employ transfer learning from the Kaggle pneumonia x-ray dataset, a highly relevant data source orders of magnitude larger than public COVID-19 datasets. Furthermore, we employ the Mean Teacher algorithm as a constraint to improve stability of training. Our qualitative analysis shows that the MTT-GAN generates x-ray images that are greatly superior to a baseline GAN and visually comparable to real x-rays. Although board-certified radiologists can distinguish MTT-GAN fakes from real COVID-19 x-rays, quantitative analysis shows that MTT-GAN greatly improves the accuracy of both a binary COVID-19 classifier as well as a multi-class pneumonia classifier as compared to a baseline GAN. Our classification accuracy is favorable as compared to recently reported results in the literature for similar binary and multi-class COVID-19 screening tasks.

Exposure of sensitive information can be harmful on its own. In addition, it could enable further attacks. A rigorous and unambiguous definition of information exposure faults can help researchers and practitioners identify them, thus avoiding security failures. This paper describes Information Exposure (IEX), a new class in the Bugs Framework (BF). The IEX class comprises a rigorous definition and (static) attributes of the class, along with their related dynamic properties, such as proximate and secondary causes, consequences and sites. We use the IEX class to analyze specific vulnerabilities and provide clear descriptions. We also discuss lessons we learned that will help create additional BF classes.

Random number generators may have weaknesses (bugs) and the applications using them may become vulnerable to attacks. Formalization of randomness bugs would help researchers and practitioners identify them and avoid security failures. The Bugs Framework (BF) comprises rigorous definitions and (static) attributes of bug classes, along with their related dynamic properties, such as proximate and secondary causes, consequences and sites. This paper presents two new BF classes: True-Random Number Bugs (TRN) and Pseudo-Random Number Bugs (PRN). We analyze particular vulnerabilities and use these classes to provide clear BF descriptions. Finally, we discuss the lessons learned towards creating new BF class.

Machine learning and graph analytics typically process data in an iterative way, reading the same data multiple times and sharing intermediate results across the worker nodes in cluster. Hadoop MapReduce and Spark are two popular open source cluster compute frameworks for large scale data analytics. Apache Spark is currently the state-of-the-art in-memory computation model extending MapReduce by transforming data into RDDs stored in memory. One limitation of Spark, however, lies in the fact that data transformation and distribution is implicitly managed by HDFS. Data locality is not guaranteed for iterative machine learning algorithms which read the same data multiple times. For example, data needed for operations to one worker node might reside in RDDs stored in other worker nodes. The resulting data shuffling becomes a bottleneck when iteratively reading such RDDs. We propose YinMem, a parallel distributed indexed in-memory computation system, bridging the gap between Hadoop ecosystem and HPC by replacing MapReduce with MPI while obtaining the advantage of the distributed data storage. YinMem achieves fair load balancing prior to computation for large sparse matrix by scheduling and distributing indexed data from NoSQL database to the RAM of working nodes. YinMem explores Alluxio as the in-memory storage system and enables efficient data sharing of intermediate results. Preliminary results show that YinMem has achieved 3× speedup to Spark, for computing eigenvalue and eigenvectors of a 16-million scale sparse matrix.

To achieve higher levels of assurance for digital systems, we need to answer questions such as does this software have bugs of these critical classes? Do two software assurance tools find the same set of bugs or different, complimentary sets? Can we guarantee that a new technique discovers all problems of this type? To answer such questions, we need a vastly improved way to describe classes of vulnerabilities and chains of failures. We present the Bugs Framework (BF), which raises the current realm of best efforts and useful heuristics. Our BF includes rigorous definitions and (static) attributes of bug classes, along with their related dynamic properties, such as proximate, secondary and tertiary causes, consequences and sites. The paper discusses the buffer overflow class, the injection class and the control of interaction frequency class, and provides examples of applying our BF taxonomy to describe particular vulnerabilities.

With the fast growing use of web-based map services, the performance of indexing and querying of location-based data is becoming a critical quality of service aspect. Spatial indexing is typically time-consuming and is not available to end-users. To address this challenge, we have developed and open-sourced an Online Indexing and Querying System for Big Geospatial Data, sksOpen. Integrated with the TerraFly Geospatial database [1], TerraFly sksOpen is an efficient indexing and query engine for processing Top-k Spatial Boolean Queries. Further, we provide ergonomic visualization of query results on interactive maps to facilitate the user's data analysis.

Abstract Recent technological advances in mobile computing and wireless communication have made portable devices, such as PDA, laptops, and wireless modems to be very compact and affordable. On the other hand, wireless networks have gained such wide popularity that new network infrastructure is continually introduced. It is thus likely that many of the future portable devices will be equipped with multiple wireless modems such as Bluetooth and 802.11 WLAN, in order to increase device inter‐operability. The availability of multiple modems can leverage the performance of the communication traffic generated by the applications, for example Internet access. We envision a tool for managing the device connection through these modems. At the core of this tool is an optimization engine that splits packet traffic across a subset of the available transports so that user's performance metrics are maximized. This paper describes a mathematical model for such an optimization problem considering its applicability to small portable devices. Relevant quality of service (QoS) parameters such as bandwidth, average delay, and energy consumption are covered in the model. The mathematical formulation is validated using a simulated environment. The experimental results have demonstrated the effectiveness of our model and captured the inter‐relationship among the quality parameters. Copyright © 2006 John Wiley & Sons, Ltd.

Testing has a vital support role in the software engineering process, but developing tests often takes significant resources. A formal specification is a repository of knowledge about a system, and a recent method uses such specifications to automatically generate complete test suites via mutation analysis. We define an extensive set of mutation operators for use with this method. We report the results of our theoretical and experimental investigation of the relationships between the classes of faults detected by the various operators. Finally, we recommend sets of mutation operators which yield good test coverage at a reduced cost compared to using all proposed operators.

We consider the problem of quantizer design in a distributed estimation system with communication constraints in the case where only a training sequence is available. Our approach is based on a generalization of regression trees. The look-ahead method that we also propose improves significantly the performance. The final system performs similarly to the one that assumes known statistics.

We consider the problem of quantizer design in a distributed estimation system with communication constraints at the channels in the case where the observation statistics are unknown and one must rely on a training set. The method that we propose applies a variation of the cyclic generalized Lloyd algorithm (CGLA) on every point of the training set and then uses a neural network for each quantizer to represent the training points along with their associated codewords. The codeword of every training point is initialized using a regression tree approach. Simulations show that the combined approach i.e. building the regression tree system and using its quantizers to initialize the neural networks provides an improvement over the regression tree approach except in the case of high noise variance.

The transposition network Tn of order n! is the Cayley graph of the symmetric group Sn with generators the set of all transpositions in Sn. Finding the bisection width of the transposition network is an open question posed by F. T. Leighton. We resolve this question for n even, by showing that the bisection width of the transposition network Tn is equal to nn!/4. When n ≥ 2 is odd, we show that the bisection width of the transposition network Tn is (1 + o(1))nn!/4. In doing so, we determine the second smallest eigenvalue of the adjacency matrix of Tn. Further, given a Cayley graph of a finite group G, with m conjugacy classes and with a set of generators closed under taking conjugates and not containing the identity of G, we show how to construct an m × m integer matrix Q, from the conjugacy classes of G, such that the set of eigenvalues of Q is equal to the set of eigenvalues of the adjacency matrix A of the given Cayley graph. Hence, when the order of G is large compared to the number of its conjugacy classes, a faster method for computing the eigenvalues of A is provided. © 1997 John Wiley & Sons, Inc.

Abstract In this paper, we further study the properties of bipartite permutation graphs. We give first efficient parallel algorithms for several problems on bipartite permutation graphs. These problems include transforming a bipartite graph into a strongly ordered one if it is also a permutation graph; testing isomorphism; finding a Hamiltonian path/cycle; solving a variant of the crossing number problem; and others. All these problems can be solved in O (log 2 n ) time with O ( n 3 ) processors on a Common CRCW PRAM. We also show that the minimum fill‐in problem for bipartite permutation graphs can be solved efficiently by a randomized parallel algorithm. © 1993 by John Wiley & Sons, Inc.

Lower bounds are proven on the parallel-time complexity of several basic functions on the most powerful concurrent-read concurrent-write PRAM with unlimited shared memory and unlimited power of individual processors (denoted by PRIORITY(∞)): It is proved that with a number of processors polynomial in n , Ω (log n ) time is needed for addition, multiplication or bitwise OR of n numbers, when each number has n ' bits. Hence even the bit complexity (i.e., the time complexity as a function of the total number of bits in the input) is logarithmic in this case. This improves a beautiful result of Meyer auf der Heide and Wigderson [22]. They proved a log n lower bound using Ramsey-type techniques. Using Ramsey theory, it is possible to get an upper bound on the number of bits in the inputs used. However, for the case of polynomially many processors, this upper bound is more than a polynomial in n . An Ω (log n ) lower bound is given for PRIORITY(∞) with n o(1) processors on a function with inputs from {0, 1}, namely for the function ƒ( x 1 , … , x n ,) = Σ n l - 1 x l a i where a is fixed and x i ε {0, 1}. Finally, by a new efficient simulation of PRIORITY(∞) by unbounded fan-in circuits, that with less than exponential number of processors, it is proven a PRIORITY(∞) cannot compute PARITY in constant time, and with n O(1) processors Ω(√log n ) time is needed. The simulation technique is of independent interest since it can serve as a general tool to translate circuit lower bounds into PRAM lower bounds. Further, the lower bounds in (1) and (2) remain valid for probabilistic or nondeterministic concurrent-read concurrent-write PRAMS.

This paper presents a parallel algorithm for constructing depth first spanning trees in planar graphs. The algorithm takes $O(\log ^2 n)$ time with $O(n)$ processors on a concurrent read concurrent write parallel random access machine (PRAM). The best previously known algorithm for the problem takes $O(\log ^3 n)$ time with $O(n^4 )$ processors on a PRAM. Our algorithm is within an $O(\log ^2 n)$ factor of optimality.

Article New lower bounds for parallel computation Share on Authors: M Li Department of Computer and Information Science, The Ohio State University, Columbus, OH Department of Computer and Information Science, The Ohio State University, Columbus, OHView Profile , Y Yesha Department of Computer and Information Science, The Ohio State University, Columbus, OH Department of Computer and Information Science, The Ohio State University, Columbus, OHView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 177–187https://doi.org/10.1145/12130.12148Published:01 November 1986 11citation355DownloadsMetricsTotal Citations11Total Downloads355Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We show that string-matching cannot be performed by a two-head one-way deterministic finite automaton (or even by a Turing machine with two one-way input heads and o(n) storage space). Thus, we answer the special case k = 2 of the open question, due to Galil and Seiferas (1983), whether a k-head one-way deterministic finite automaton can perform string-matching.

Let $\Sigma $ be a finite alphabet. A set $S \subset \Sigma ^ * $ is called sparse if the number of members of S having length at most n is bounded above by a polynomial in n. Let $ \leqq _m^P $ denote polynomial-time many-one reducibility, and let $ \leqq _{bptt}^P $ denote the more general polynomial-time bounded positive truth-table reducibility. We prove: (1) $ \leqq _{bptt}^P $ reducibility of a coNP-hard set to a sparse set implies ${\text{NP}} = {\text{P}}$, and (2) $ \leqq _{bptt}^P $ reducibility of an NP-hard set to a sparse set which is itself in NP implies ${\text{NP}} = {\text{P}}$. (1) generalizes Fortune’s result [F]. He proved it for the case of $ \leqq _m^P $ reducibility. (2), for the case of $ \leqq _m^P $ reducibility, was proved by Mahaney [M], even without assuming that the sparse set itself is in NP. Our results imply that if a coNP-hard set is a finite union of sets which are $ \leqq _m^P $ reducible to sparse sets, then ${\text{NP}} = {\text{P}}$. We then investigate a certain nonpositive polynomial-time truth-table reducibility of NP-hard sets to sparse sets, and obtain new results regarding the structure of sets hard for NP or for ETIME. Finally, we investigate the possibility of existence of sets in NP–coNP which are $ \leqq _m^P $ reducible to sparse sets. Some of our techniques involve generalizations of and variations on the techniques of Berman [B], Fortune [F] and Mahaney [M].

Abstract Horn's algorithm for weighted mean flow scheduling with treelike precedence constraints is reexamined. A new analysis of an efficient implementation of Horn's algorithm shows an O(n log n) complexity. This is an improvement on the known O(n2) complexity of this algorithm. An application of Horn's algorithm to a problem of optimal scheduling of a treelike communication network is presented.

We consider the game of Checkers generalized to an N × N board. Although certain properties of positions are efficiently computable (e.g., can Black jump all of White's pieces in a single move?), the general question, given a position, of whether a specified player can force a win against best play by his opponent, is shown to be PSPACE-hard. Under certain reasonable assumptions about the "drawing rule" in force, the problem is itself in PSPACE and hence is PSPACE-complete.