OpenRaiser/Intern-Atlas huggingface dataset:
Domain Decomposition in space-time of 4D-VAR Data Assimilation problem: a case study on the ROMS software
Venue: arXiv cs.CE 2021
Year: 2021

Domain Decomposition of 4D-VAR Data Assimilation (DD-4DVAR) is made up of decomposition of the spate-time domain, solution of reduced forecast model and minimization of local 4D-VAR functionals. Relying on the existing software implementation of ROMS software, we describe main components of DD-4D VAR DA method, highlighting the topics that we will should address both on the mathematical problem underlying ROMS and the MPI-based code implementation of the ROMS-IS4DVAR formulation.
Machine Learning and Artificial Intelligence in Next-Generation Wireless Network
Venue: arXiv cs.NI 2021
Year: 2021

Due to the advancement in technologies, the next-generation wireless network will be very diverse, complicated, and according to the changed demands of the consumers. The current network operator methodologies and approaches are traditional and cannot help the next generation networks to utilize their resources most appropriately. The limited capability of the traditional tools will not allow the network providers to fulfill the demands of the network's subscribers in the future. Therefore, this paper will focus on machine learning, automation, artificial intelligence, and big data analytics for improving the capacity and effectiveness of next-generation wireless networks. The paper will discuss the role of these new technologies in improving the service and performance of the network providers in the future. The paper will find out that machine learning, big data analytics, and artificial intelligence will help in making the next-generation wireless network self-adaptive, self-aware, prescriptive, and proactive. At the end of the paper, it will be provided that future wireless network operators cannot work without shifting their operational framework to AI and machine learning technologies.
A Note on Scheduling Equal-Length Jobs to Maximize Throughput
Venue: arXiv cs.DS 2021
Year: 2021

We study the problem of scheduling equal-length jobs with release times and deadlines, where the objective is to maximize the number of completed jobs. Preemptions are not allowed. In Graham's notation, the problem is described as 1|r_j;p_j=p|\sum U_j. We give the following results: (1) We show that the often cited algorithm by Carlier from 1981 is not correct. (2) We give an algorithm for this problem with running time O(n^5).
Integration of ontology with machine learning to predict the presence of covid-19 based on symptoms
Venue: arXiv cs.IR 2022
Year: 2022

Coronavirus (covid 19) is one of the most dangerous viruses that have spread all over the world. With the increasing number of cases infected with the coronavirus, it has become necessary to address this epidemic by all available means. Detection of the covid-19 is currently one of the world's most difficult challenges. Data science and machine learning (ML), for example, can aid in the battle against this pandemic. Furthermore, various research published in this direction proves that ML techniques can identify illness and viral infections more precisely, allowing patients' diseases to be detected at an earlier stage. In this paper, we will present how ontologies can aid in predicting the presence of covid-19 based on symptoms. The integration of ontology and ML is achieved by implementing rules of the decision tree algorithm into ontology reasoner. In addition, we compared the outcomes with various ML classifications used to make predictions. The findings are assessed using performance measures generated from the confusion matrix, such as F-measure, accuracy, precision, and recall. The ontology surpassed all ML algorithms with high accuracy value of 97.4%, according to the results.
Efficient Rounding for the Noncommutative Grothendieck Inequality
Venue: arXiv cs.DS 2022
Year: 2022

