OpenRaiser/Intern-Atlas huggingface dataset:
Cross-Language Source Code Clone Detection Using Deep Learning with InferCode
Venue: arXiv cs.SE 2022
Year: 2022

Software clones are beneficial to detect security gaps and software maintenance in one programming language or across multiple languages. The existing work on source clone detection performs well but in a single programming language. However, if a piece of code with the same functionality is written in different programming languages, detecting it is harder as different programming languages have a different lexical structure. Moreover, most existing work rely on manual feature engineering. In this paper, we propose a deep neural network model based on source code AST embeddings to detect cross-language clones in an end-to-end fashion of the source code without the need of the manual process to pinpoint similar features across different programming languages. To overcome data shortage and reduce overfitting, a Siamese architecture is employed. The design methodology of our model is twofold -- (a) it accepts AST embeddings as input for two different programming languages, and (b) it uses a deep neural network to learn abstract features from these embeddings to improve the accuracy of cross-language clone detection. The early evaluation of the model observes an average precision, recall and F-measure score of $0.99$, $0.59$ and $0.80$ respectively, which indicates that our model outperforms all available models in cross-language clone detection.
QUANTAS: Quantitative User-friendly Adaptable Networked Things Abstract Simulator
Venue: arXiv cs.DC 2022
Year: 2022

We present QUANTAS: a simulator that enables quantitative performance analysis of distributed algorithms. It has a number of attractive features. QUANTAS is an abstract simulator, therefore, the obtained results are not affected by the specifics of a particular network or operating system architecture. QUANTAS allows distributed algorithms researchers to quickly investigate a potential solution and collect data about its performance. QUANTAS programming is relatively straightforward and is accessible to theoretical researchers. To demonstrate QUANTAS capabilities, we implement and compare the behavior of two representative examples from four major classes of distributed algorithms: blockchains, distributed hash tables, consensus, and reliable data link message transmission.
Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph Clustering
Venue: arXiv cs.DS 2022
Year: 2022

Hierarchical agglomerative clustering (HAC) is a popular algorithm for clustering data, but despite its importance, no dynamic algorithms for HAC with good theoretical guarantees exist. In this paper, we study dynamic HAC on edge-weighted graphs. As single-linkage HAC reduces to computing a minimum spanning forest (MSF), our first result is a parallel batch-dynamic algorithm for maintaining MSFs. On a batch of $k$ edge insertions or deletions, our batch-dynamic MSF algorithm runs in $O(k\log^6 n)$ expected amortized work and $O(\log^4 n)$ span with high probability. It is the first fully dynamic MSF algorithm handling batches of edge updates with polylogarithmic work per update and polylogarithmic span. Using our MSF algorithm, we obtain a parallel batch-dynamic algorithm that can answer queries about single-linkage graph HAC clusters. Our second result is that dynamic graph HAC is significantly harder for other common linkage functions. For example, assuming the strong exponential time hypothesis, dynamic graph HAC requires $Ω(n^{1-o(1)})$ work per update or query on a graph with $n$ vertices for complete linkage, weighted average linkage, and average linkage. For complete linkage and weighted average linkage, the bound still holds even for incremental or decremental algorithms and even if we allow $\operatorname{poly}(n)$-approximation. For average linkage, the bound weakens to $Ω(n^{1/2 - o(1)})$ for incremental and decremental algorithms, and the bounds still hold when allowing $n^{o(1)}$-approximation.
How Game Jams and Hackathons Accelerate Design Processes
Venue: arXiv cs.HC 2022
Year: 2022

This dissertation presents three years of research on how design processes in game jams and hackathons can be understood as accelerated. Hackathons and game jams can both be described as formats where participants engage in designing and developing prototypes during an intentionally short time frame, such as 48 hours, which is meant to facilitate creativity, and encourage fast decision making and rapid prototyping. Game jams and hackathons are organised in many different contexts and for many different purposes as well, such as: internally in companies to spark new ideas; for fostering citizen innovation for municipalities; in cultural and governmental agencies; integral parts of education; entry points for developers wanting to enter especially the game industry (Olesen, 2020; Kultima, 2015). During the recent decade, game jams and hackathons have been introduced to academia as well, as formats for teaching and learning, and as research platforms as well. Only few research contributions engage with understanding how accelerated design processes in game jams and hackathons unfold, or how the organisation of game jam and hackathon formats influence these accelerated design processes. The main contributions of my PhD project are: 1) Descriptive process-level knowledge, which contextualise and solidify how accelerated design processes unfold under the circumstances of a game jam and a hackathon. 2) Overviews of how game jams have been organised for supporting participants' creativity and of how hackathons have been used as means and as research focus within academia. 3) Exploring how game jam and hackathon formats may be organised in order to support knowledge generation such as within academia, and in order to support creativity.
A Finite-Range Search Formulation of Maximum Likelihood MIMO Detection for Coherent Ising Machines
Venue: arXiv cs.NI 2022
Year: 2022

