OpenRaiser/Intern-Atlas huggingface dataset:
Tensor Reconstruction Beyond Constant Rank
Venue: arXiv cs.CC 2022
Year: 2022

We give reconstruction algorithms for subclasses of depth-3 arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. We obtain the following results: 1. A deterministic algorithm that reconstructs polynomials computed by $Σ^{[k]}\bigwedge^{[d]}Σ$ circuits in time $\mathsf{poly}(n,d,c) \cdot \mathsf{poly}(k)^{k^{k^{10}}}$ 2. A randomized algorithm that reconstructs polynomials computed by multilinear $Σ^{k]}\prod^{[d]}Σ$ circuits in time $\mathsf{poly}(n,d,c) \cdot k^{k^{k^{k^{O(k)}}}}$ 3. A randomized algorithm that reconstructs polynomials computed by set-multilinear $Σ^{k]}\prod^{[d]}Σ$ circuits in time $\mathsf{poly}(n,d,c) \cdot k^{k^{k^{k^{O(k)}}}}$, where $c=\log q$ if $\mathbb{F}=\mathbb{F}_q$ is a finite field, and $c$ equals the maximum bit complexity of any coefficient of $f$ if $\mathbb{F}$ is infinite. Prior to our work, polynomial time algorithms for the case when the rank, $k$, is constant, were given by Bhargava, Saraf and Volkovich [BSV21]. Another contribution of this work is correcting an error from a paper of Karnin and Shpilka [KS09] that affected Theorem 1.6 of [BSV21]. Consequently, the results of [KS09, BSV21] continue to hold, with a slightly worse setting of parameters. For fixing the error we study the relation between syntactic and semantic ranks of $ΣΠΣ$ circuits. We obtain our improvement by introducing a technique for learning rank preserving coordinate-subspaces. [KS09] and [BSV21] tried all choices of finding the "correct" coordinates, which led to having a fast growing function of $k$ at the exponent of $n$. We find these spaces in time that is growing fast with $k$, yet it is only a fixed polynomial in $n$.
Self-supervised Learning for Heterogeneous Graph via Structure Information based on Metapath
Venue: arXiv cs.LG 2022
Year: 2022

graph neural networks (GNNs) are the dominant paradigm for modeling and handling graph structure data by learning universal node representation. The traditional way of training GNNs depends on a great many labeled data, which results in high requirements on cost and time. In some special scene, it is even unavailable and impracticable. Self-supervised representation learning, which can generate labels by graph structure data itself, is a potential approach to tackle this problem. And turning to research on self-supervised learning problem for heterogeneous graphs is more challenging than dealing with homogeneous graphs, also there are fewer studies about it. In this paper, we propose a SElfsupervised learning method for heterogeneous graph via Structure Information based on Metapath (SESIM). The proposed model can construct pretext tasks by predicting jump number between nodes in each metapath to improve the representation ability of primary task. In order to predict jump number, SESIM uses data itself to generate labels, avoiding time-consuming manual labeling. Moreover, predicting jump number in each metapath can effectively utilize graph structure information, which is the essential property between nodes. Therefore, SESIM deepens the understanding of models for graph structure. At last, we train primary task and pretext tasks jointly, and use meta-learning to balance the contribution of pretext tasks for primary task. Empirical results validate the performance of SESIM method and demonstrate that this method can improve the representation ability of traditional neural networks on link prediction task and node classification task.
A Software Package for Queueing Networks and Markov Chains analysis
Venue: arXiv cs.PF 2022
Year: 2022

Queueing networks and Markov chains are widely used for conducting performance and reliability studies. In this paper we describe the queueing package, a free software package for queueing networks and Markov chain analysis for GNU Octave. The queueing package provides implementations of numerical algorithms for computing transient and steady-state performance measures of discrete and continuous Markov chains, and for steady-state analysis of single-station queueing systems and queueing networks. We illustrate the design principles of the queueing package, describe its most salient features and provide some usage examples.
Deriving dynamical systems for language based on the Tolerance Principle
Venue: arXiv cs.CL 2022
Year: 2022

In this research note, I derive explicit dynamical systems for language within an acquisition-driven framework (Niyogi \& Berwick, 1997; Niyogi, 2006) assuming that children/learners follow the Tolerance Principle (Yang, 2016) to determine whether a rule is productive during the process of language acquisition. I consider different theoretical parameters such as population size (finite vs. infinite) and the number of previous generations that provide learners with data. Multiple simulations of the dynamics obtained here and applications to diacrhonic language data are in preparation, so they are not included in this first note.
Sensing using Coded Communications Signals
Venue: arXiv cs.IT 2022
Year: 2022