$ \newcommand{\cclass}[1]{\textsf{#1}} $The classical Grothendieck inequality has applications to the design of approximation algorithms for $\cclass{NP}$-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a polynomial-time constant-factor approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principal component analysis and the orthogonal Procrustes problem.
Choice Disjunctive Queries in Logic Programming
Venue: arXiv cs.LO 2022
Year: 2022

One of the long-standing research problems on logic programming is to treat the cut predicate in a logical, high-level way. We argue that this problem can be solved by adopting linear logic and choice-disjunctive goal formulas of the form $G_0 \add G_1$ where $G_0, G_1$ are goals. These goals have the following intended semantics: $choose$ the true disjunct $G_i$ and execute $G_i$ where $i (= 0\ {\rm or}\ 1)$, while $discarding$ the unchosen disjunct. Note that only one goal can remain alive during execution. These goals thus allow us to specify mutually exclusive tasks in a high-level way.
Limiting Lamport Exposure to Distant Failures in Globally-Managed Distributed Systems
Venue: arXiv cs.DC 2022
Year: 2022

Globalized computing infrastructures offer the convenience and elasticity of globally managed objects and services, but lack the resilience to distant failures that localized infrastructures such as private clouds provide. Providing both global management and resilience to distant failures, however, poses a fundamental problem for configuration services: How to discover a possibly migratory, strongly-consistent service/object in a globalized infrastructure without dependencies on globalized state? Limix is the first metadata configuration service that addresses this problem. With Limix, global strongly-consistent data-plane services and objects are insulated from remote gray failures by ensuring that the definitive, strongly-consistent metadata for any object is always confined to the same region as the object itself. Limix guarantees availability bounds: any user can continue accessing any strongly consistent object that matters to the user located at distance $Δ$ away, insulated from failures outside a small multiple of $Δ$. We built a Limix metadata service based on CockroachDB. Our experiments on Internet-like networks and on AWS, using realistic trace-driven workloads, show that Limix enables global management and significantly improves availability over the state-of-the-art.
The Digital Public Library of America Ingestion Ecosystem: Lessons Learned After One Year of Large-Scale Collaborative Metadata Aggregation
Venue: arXiv cs.DL 2022
Year: 2022

The Digital Public Library of America (DPLA) aggregates metadata for cultural heritage materials from 20 direct partners, or Hubs, across the United States. While the initial build-out of the DPLA's infrastructure used a lightweight ingestion system that was ultimately pushed into production, a year's experience has allowed DPLA and its partners to identify limitations to that system, the quality and scalability of metadata remediation and enhancement possible, and areas for collaboration and leadership across the partnership. Although improved infrastructure is needed to support aggregation at this scale and complexity, ultimately DPLA needs to balance responsibilities across the partnership and establish a strong community that shares ownership of the aggregation process.
PH = PSPACE
Venue: arXiv cs.CC 2022
Year: 2022

In this paper we show that PSPACE is equal to 4th level in the polynomial hierarchy. We also deduce a lot of important consequences. True quantified Boolean formula is a generalisation of the Boolean Satisfiability Problem, where determining of interpretation that satisfies a given Boolean formula is replaced by existence of Boolean functions that makes a given QBF to be tautology. Such functions are called the Skolem functions. The essential idea of the proof is to show that for any quantified Boolean formula $ϕ$ we can obtain a formula $ϕ'$ which is in the 4th level of the polynomial hierarchy, no more than polynomial in the size of a given $ϕ$, such that the truth of $ϕ$ can be determined from the truth of $ϕ'$. The idea is to skolemize, and then use additional formulas from the 2nd level of the polynomial hierarchy inside the skolemized prefix to enforce that the skolem variables indeed depend only on the universally quantified variables they are supposed to. However, some dependence is lost when the quantification is reversed. It is called "XOR issue" because the functional dependence can be expressed by means of an XOR formula. Thus, it is needed to locate these XORs, but there is no need to locate all chains with XORs: any chain includes a XOR of only two variables. The last can be done locally in each iteration (keep in mind the algebraic normal form (ANF)), when all arguments are specified, i.e. as a polynomial subroutine. Relativization is defeated due to the well-known fact: PH = PSPACE iff second-order logic over finite structures gains no additional power from the addition of a transitive closure operator. The exchange is possible due to finite possibilities for arguments. So, the theorems with oracles are not applicable since a random oracle is an arbitrary set. And that's why PH is infinite relative to a random oracle with probability 1.
Replication of arbitrary hole-free shapes via self-assembly with signal-passing tiles
Venue: arXiv cs.ET 2022
Year: 2022

In this paper, we investigate the abilities of systems of self-assembling tiles which can each pass a constant number of signals to their immediate neighbors to create replicas of input shapes. Namely, we work within the Signal-passing Tile Assembly Model (STAM), and we provide a universal STAM tile set which is capable of creating unbounded numbers of assemblies of shapes identical to those of input assemblies. The shapes of the input assemblies can be arbitrary 2-dimensional hole-free shapes. This improves previous shape replication results in self-assembly that required models in which multiple assembly stages and/or bins were required, and the shapes which could be replicated were more constrained, as well as a previous version of this result that required input shapes to be represented at scale factor 2.
When Hillclimbers Beat Genetic Algorithms in Multimodal Optimization
Venue: arXiv cs.NE 2022
Year: 2022

This paper investigates the performance of multistart next ascent hillclimbing and well-known evolutionary algorithms incorporating diversity preservation techniques on instances of the multimodal problem generator. This generator induces a class of problems in the bitstringdomain which is interesting to study from a theoretical perspective in the context of multimodal optimization, as it is a generalization of the classical OneMax and TwoMax functions for an arbitrary number of peaks. An average-case runtime analysis for multistart next ascent hill-climbing is presented for uniformly distributed equal-height instances of this class of problems. It is shown empirically that conventional niching and mating restriction techniques incorporated in an evolutionary algorithm are not sufficient to make them competitive with the hillclimbing strategy. We conjecture the reason for this behaviour is the lack of structure in the space of local optima on instances of this problem class, which makes an optimization algorithm unable to exploit information from one optimum to infer where another optimum might be. When no such structure exist, it seems that the best strategy for discovering all optima is a brute-force one. Overall, our study gives insights with respect to the adequacy of hillclimbers and evolutionary algorithms for multimodal optimization, depending on properties of the fitness landscape.
Media-Based Modulation for Next-Generation Wireless: A Survey and Some New Developments
Venue: arXiv cs.IT 2022
Year: 2022

The idea of media-based modulation (MBM) is to embed information in the channel states via intentional perturbations of the transmission media. This article covers a broad range of topics regarding MBM, expanding on its benefits and reviewing relevant challenges, alluding to potential future research directions. The article starts by arguing how MBM differs from a source-based modulation; we highlight the key shortcomings in a legacy multiple-input multiple-output (MIMO) system that MBM sets out to address, including the issue of deep fades and MIMO diversity-multiplexing trade-off. The article further explains how MBM works in harmony with other index modulations and improves upon them by providing similar advantages with a more compact transmitter. Numerical results (simulation and analytical) are provided to support the claims on the discussed benefits. The highlights of numerical results include: 1) outage comparison with legacy MIMO systems; 2) comparisons with other state-of-the-art modulation schemes such as generalized spatial modulation; and 3) performance example of sending 32 bits of information in a single transmission with an excellent symbol error rate of $\mathsf{SER} \simeq 10^{-5}$ at \say{energy per bit to noise power spectral density ratio} of $\mathsf{E_b/N_0} \simeq -3.5$ dB. The article continues with methods to address the issues of receiver training and decoding for large constellation sets. A number of other research questions, such as pulse shaping to limit spectral growth due to the time-varying nature of MBM and the effect of forward error correcting codes on MBM diversity order are discussed. Finally, an RF transceiver structure is presented to generate independent propagation paths for embedding information. Fabrication and testing of the transceiver structure show close agreement between simulation and measurement.
Algorithm 979: Recursive Algorithms for Dense Linear Algebra -- The ReLAPACK Collection
Venue: arXiv cs.MS 2022
Year: 2022

