OpenRaiser/Intern-Atlas huggingface dataset:
Security and Privacy of Lightning Network Payments with Uncertain Channel Balances
Venue: arXiv cs.CR 2021
Year: 2021

The Lightning Network (LN) is a prominent payment channel network aimed at addressing Bitcoin's scalability issues. Due to the privacy of channel balances, senders cannot reliably choose sufficiently liquid payment paths and resort to a trial-and-error approach, trying multiple paths until one succeeds. This leaks private information and decreases payment reliability, which harms the user experience. This work focuses on the reliability and privacy of LN payments. We create a probabilistic model of the payment process in the LN, accounting for the uncertainty of the channel balances. This enables us to express payment success probabilities for a given payment amount and a path. Applying negative Bernoulli trials for single- and multi-part payments allows us to compute the expected number of payment attempts for a given amount, sender, and receiver. As a consequence, we analytically derive the optimal number of parts into which one should split a payment to minimize the expected number of attempts. This methodology allows us to define service level objectives and quantify how much private information leaks to the sender as a side effect of payment attempts. We propose an optimized path selection algorithm that does not require a protocol upgrade. Namely, we suggest that nodes prioritize paths that are most likely to succeed while making payment attempts. A simulation based on the real-world LN topology shows that this method reduces the average number of payment attempts by 20% compared to a baseline algorithm similar to the ones used in practice. This improvement will increase to 48% if the LN protocol is upgraded to implement the channel rebalancing proposal described in BOLT14.
iWarded: A System for Benchmarking Datalog+/- Reasoning (technical report)
Venue: arXiv cs.DB 2021
Year: 2021

Recent years have seen increasing popularity of logic-based reasoning systems, with research and industrial interest as well as many flourishing applications in the area of Knowledge Graphs. Despite that, one can observe a substantial lack of specific tools able to generate nontrivial reasoning settings and benchmark scenarios. As a consequence, evaluating, analysing and comparing reasoning systems is a complex task, especially when they embody sophisticated optimizations and execution techniques that leverage the theoretical underpinnings of the adopted logic fragment. In this paper, we aim at filling this gap by introducing iWarded, a system that can generate very large, complex, realistic reasoning settings to be used for the benchmarking of logic-based reasoning systems adopting Datalog+/-, a family of extensions of Datalog that has seen a resurgence in the last few years. In particular, iWarded generates reasoning settings for Warded Datalog+/-, a language with a very good tradeoff between computational complexity and expressive power. In the paper, we present the iWarded system and a set of novel theoretical results adopted to generate effective scenarios. As Datalog-based languages are of general interest and see increasing adoption, we believe that iWarded is a step forward in the empirical evaluation of current and future systems.
Promise Problems Meet Pseudodeterminism
Venue: arXiv cs.CC 2021
Year: 2021

The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high probability. Recently, it was shown that such an algorithm would imply that every approximation algorithm can be made pseudodeterministic (Dixon, Pavan, Vinodchandran; ITCS 2021). The main conceptual contribution of this work is to establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally connected to the relationship between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence: every promise problem in PromiseBPP has a solution in BPP if and only if APEP has a pseudodeterministic algorithm. Based on this intuition, we show that pseudodeterministic algorithms for APEP can shed light on a few central topics in complexity theory such as circuit lowerbounds, probabilistic hierarchy theorems, and multi-pseudodeterminism.
Competitive Equilibria with Unequal Budgets: Supporting Arbitrary Pareto Optimal Allocations
Venue: arXiv cs.GT 2021
Year: 2021

We consider a market setting of agents with additive valuations over heterogeneous divisible resources. Agents are assigned a budget of tokens (possibly unequal budgets) they can use to obtain resources; leftover tokens are worthless. We show how to support any Pareto efficient allocation in equilibrium, using anonymous resource prices and agent specific budgets. We also give computationally efficient algorithms for those tasks. In particular, this allows us to support the Rawlsian max-min allocation.
UPANets: Learning from the Universal Pixel Attention Networks
Venue: arXiv cs.CV 2021
Year: 2021

Among image classification, skip and densely-connection-based networks have dominated most leaderboards. Recently, from the successful development of multi-head attention in natural language processing, it is sure that now is a time of either using a Transformer-like model or hybrid CNNs with attention. However, the former need a tremendous resource to train, and the latter is in the perfect balance in this direction. In this work, to make CNNs handle global and local information, we proposed UPANets, which equips channel-wise attention with a hybrid skip-densely-connection structure. Also, the extreme-connection structure makes UPANets robust with a smoother loss landscape. In experiments, UPANets surpassed most well-known and widely-used SOTAs with an accuracy of 96.47% in Cifar-10, 80.29% in Cifar-100, and 67.67% in Tiny Imagenet. Most importantly, these performances have high parameters efficiency and only trained in one customer-based GPU. We share implementing code of UPANets in https://github.com/hanktseng131415go/UPANets.
A Systematic Literature Review on Model-driven Engineering for Cyber-Physical Systems
Venue: arXiv cs.SE 2021
Year: 2021