A key challenge for a common waveform for Integrated Sensing and Communications (ISAC) - widely seen as an attractive proposition to achieve high performance for both functionalities, while efficiently utilizing available resources -- lies in leveraging information-bearing channel-coded communications signals (c.c.s) for sensing. In this paper, we investigate the sensing performance of c.c.s in (multi-user) interference-limited operation, and show that it is limited by sidelobes in the range-Doppler map, whose form depends on whether the c.c.s modulates a single-carrier or OFDM waveform. While uncoded communications signals -- comprising a block of $N$ i.i.d zero-mean symbols -- give rise to asymptotically (i.e., as $N \rightarrow \infty$) zero sidelobes due to the law of large numbers, it is not obvious that the same holds for c.c.s, as structured channel coding schemes (e.g., linear block codes) induce dependence across codeword symbols. In this paper, we show that c.c.s also give rise to asymptotically zero sidelobes -- for both single-carrier and OFDM waveforms -- by deriving upper bounds for the tail probabilities of the sidelobe magnitudes that decay as $\exp( - O($code rate $\times$ block length$))$. This implies that for any code rate, c.c.s are effective sensing signals that are robust to multi-user interference at sufficiently large block lengths, with negligible difference in performance based on whether they modulate a single-carrier or OFDM waveform. We verify the latter implication through simulations, where we observe the sensing performance (characterized by the detection and false-alarm probabilities) of a QPSK-modulated c.c.s (code rate = 120/1024, block length = 1024 symbols) to match that of a comparable interference-free FMCW waveform even at high interference levels (signal-to-interference ratio of -11dB), for both single-carrier and OFDM waveforms.
Alternate Timelines for TidalCycles
Venue: arXiv cs.OH 2022
Year: 2022

The TidalCycles (or Tidal for short) live coding environment has been developed since around 2009, via several rewrites of its core representation. Rather than having fixed goals, this development has been guided by use, motivated by the open aim to make music. This development process can be seen as a long-form improvisation, with insights into the nature of Tidal gained through the process of writing it, feeding back to guide the next steps of development. This brings the worrying thought that key insights will have been missed along this development journey, that would otherwise have lead to very different software. Indeed participants at beginners' workshops that I have lead or co-lead have often asked questions without good answers, because they made deficiencies or missing features in the software clear. It is well known that a beginner's mind is able to see much that an expert has become blind to. Running workshops are an excellent way to find new development ideas, but the present paper explores a different technique - the rewrite.
Automatic Readability Assessment of German Sentences with Transformer Ensembles
Venue: arXiv cs.CL 2022
Year: 2022

Reliable methods for automatic readability assessment have the potential to impact a variety of fields, ranging from machine translation to self-informed learning. Recently, large language models for the German language (such as GBERT and GPT-2-Wechsel) have become available, allowing to develop Deep Learning based approaches that promise to further improve automatic readability assessment. In this contribution, we studied the ability of ensembles of fine-tuned GBERT and GPT-2-Wechsel models to reliably predict the readability of German sentences. We combined these models with linguistic features and investigated the dependence of prediction performance on ensemble size and composition. Mixed ensembles of GBERT and GPT-2-Wechsel performed better than ensembles of the same size consisting of only GBERT or GPT-2-Wechsel models. Our models were evaluated in the GermEval 2022 Shared Task on Text Complexity Assessment on data of German sentences. On out-of-sample data, our best ensemble achieved a root mean squared error of 0.435.
PetLock:A Genderless and Standard Interface for the Future On-orbit Construction
Venue: arXiv cs.RO 2022
Year: 2022

Modular design is the foundation of on orbit construction technology of large space facilities in the future.Standard interface is the key technology of modular design of the future space robotic systems and space facilities.This paper presents the designed and tested of PetLock,a standard and genderless interface which can transfer mechanical loads,power and data between the future modular space robotic manipulator and spacecraft.PetLock adopts a completely genderless design,including connection face,locking mechanism,data and power interface.The connection surface provides a large translation and rotation misalignment tolerance,due to its 120-degree symmetrical and 3D shape design.The locking mechanism features the three locking pins retraction structure design,which is simple and reliable.POGO pin connectors in the center of the interface provides the power and data transfer capabilities.Due to the advantages of high locking force,large tolerance,high reliability and low cost,PetLock has the very big application potential in future on orbit construction missions.
Pre-training image-language transformers for open-vocabulary tasks
Venue: arXiv cs.CV 2022
Year: 2022

We present a pre-training approach for vision and language transformer models, which is based on a mixture of diverse tasks. We explore both the use of image-text captioning data in pre-training, which does not need additional supervision, as well as object-aware strategies to pre-train the model. We evaluate the method on a number of textgenerative vision+language tasks, such as Visual Question Answering, visual entailment and captioning, and demonstrate large gains over standard pre-training methods.
Energy-Aware JPEG Image Compression: A Multi-Objective Approach
Venue: arXiv cs.CV 2022
Year: 2022