To exploit both memory locality and the full performance potential of highly tuned kernels, dense linear algebra libraries such as LAPACK commonly implement operations as blocked algorithms. However, to achieve next-to-optimal performance with such algorithms, significant tuning is required. On the other hand, recursive algorithms are virtually tuning free, and yet attain similar performance. In this paper, we first analyze and compare blocked and recursive algorithms in terms of performance, and then introduce ReLAPACK, an open-source library of recursive algorithms to seamlessly replace most of LAPACK's blocked algorithms. In many scenarios, ReLAPACK clearly outperforms reference LAPACK, and even improves upon the performance of optimizes libraries.
A Super-Resolution Framework for Tensor Decomposition
Venue: arXiv cs.IT 2022
Year: 2022

This work considers a super-resolution framework for overcomplete tensor decomposition. Specifically, we view tensor decomposition as a super-resolution problem of recovering a sum of Dirac measures on the sphere and solve it by minimizing a continuous analog of the $\ell_1$ norm on the space of measures. The optimal value of this optimization defines the tensor nuclear norm. Similar to the separation condition in the super-resolution problem, by explicitly constructing a dual certificate, we develop incoherence conditions of the tensor factors so that they form the unique optimal solution of the continuous analog of $\ell_1$ norm minimization. Remarkably, the derived incoherence conditions are satisfied with high probability by random tensor factors uniformly distributed on the sphere, implying global identifiability of random tensor factors.
Ternary Weight Networks
Venue: arXiv cs.CV 2022
Year: 2022