This technical report presents a Systematic Literature Review (SLR) study that focuses on identifying and classifying the recent research practices pertaining to CPS development through MDE approaches. The study evaluates 140 research papers published during 2010-2018. Accordingly, a comprehensive analysis of various MDE approaches used in the development life-cycle of CPS is presented. Furthermore, the study identifies the research gaps and areas that need more investigation. The contribution helps researchers and practitioners to get an overall understanding of the research trends and existing challenges for further research/development.
Tukey Depth Histograms
Venue: arXiv cs.CG 2021
Year: 2021

The Tukey depth of a flat with respect to a point set is a concept that appears in many areas of discrete and computational geometry. In particular, the study of centerpoints, center transversals, Ham Sandwich cuts, or $k$-edges can all be phrased in terms of depths of certain flats with respect to one or more point sets. In this work, we introduce the Tukey depth histogram of $k$-flats in $\mathbb{R}^d$ with respect to a point set $P$, which is a vector $D^{k,d}(P)$, whose $i$'th entry $D^{k,d}_i(P)$ denotes the number of $k$-flats spanned by $k+1$ points of $P$ that have Tukey depth $i$ with respect to $P$. As our main result, we give a complete characterization of the depth histograms of points, that is, for any dimension $d$ we give a description of all possible histograms $D^{0,d}(P)$. This then allows us to compute the exact number of possible such histograms.
Cost-aware Integration Process Modeling in Multiclouds
Venue: arXiv cs.SE 2021
Year: 2021

Integration as a service (INTaaS) is the centrepiece of current corporate, cloud and device integration processes. Thereby, compositions of integration patterns denote the required integration logic as integration processes, currently running in single-clouds. While multicloud settings gain importance, their promised freedom of selecting the best option for a specific problem is currently not realized as well as security constraints are handled in a cost-intensive manner for the INTaaS vendors, leading to security vs. costs goal conflicts, and intransparent to the process modeler. In this work, we propose a design-time placement for processes in multiclouds that is cost-optimal for INTaaS problem sizes, and respects configurable security constraints of their customers. To make the solution tractable for larger, productive INTaaS processes, it is relaxed by using a local search heuristic, and complemented by correctness-preserving model decomposition. This allows for a novel perspective on cost-aware process modeling from a process modeler's perspective. The multicloud process placement is evaluated on real-world integration processes with respect to cost- and runtime-efficiency, and discusses interesting trade-offs. The process modeler's perspective is investigated based on a new cost-aware modeling process, featuring the interaction between the user and the INTaaS vendor through ad-hoc multicloud cost calculation and correctness-preserving, process cost reduction proposals.
Approximation metatheorems for classes with bounded expansion
Venue: arXiv cs.DM 2021
Year: 2021