Customer satisfaction is crucially affected by energy consumption in mobile devices. One of the most energy-consuming parts of an application is images. While different images with different quality consume different amounts of energy, there are no straightforward methods to calculate the energy consumption of an operation in a typical image. This paper, first, investigates that there is a correlation between energy consumption and image quality as well as image file size. Therefore, these two can be considered as a proxy for energy consumption. Then, we propose a multi-objective strategy to enhance image quality and reduce image file size based on the quantisation tables in JPEG image compression. To this end, we have used two general multi-objective metaheuristic approaches: scalarisation and Pareto-based. Scalarisation methods find a single optimal solution based on combining different objectives, while Pareto-based techniques aim to achieve a set of solutions. In this paper, we embed our strategy into five scalarisation algorithms, including energy-aware multi-objective genetic algorithm (EnMOGA), energy-aware multi-objective particle swarm optimisation (EnMOPSO), energy-aware multi-objective differential evolution (EnMODE), energy-aware multi-objective evolutionary strategy (EnMOES), and energy-aware multi-objective pattern search (EnMOPS). Also, two Pareto-based methods, including a non-dominated sorting genetic algorithm (NSGA-II) and a reference-point-based NSGA-II (NSGA-III) are used for the embedding scheme, and two Pareto-based algorithms, EnNSGAII and EnNSGAIII, are presented. Experimental studies show that the performance of the baseline algorithm is improved by embedding the proposed strategy into metaheuristic algorithms.
Resilient Consensus via Voronoi Communication Graphs
Venue: arXiv cs.RO 2022
Year: 2022

Consensus algorithms form the foundation for many distributed algorithms by enabling multiple robots to converge to consistent estimates of global variables using only local communication. However, standard consensus protocols can be easily led astray by non-cooperative team members. As such, the study of resilient forms of consensus is necessary for designing resilient distributed algorithms. W-MSR consensus is one such resilient consensus algorithm that allows for resilient consensus with only local knowledge of the communication graph and no a priori model for the data being shared. However, the verification that a given communication graph meets the strict graph connectivity requirement makes W-MSR difficult to use in practice. In this paper, we show that a commonly used communication graph structure in robotics literature, the communication graph built based on the Voronoi tessellation, automatically results in a sufficiently connected graph to reject a single non-cooperative team member. Further, we show how this graph can be enhanced to reject two non-cooperative team members and provide a roadmap for modifications for further resilience. This contribution will allow for the easy application of resilient consensus to algorithms that already rely on Voronoi-based communication such as distributed coverage and exploration algorithms.
The Role Of Biology In Deep Learning
Venue: arXiv cs.NE 2022
Year: 2022

Artificial neural networks took a lot of inspiration from their biological counterparts in becoming our best machine perceptual systems. This work summarizes some of that history and incorporates modern theoretical neuroscience into experiments with artificial neural networks from the field of deep learning. Specifically, iterative magnitude pruning is used to train sparsely connected networks with 33x fewer weights without loss in performance. These are used to test and ultimately reject the hypothesis that weight sparsity alone improves image noise robustness. Recent work mitigated catastrophic forgetting using weight sparsity, activation sparsity, and active dendrite modeling. This paper replicates those findings, and extends the method to train convolutional neural networks on a more challenging continual learning task. The code has been made publicly available.
Elastic RAID: When RAID Meets SSDs with Built-in Transparent Compression
Venue: arXiv cs.AR 2022
Year: 2022

This paper studies how RAID (redundant array of independent disks) could take full advantage of modern SSDs (solid-state drives) with built-in transparent compression. In current practice, RAID users are forced to choose a specific RAID level (e.g., RAID 10 or RAID 5) with a fixed storage cost vs. speed performance trade-off. Commercial market is witnessing the emergence of a new family of SSDs that can internally perform hardware-based lossless compression on each 4KB LBA (logical block address) block, transparent to host OS and user applications. Beyond straightforwardly reducing the RAID storage cost, such modern SSDs make it possible to relieve RAID users from being locked into a fixed storage cost vs. speed performance trade-off. The key idea is simple: RAID systems opportunistically leverage higher-than-expected runtime user data compressibility to enable dynamic RAID level conversion to improve the speed performance without compromising the effective storage capacity. This paper presents design techniques to enable and optimize the practical implementation of such elastic RAID systems. For the purpose of demonstration, we implemented a Linux software-based elastic RAID prototype that supports dynamic conversion between RAID 5 and RAID 10. Compared with a baseline software-based RAID 5, under sufficient runtime data compressibility that enables the conversion from RAID 5 to RAID 10 over 60% user data, the elastic RAID could improve the 4KB random write IOPS (IO per second) by 42% and 4KB random read IOPS in degraded mode by 46%, while maintaining the same effective storage capacity.
SMART: Investigating the Impact of Threshold Voltage Suppression in an In-SRAM Multiplication/Accumulation Accelerator for Accuracy Improvement in 65 nm CMOS Technology
Venue: arXiv cs.AR 2022
Year: 2022