We present a memory and computation efficient ternary weight networks (TWNs) - with weights constrained to +1, 0 and -1. The Euclidian distance between full (float or double) precision weights and the ternary weights along with a scaling factor is minimized in training stage. Besides, a threshold-based ternary function is optimized to get an approximated solution which can be fast and easily computed. TWNs have shown better expressive abilities than binary precision counterparts. Meanwhile, TWNs achieve up to 16$\times$ model compression rate and need fewer multiplications compared with the float32 precision counterparts. Extensive experiments on MNIST, CIFAR-10, and ImageNet datasets show that the TWNs achieve much better result than the Binary-Weight-Networks (BWNs) and the classification performance on MNIST and CIFAR-10 is very close to the full precision networks. We also verify our method on object detection task and show that TWNs significantly outperforms BWN by more than 10\% mAP on PASCAL VOC dataset. The pytorch version of source code is available at: https://github.com/Thinklab-SJTU/twns.
DAiSEE: Towards User Engagement Recognition in the Wild
Venue: arXiv cs.CV 2022
Year: 2022

We introduce DAiSEE, the first multi-label video classification dataset comprising of 9068 video snippets captured from 112 users for recognizing the user affective states of boredom, confusion, engagement, and frustration in the wild. The dataset has four levels of labels namely - very low, low, high, and very high for each of the affective states, which are crowd annotated and correlated with a gold standard annotation created using a team of expert psychologists. We have also established benchmark results on this dataset using state-of-the-art video classification methods that are available today. We believe that DAiSEE will provide the research community with challenges in feature extraction, context-based inference, and development of suitable machine learning methods for related tasks, thus providing a springboard for further research. The dataset is available for download at https://people.iith.ac.in/vineethnb/resources/daisee/index.html.
An Explicit, Coupled-Layer Construction of a High-Rate Regenerating Code with Low Sub-Packetization Level, Small Field Size and $d< (n-1)$
Venue: arXiv cs.IT 2022
Year: 2022

This paper presents an explicit construction for an $((n=2qt,k=2q(t-1),d=n-(q+1)), (α= q(2q)^{t-1},β= \fracα{q}))$ regenerating code (RGC) over a field $\mathbb{F}_Q$ having rate $\geq \frac{t-2}{t}$. The RGC code can be constructed to have rate $k/n$ as close to $1$ as desired, sub-packetization level $α\leq r^{\frac{n}{r}}$ for $r=(n-k)$, field size $Q$ no larger than $n$ and where all code symbols can be repaired with the same minimum data download.
ME R-CNN: Multi-Expert R-CNN for Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

We introduce Multi-Expert Region-based Convolutional Neural Network (ME R-CNN) which is equipped with multiple experts (ME) where each expert is learned to process a certain type of regions of interest (RoIs). This architecture better captures the appearance variations of the RoIs caused by different shapes, poses, and viewing angles. In order to direct each RoI to the appropriate expert, we devise a novel "learnable" network, which we call, expert assignment network (EAN). EAN automatically learns the optimal RoI-expert relationship even without any supervision of expert assignment. As the major components of ME R-CNN, ME and EAN, are mutually affecting each other while tied to a shared network, neither an alternating nor a naive end-to-end optimization is likely to fail. To address this problem, we introduce a practical training strategy which is tailored to optimize ME, EAN, and the shared network in an end-to-end fashion. We show that both of the architectures provide considerable performance increase over the baselines on PASCAL VOC 07, 12, and MS COCO datasets.
Satellite Image-based Localization via Learned Embeddings
Venue: arXiv cs.RO 2022
Year: 2022