The last couple of years have seen an emergence of physics-inspired computing for maximum likelihood MIMO detection. These methods involve transforming the MIMO detection problem into an Ising minimization problem, which can then be solved on an Ising Machine. Recent works have shown promising projections for MIMO wireless detection using Quantum Annealing optimizers and Coherent Ising Machines. While these methods perform very well for BPSK and 4-QAM, they struggle to provide good BER for 16-QAM and higher modulations. In this paper, we explore an enhanced CIM model, and propose a novel Ising formulation, which together are shown to be the first Ising solver that provides significant gains in the BER performance of large and massive MIMO systems, like $16\times16$ and $16\times32$, and sustain its performance gain even at 256-QAM modulation. We further perform a spectral efficiency analysis and show that, for a $16\times16$ MIMO with Adaptive Modulation and Coding, our method can provide substantial throughput gains over MMSE, achieving $2\times$ throughput for SNR $\leq25$ dB, and up to $1.5\times$ throughput for SNR $\geq 30$ dB.
Decisions in Continuous Integration and Delivery: An Exploratory Study
Venue: arXiv cs.SE 2022
Year: 2022

In recent years, Continuous Integration (CI) and Continuous Delivery (CD) has been heatedly discussed and widely used in part or all of the software development life cycle as the practices and pipeline to deliver software products in an efficient way. There are many tools, such as Travis CI, that offer various features to support the CI/CD pipeline, but there is a lack of understanding about what decisions are frequently made in CI/CD. In this work, we explored one popular open-source project on GitHub, Budibase, to provide insights on the types of decisions made in CI/CD from a practitioners' perspective. We first explored the GitHub Trending page, conducted a pilot repository extraction, and identified the Budibase repository as the case for our study. We then crawled all the closed issues from the repository and got 1,168 closed issues. Irrelevant issues were filtered out based on certain criteria, and 370 candidate issues that contain decisions were obtained for data extraction. We analyzed the issues using a hybrid approach combining pre-defined types and the Constant Comparison method to get the categories of decisions. The results show that the major type of decisions in the Budibase closed issues is Functional Requirement Decision (67.6%), followed by Architecture Decision (11.1%). Our findings encourage developers to put more effort on the issues and making decisions related to CI/CD, and provide researchers with a reference of decision classification made in CI/CD.
Classification and mapping of low-statured 'shrubland' cover types in post-agricultural landscapes of the US Northeast
Venue: arXiv cs.CV 2022
Year: 2022

Novel plant communities reshape landscapes and pose challenges for land cover classification and mapping that can constrain research and stewardship efforts. In the US Northeast, emergence of low-statured woody vegetation, or shrublands, instead of secondary forests in post-agricultural landscapes is well-documented by field studies, but poorly understood from a landscape perspective, which limits the ability to systematically study and manage these lands. To address gaps in classification/mapping of low-statured cover types where they have been historically rare, we developed models to predict shrubland distributions at 30m resolution across New York State (NYS), using a stacked ensemble combining a random forest, gradient boosting machine, and artificial neural network to integrate remote sensing of structural (airborne LIDAR) and optical (satellite imagery) properties of vegetation cover. We first classified a 1m canopy height model (CHM), derived from a patchwork of available LIDAR coverages, to define shrubland presence/absence. Next, these non-contiguous maps were used to train a model ensemble based on temporally-segmented imagery to predict shrubland probability for the entire study landscape (NYS). Approximately 2.5% of the CHM coverage area was classified as shrubland. Models using Landsat predictors trained on the classified CHM were effective at identifying shrubland (test set AUC=0.893, real-world AUC=0.904), in discriminating between shrub/young forest and other cover classes, and produced qualitatively sensible maps, even when extending beyond the original training data. Our results suggest that incorporation of airborne LiDAR, even from a discontinuous patchwork of coverages, can improve land cover classification of historically rare but increasingly prevalent shrubland habitats across broader areas.
Secure and Private Source Coding with Private Key and Decoder Side Information
Venue: arXiv cs.IT 2022
Year: 2022

The problem of secure source coding with multiple terminals is extended by considering a remote source whose noisy measurements are the correlated random variables used for secure source reconstruction. The main additions to the problem include 1) all terminals noncausally observe a noisy measurement of the remote source; 2) a private key is available to all legitimate terminals; 3) the public communication link between the encoder and decoder is rate-limited; and 4) the secrecy leakage to the eavesdropper is measured with respect to the encoder input, whereas the privacy leakage is measured with respect to the remote source. Exact rate regions are characterized for a lossy source coding problem with a private key, remote source, and decoder side information under security, privacy, communication, and distortion constraints. By replacing the distortion constraint with a reliability constraint, we obtain the exact rate region also for the lossless case. Furthermore, the lossy rate region for scalar discrete-time Gaussian sources and measurement channels is established.
Robustness of Humans and Machines on Object Recognition with Extreme Image Transformations
Venue: arXiv cs.CV 2022
Year: 2022