State-of-the-art in-memory computation has recently emerged as the most promising solution to overcome design challenges related to data movement inside current computing systems. One of the approaches to performing in-memory computation is based on the analog behavior of the data stored inside the memory cell. These approaches proposed various system architectures for that. In this paper, we investigated the effect of threshold voltage suppression on the access transistors of the In-SRAM multiplication and accumulation (MAC) accelerator to improve and enhance the performance of bit line (bit line bar) discharge rate that will increase the accuracy of MAC operation. We provide a comprehensive analytical analysis followed by circuit implementation, including a Monte-Carlo simulation by a 65nm CMOS technology. We confirmed the efficiency of our method (SMART) for a four-by-four-bit MAC operation. The proposed technique improves the accuracy while consuming 0.683 pJ per computation from a power supply of 1V. Our novel technique presents less than 0.009 standard deviations for the worst-case incorrect output scenario.
MCIBI++: Soft Mining Contextual Information Beyond Image for Semantic Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Co-occurrent visual pattern makes context aggregation become an essential paradigm for semantic segmentation.The existing studies focus on modeling the contexts within image while neglecting the valuable semantics of the corresponding category beyond image. To this end, we propose a novel soft mining contextual information beyond image paradigm named MCIBI++ to further boost the pixel-level representations. Specifically, we first set up a dynamically updated memory module to store the dataset-level distribution information of various categories and then leverage the information to yield the dataset-level category representations during network forward. After that, we generate a class probability distribution for each pixel representation and conduct the dataset-level context aggregation with the class probability distribution as weights. Finally, the original pixel representations are augmented with the aggregated dataset-level and the conventional image-level contextual information. Moreover, in the inference phase, we additionally design a coarse-to-fine iterative inference strategy to further boost the segmentation results. MCIBI++ can be effortlessly incorporated into the existing segmentation frameworks and bring consistent performance improvements. Also, MCIBI++ can be extended into the video semantic segmentation framework with considerable improvements over the baseline. Equipped with MCIBI++, we achieved the state-of-the-art performance on seven challenging image or video semantic segmentation benchmarks.
Logic and Reduction Operation based Hardware Trojans in Digital Design
Venue: arXiv cs.CR 2022
Year: 2022

In this paper, we will demonstrate Hardware Trojan Attacks on four different digital designs implemented on FPGA. The hardware trojan is activated based on special logical and reduction-based operations on vectors which makes the trojan-activity as silent and effective as possible. In this paper, we have introduced 5 novel trojan attack methodologies.
PGAbB: A Block-Based Graph Processing Framework for Heterogeneous Platforms
Venue: arXiv cs.DC 2022
Year: 2022

Designing flexible graph kernels that can run well on various platforms is a crucial research problem due to the frequent usage of graphs for modeling data and recent architectural advances and variety. In this work, we propose a novel graph processing framework, PGAbB (Parallel Graph Algorithms by Blocks), for modern shared-memory heterogeneous platforms. Our framework implements a block-based programming model. This allows a user to express a graph algorithm using kernels that operate on subgraphs. PGAbB support graph computations that fit in host DRAM but not in GPU device memory, and provides simple but effective scheduling techniques to schedule computations to all available resources in a heterogeneous architecture. We have demonstrated that one can easily implement a diverse set of graph algorithms in our framework by developing five algorithms. Our experimental results show that PGAbB implementations achieve better or competitive performance compared to hand-optimized implementations. Based on our experiments on five graph algorithms and forty-four graphs, in the median, PGAbB achieves 1.6, 1.6, 5.7, 3.4, 4.5, and 2.4 times better performance than GAPBS, Galois, Ligra, LAGraph Galois-GPU, and Gunrock graph processing systems, respectively.
On the Reliability of Funding Acknowledgements as Research Data: Evidence from Astronomy
Venue: arXiv cs.DL 2022
Year: 2022

Online bibliographic databases have enabled new research through which bibliographic records are analyzed as data about science. Within these records, the acknowledgements sections of papers are often used to draw conclusions about funding support for published research. While acknowledgements and funding statements can be informative for research and policy development, this poster adds to a body of literature that highlights limitations of funding data for scientometric and policy research, using evidence gathered from a questionnaire of authors of astronomy journal articles. The study shows that only 71.4% of a sample of authors of papers tied to NSF grants through acknowledgements reported in the survey that NSF funded the research presented in the respective papers. A brief analysis of the questionnaire followed by recommendations and considerations for further research are presented. The discrepancy in reporting appears to indicate that funding streams can be fluid and not always apparent to authors, overall raising the question of what sorts of research should be addressed with funding statements, where conceptually tying a paper directly to a grant is not straightforward.