We propose a vision-based method that localizes a ground vehicle using publicly available satellite imagery as the only prior knowledge of the environment. Our approach takes as input a sequence of ground-level images acquired by the vehicle as it navigates, and outputs an estimate of the vehicle's pose relative to a georeferenced satellite image. We overcome the significant viewpoint and appearance variations between the images through a neural multi-view model that learns location-discriminative embeddings in which ground-level images are matched with their corresponding satellite view of the scene. We use this learned function as an observation model in a filtering framework to maintain a distribution over the vehicle's pose. We evaluate our method on different benchmark datasets and demonstrate its ability localize ground-level images in environments novel relative to training, despite the challenges of significant viewpoint and appearance variations.
Adposition and Case Supersenses v2.6: Guidelines for English
Venue: arXiv cs.CL 2022
Year: 2022

This document offers a detailed linguistic description of SNACS (Semantic Network of Adposition and Case Supersenses; Schneider et al., 2018), an inventory of 52 semantic labels ("supersenses") that characterize the use of adpositions and case markers at a somewhat coarse level of granularity, as demonstrated in the STREUSLE corpus (https://github.com/nert-nlp/streusle/ ; version 4.5 tracks guidelines version 2.6). Though the SNACS inventory aspires to be universal, this document is specific to English; documentation for other languages will be published separately. Version 2 is a revision of the supersense inventory proposed for English by Schneider et al. (2015, 2016) (henceforth "v1"), which in turn was based on previous schemes. The present inventory was developed after extensive review of the v1 corpus annotations for English, plus previously unanalyzed genitive case possessives (Blodgett and Schneider, 2018), as well as consideration of adposition and case phenomena in Hebrew, Hindi, Korean, and German. Hwang et al. (2017) present the theoretical underpinnings of the v2 scheme. Schneider et al. (2018) summarize the scheme, its application to English corpus data, and an automatic disambiguation task. Liu et al. (2021) offer an English Lexical Semantic Recognition tagger that includes SNACS labels in its output. This documentation can also be browsed alongside corpus data on the Xposition website (Gessler et al., 2022): http://www.xposition.org/
Mo3: a Modular Mobility Model for future generation mobile wireless networks
Venue: arXiv cs.NI 2022
Year: 2022

Mobility modeling in 5G and beyond 5G must address typical features such as time-varying correlation between mobility patterns of different nodes, and their variation ranging from macro-mobility (kilometer range) to micro-mobility (sub-meter range). Current models have strong limitations in doing so: the widely used reference-based models, such as the Reference Point Group Mobility (RPGM), lack flexibility and accuracy, while the more sophisticated rule-based (i.e. behavioral) models are complex to set-up and tune. This paper introduces a new rule-based Modular Mobility Model, named Mo3, that provides accuracy and flexibility on par with behavioral models, while preserving the intuitiveness of the reference-based approach, and is based on five rules: 1) Individual Mobility, 2) Correlated Mobility, 3) Collision Avoidance, 4) Obstacle Avoidance and 5) Upper Bounds Enforcement. Mo3 avoids introducing acceleration vectors to define rules, as behavioral models do, and this significantly reduces complexity. Rules are mapped one-to-one onto five modules, that can be independently enabled or replaced. Comparison of time-correlation features obtained with Mo3 vs. reference-based models, and in particular RPGM, in pure micro-mobility and mixed macro-mobility / micro-mobility scenarios, shows that Mo3 and RPGM generate mobility patterns with similar topological properties (intra-group and inter-group distances), but that Mo3 preserves a spatial correlation that is lost in RPGM - at no price in terms of complexity - making it suitable for adoption in 5G and beyond 5G.