Recent neural network architectures have claimed to explain data from the human visual cortex. Their demonstrated performance is however still limited by the dependence on exploiting low-level features for solving visual tasks. This strategy limits their performance in case of out-of-distribution/adversarial data. Humans, meanwhile learn abstract concepts and are mostly unaffected by even extreme image distortions. Humans and networks employ strikingly different strategies to solve visual tasks. To probe this, we introduce a novel set of image transforms and evaluate humans and networks on an object recognition task. We found performance for a few common networks quickly decreases while humans are able to recognize objects with a high accuracy.
Weak Supervision with Incremental Source Accuracy Estimation
Venue: arXiv cs.LG 2022
Year: 2022

Motivated by the desire to generate labels for real-time data we develop a method to estimate the dependency structure and accuracy of weak supervision sources incrementally. Our method first estimates the dependency structure associated with the supervision sources and then uses this to iteratively update the estimated source accuracies as new data is received. Using both off-the-shelf classification models trained using publicly-available datasets and heuristic functions as supervision sources we show that our method generates probabilistic labels with an accuracy matching that of existing off-line methods.
Deep Depth Completion from Extremely Sparse Data: A Survey
Venue: arXiv cs.CV 2022
Year: 2022

Depth completion aims at predicting dense pixel-wise depth from an extremely sparse map captured from a depth sensor, e.g., LiDARs. It plays an essential role in various applications such as autonomous driving, 3D reconstruction, augmented reality, and robot navigation. Recent successes on the task have been demonstrated and dominated by deep learning based solutions. In this article, for the first time, we provide a comprehensive literature review that helps readers better grasp the research trends and clearly understand the current advances. We investigate the related studies from the design aspects of network architectures, loss functions, benchmark datasets, and learning strategies with a proposal of a novel taxonomy that categorizes existing methods. Besides, we present a quantitative comparison of model performance on three widely used benchmarks, including indoor and outdoor datasets. Finally, we discuss the challenges of prior works and provide readers with some insights for future research directions.
Improved maximin fair allocation of indivisible items to three agents
Venue: arXiv cs.GT 2022
Year: 2022

We consider the problem of approximate maximin share (MMS) allocation of indivisible items among three agents with additive valuation functions. For goods, we show that an $\frac{11}{12}$ - MMS allocation always exists, improving over the previously known bound of $\frac{8}{9}$ . Moreover, in our allocation, we can prespecify an agent that is to receive her full proportional share (PS); we also present examples showing that for such allocations the ratio of $\frac{11}{12}$ is best possible. For chores, we show that a $\frac{19}{18}$-MMS allocation always exists. Also in this case, we can prespecify an agent that is to receive no more than her PS, and we present examples showing that for such allocations the ratio of $\frac{19}{18}$ is best possible.
Uptime-Optimized Cloud Architecture as a Brokered Service
Venue: arXiv cs.DC 2022
Year: 2022

Enterprise workloads usually call for an uptime service level agreement (SLA) at the pain of contractual penalty in the event of slippage. Often, the strategy is to introduce ad-hoc HA (High Availability) mechanisms in response. Implemented solutions that we surveyed do not mathematically map their availability model to the required uptime SLA and to any expected penalty payout. In most client cases that we observed, this either resulted in an over-engineered solution that had more redundancies than was required, or in an inadequate solution that could potentially slip on the system uptime SLA stipulated in the contract. In this paper, we propose a framework backed by a model, to automatically determine the HA-enabled solution with the least TCO (total cost of ownership) for a given uptime SLA and slippage penalty. We attempt to establish that our work is best implemented as a brokered service that recommends an uptime-optimized cloud architecture.
Compact and Efficient KEMs over NTRU Lattices
Venue: arXiv cs.CR 2022
Year: 2022