We give a number of approximation metatheorems for monotone maximization problems expressible in the first-order logic, in substantially more general settings than the previously known. We obtain * constant-factor approximation algorithm in any class of graphs with bounded expansion, * a QPTAS in any class with strongly sublinear separators, and * a PTAS in any fractionally treewidth-fragile class (which includes all common classes with strongly sublinear separators. Moreover, our tools also give an exact subexponential-time algorithm in any class with strongly sublinear separators.
Growing 3D Artefacts and Functional Machines with Neural Cellular Automata
Venue: arXiv cs.LG 2021
Year: 2021

Neural Cellular Automata (NCAs) have been proven effective in simulating morphogenetic processes, the continuous construction of complex structures from very few starting cells. Recent developments in NCAs lie in the 2D domain, namely reconstructing target images from a single pixel or infinitely growing 2D textures. In this work, we propose an extension of NCAs to 3D, utilizing 3D convolutions in the proposed neural network architecture. Minecraft is selected as the environment for our automaton since it allows the generation of both static structures and moving machines. We show that despite their simplicity, NCAs are capable of growing complex entities such as castles, apartment blocks, and trees, some of which are composed of over 3,000 blocks. Additionally, when trained for regeneration, the system is able to regrow parts of simple functional machines, significantly expanding the capabilities of simulated morphogenetic systems. The code for the experiment in this paper can be found at: https://github.com/real-itu/3d-artefacts-nca.
Please Don't Go -- A Comprehensive Approach to Increase Women's Participation in Open Source Software
Venue: arXiv cs.SE 2021
Year: 2021

Women represent less than 24% of employees in the software development industry and experience various types of prejudice and bias. Despite various efforts to increase diversity and multi-gendered participation, women are even more underrepresented in Open Source Software (OSS) projects. In my PhD, I investigate the following question: How can OSS communities increase women's participation in their projects? I will identify different OSS career pathways and develop a holistic view of women's motivations to join or leave OSS, as well as their definitions of success. Based on this empirical investigation, I will work together with the Linux Foundation to design attraction and retention strategies focused on women. Before and after implementing the strategies, I will conduct empirical studies to evaluate the state of the practice and understand the implications of the strategies.
dictNN: A Dictionary-Enhanced CNN Approach for Classifying Hate Speech on Twitter
Venue: arXiv cs.CL 2021
Year: 2021

Hate speech on social media is a growing concern, and automated methods have so far been sub-par at reliably detecting it. A major challenge lies in the potentially evasive nature of hate speech due to the ambiguity and fast evolution of natural language. To tackle this, we introduce a vectorisation based on a crowd-sourced and continuously updated dictionary of hate words and propose fusing this approach with standard word embedding in order to improve the classification performance of a CNN model. To train and test our model we use a merge of two established datasets (110,748 tweets in total). By adding the dictionary-enhanced input, we are able to increase the CNN model's predictive power and increase the F1 macro score by seven percentage points.
Multi-Robot Routing with Time Windows: A Column Generation Approach
Venue: arXiv cs.RO 2021
Year: 2021

Robots performing tasks in warehouses provide the first example of wide-spread adoption of autonomous vehicles in transportation and logistics. The efficiency of these operations, which can vary widely in practice, are a key factor in the success of supply chains. In this work we consider the problem of coordinating a fleet of robots performing picking operations in a warehouse so as to maximize the net profit achieved within a time period while respecting problem- and robot-specific constraints. We formulate the problem as a weighted set packing problem where the elements in consideration are items on the warehouse floor that can be picked up and delivered within specified time windows. We enforce the constraint that robots must not collide, that each item is picked up and delivered by at most one robot, and that the number of robots active at any time does not exceed the total number available. Since the set of routes is exponential in the size of the input, we attack optimization of the resulting integer linear program using column generation, where pricing amounts to solving an elementary resource-constrained shortest-path problem. We propose an efficient optimization scheme that avoids consideration of every increment within the time windows. We also propose a heuristic pricing algorithm that can efficiently solve the pricing subproblem. While this itself is an important problem, the insights gained from solving these problems effectively can lead to new advances in other time-widow constrained vehicle routing problems.
Intelligent Stretch Reduction in Information-CentricNetworking towards 5G-Tactile Internet realization
Venue: arXiv cs.NI 2021
Year: 2021

In recent years, 5G is widely used in parallel with IoT networks to enable massive data connectivity and exchange with ultra-reliable and low latency communication (URLLC) services. The internet requirements from user's perspective have shifted from simple human to human interactions to different communication paradigms and information-centric networking (ICN). ICN distributes the content among the users based on their trending requests. ICN is responsible not only for the routing and caching but also for naming the network's content. ICN considers several parameters such as cache-hit ratio, content diversity, content redundancy, and stretch to route the content. ICN enables name-based caching of the required content according to the user's request based on the router's interest table. The stretch shows the path covered while retrieving the content from producer to consumer. Reduction in path length also leads to a reduction in end-to-end latency and better data rate availability. ICN routers must have the minimum stretch to obtain a better system efficiency. Reinforcement learning (RL) is widely used in networks environment to increase agent efficiency to make decisions. In ICN, RL can aid to increase caching and stretch efficiency. This paper investigates a stretch reduction strategy for ICN routers by formulating the stretch reduction problem as a Markov decision process. The evaluation of the proposed stretch reduction strategy's accuracy is done by employing Q-Learning, an RL technique. The simulation results indicate that by using the optimal parameters for the proposed stretch reduction strategy.
LabelGit: A Dataset for Software Repositories Classification using Attributed Dependency Graphs
Venue: arXiv cs.SE 2021
Year: 2021

Software repository hosting services contain large amounts of open-source software, with GitHub hosting more than 100 million repositories, from new to established ones. Given this vast amount of projects, there is a pressing need for a search based on the software's content and features. However, even though GitHub offers various solutions to aid software discovery, most repositories do not have any labels, reducing the utility of search and topic-based analysis. Moreover, classifying software modules is also getting more importance given the increase in Component-Based Software Development. However, previous work focused on software classification using keyword-based approaches or proxies for the project (e.g., README), which is not always available. In this work, we create a new annotated dataset of GitHub Java projects called LabelGit. Our dataset uses direct information from the source code, like the dependency graph and source code neural representations from the identifiers. Using this dataset, we hope to aid the development of solutions that do not rely on proxies but use the entire source code to perform classification.
From Innovations to Prospects: What Is Hidden Behind Cryptocurrencies?
Venue: arXiv cs.SE 2021
Year: 2021

The great influence of Bitcoin has promoted the rapid development of blockchain-based digital currencies, especially the altcoins, since 2013. However, most altcoins share similar source codes, resulting in concerns about code innovations. In this paper, an empirical study on existing altcoins is carried out to offer a thorough understanding of various aspects associated with altcoin innovations. Firstly, we construct the dataset of altcoins, including source code repositories, GitHub fork relations, and market capitalizations (cap). Then, we analyze the altcoin innovations from the perspective of source code similarities. The results demonstrate that more than 85% of altcoin repositories present high code similarities. Next, a temporal clustering algorithm is proposed to mine the inheritance relationship among various altcoins. The family pedigrees of altcoin are constructed, in which the altcoin presents similar evolution features as biology, such as power-law in family size, variety in family evolution, etc. Finally, we investigate the correlation between code innovations and market capitalization. Although we fail to predict the price of altcoins based on their code similarities, the results show that altcoins with higher innovations reflect better market prospects.
Data Mining and Visualization to Understand Accident-prone Areas
Venue: arXiv cs.CY 2021
Year: 2021

In this study, we present both data mining and information visualization techniques to identify accident-prone areas, most accident-prone time, day, and month. Also, we surveyed among volunteers to understand which visualization techniques help non-expert users to understand the findings better. Findings of this study suggest that most accidents occur in the dusk (i.e., between 6 to 7 pm), and on Fridays. Results also suggest that most accidents occurred in October, which is a popular month for tourism. These findings are consistent with social information and can help policymakers, residents, tourists, and other law enforcement agencies. This study can be extended to draw broader implications.
Predicting Early Dropout: Calibration and Algorithmic Fairness Considerations
Venue: arXiv cs.LG 2021
Year: 2021

In this work, the problem of predicting dropout risk in undergraduate studies is addressed from a perspective of algorithmic fairness. We develop a machine learning method to predict the risks of university dropout and underperformance. The objective is to understand if such a system can identify students at risk while avoiding potential discriminatory biases. When modeling both risks, we obtain prediction models with an Area Under the ROC Curve (AUC) of 0.77-0.78 based on the data available at the enrollment time, before the first year of studies starts. This data includes the students' demographics, the high school they attended, and their admission (average) grade. Our models are calibrated: they produce estimated probabilities for each risk, not mere scores. We analyze if this method leads to discriminatory outcomes for some sensitive groups in terms of prediction accuracy (AUC) and error rates (Generalized False Positive Rate, GFPR, or Generalized False Negative Rate, GFNR). The models exhibit some equity in terms of AUC and GFNR along groups. The similar GFNR means a similar probability of failing to detect risk for students who drop out. The disparities in GFPR are addressed through a mitigation process that does not affect the calibration of the model.
A Polynomial-Time Algorithm for Special Cases of the Unbounded Subset-Sum Problem
Venue: arXiv cs.DS 2021
Year: 2021

The Unbounded Subset-Sum Problem (USSP) is defined as: given sum $s$ and a set of integers $W\leftarrow \{p_1,\dots,p_n\}$ output a set of non-negative integers $\{y_1,\dots,y_n\}$ such that $p_1y_1+\dots+p_ny_n=s$. The USSP is an NP-complete problem that does not have any known polynomial-time solution. There is a pseudo-polynomial algorithm for the USSP problem with $O((p_{1})^{2}+n)$ time complexity and $O(p_{1})$ memory complexity, where $p_{1}$ is the smallest element of $W$ \cite{PH}. This algorithm is polynomial in term of the number of inputs, but exponential in the size of $p_1$. Therefore, this solution is impractical for the large-scale problems. In this paper, first we propose an efficient polynomial-time algorithm with $O(n)$ computational complexity for solving the specific case of the USSP where $ s> \sum_{i=1}^{k-1}q_iq_{i+1}-q_i-q_{i+1}$, $q_i$'s are the elements of a small subset of $W$ in which $gcd$ of its elements divides $s$ and $2\le k \le n$. Second, we present another algorithm for smaller values of $s$ with $O(n^2)$ computational complexity that finds the answer for some inputs with a probability between $0.5$ to $1$. Its success probability is directly related to the number of subsets of $W$ in which $gcd$ of their elements divides $s$. This algorithm can solve the USSP problem with large inputs in the polynomial-time, no matter how big inputs are, but, in some special cases where $s$ is small, it cannot find the answer.