The NTRU lattice is a promising candidate to construct practical cryptosystems, in particular key encapsulation mechanism (KEM), resistant to quantum computing attacks. Nevertheless, there are still some inherent obstacles to NTRU-based KEM schemes in having integrated performance, taking security, bandwidth, error probability, and computational efficiency \emph{as a whole}, that is as good as and even better than their \{R,M\}LWE-based counterparts. In this work, we solve this problem by presenting a new family of NTRU-based KEM schemes, referred to as CTRU and CNTR. By bridging low-dimensional lattice codes and high-dimensional NTRU-lattice-based cryptography with careful design and analysis, to the best of our knowledge CTRU and CNTR are the first NTRU-based KEM schemes with scalable ciphertext compression via only one \emph{single} ciphertext polynomial, and are the first that could outperform \{R,M\}LWE-based KEM schemes in integrated performance. For instance, compared to Kyber that is currently the only standardized KEM by NIST, on the recommended parameter set CNTR-768 has about $12\%$ smaller ciphertext size while encapsulating 384-bit keys compared to the fixed 256-bit key size of Kyber, security strengthened by $(8,7)$ bits for classical and quantum security respectively, and significantly lower error probability ($2^{-230}$ of CNTR-768 vs. $2^{-164}$ of Kyber-768). In comparison with the state-of-the-art AVX2 implementation of Kyber-768, CNTR-768 is faster by 1.9X in KeyGen, 2.6X in Encaps, and 1.2X in Decaps, respectively. When compared to the NIST Round 3 finalist NTRU-HRSS, our CNTR-768 has about $15\%$ smaller ciphertext size, and the security is strengthened by $(55,49)$ bits for classical and quantum security respectively. As for the AVX2 implementation, CNTR-768 is faster than NTRU-HRSS by 19X in KeyGen, 2.3X in Encaps, and 1.6X in Decaps, respectively.
"If it didn't happen, why would I change my decision?": How Judges Respond to Counterfactual Explanations for the Public Safety Assessment
Venue: arXiv cs.HC 2022
Year: 2022

Many researchers and policymakers have expressed excitement about algorithmic explanations enabling more fair and responsible decision-making. However, recent experimental studies have found that explanations do not always improve human use of algorithmic advice. In this study, we shed light on how people interpret and respond to counterfactual explanations (CFEs) -- explanations that show how a model's output would change with marginal changes to its input(s) -- in the context of pretrial risk assessment instruments (PRAIs). We ran think-aloud trials with eight sitting U.S. state court judges, providing them with recommendations from a PRAI that includes CFEs. We found that the CFEs did not alter the judges' decisions. At first, judges misinterpreted the counterfactuals as real -- rather than hypothetical -- changes to defendants. Once judges understood what the counterfactuals meant, they ignored them, stating their role is only to make decisions regarding the actual defendant in question. The judges also expressed a mix of reasons for ignoring or following the advice of the PRAI without CFEs. These results add to the literature detailing the unexpected ways in which people respond to algorithms and explanations. They also highlight new challenges associated with improving human-algorithm collaborations through explanations.
ALIGNMEET: A Comprehensive Tool for Meeting Annotation, Alignment, and Evaluation
Venue: arXiv cs.CL 2022
Year: 2022

Summarization is a challenging problem, and even more challenging is to manually create, correct, and evaluate the summaries. The severity of the problem grows when the inputs are multi-party dialogues in a meeting setup. To facilitate the research in this area, we present ALIGNMEET, a comprehensive tool for meeting annotation, alignment, and evaluation. The tool aims to provide an efficient and clear interface for fast annotation while mitigating the risk of introducing errors. Moreover, we add an evaluation mode that enables a comprehensive quality evaluation of meeting minutes. To the best of our knowledge, there is no such tool available. We release the tool as open source. It is also directly installable from PyPI.
A polynomial time algorithm for local testability and its level
Venue: arXiv cs.FL 2022
Year: 2022

A locally testable semigroup S is a semigroup with the property that for some nonnegative integer k, called the order or level of local testability, two words u and v in some set of generators for semigroup S are equal in the semigroup if (1) the prefix and suffix of the words of length k coincide, and (2) the set of intermediate substrings of length k of the words coincide. The local testability problem for semigroups is, given a finite semigroup, to decide, if the semigroup is locally testable or not. Recently, we introduced a polynomial time algorithm for the local testability problem and to find the level of local testability for semigroups based on our previous description of identities of $k$-testable semigroups and the structure of locally testable semigroups. The first part of the algorithm we introduce solves the local testability problem. The second part of the algorithm finds the order of local testability of a semigroup. The algorithm is of quadratic order where n is the order of the semigroup.
Symphony Generation with Permutation Invariant Language Model
Venue: arXiv cs.SD 2022
Year: 2022

In this work, we propose a permutation invariant language model, SymphonyNet, as a solution for symbolic symphony music generation. We propose a novel Multi-track Multi-instrument Repeatable (MMR) representation for symphonic music and model the music sequence using a Transformer-based auto-regressive language model with specific 3-D positional embedding. To overcome length overflow when modeling extra-long symphony tokens, we also propose a modified Byte Pair Encoding algorithm (Music BPE) for music tokens and introduce a novel linear transformer decoder architecture as a backbone. Meanwhile, we train the decoder to learn automatic orchestration as a joint task by masking instrument information from the input. We also introduce a large-scale symbolic symphony dataset for the advance of symphony generation research. Empirical results show that the proposed approach can generate coherent, novel, complex and harmonious symphony as a pioneer solution for multi-track multi-instrument symbolic music generation.