OpenRaiser/Intern-Atlas huggingface dataset:
Summarizing and Analyzing the Privacy-Preserving Techniques in Bitcoin and other Cryptocurrencies
Venue: arXiv cs.CR 2024
Year: 2024

Bitcoin and many other similar Cryptocurrencies have been in existence for over a decade, prominently focusing on decentralized, pseudo-anonymous ledger-based transactions. Many protocol improvements and changes have resulted in new variants of Cryptocurrencies that are known for their peculiar characteristics. For instance, Storjcoin is a Proof-of-Storage-based Cryptocurrency that incentivizes its peers based on the amount of storage owned by them. Cryptocurrencies like Monero strive for user privacy by using privacy-centric cryptographic algorithms. While Cryptocurrencies strive to maintain peer transparency by making the transactions and the entire ledger public, user privacy is compromised at times. Monero and many other privacy-centric Cryptocurrencies have significantly improved from the original Bitcoin protocol after several problems were found in the protocol. Most of these deficiencies were related to the privacy of users. Even though Bitcoin claims to have pseudo-anonymous user identities, many attacks have managed to successfully de-anonymize users. In this paper, we present some well-known attacks and analysis techniques that have compromised the privacy of Bitcoin and many other similar Cryptocurrencies. We also analyze and study different privacy-preserving algorithms and the problems these algorithms manage to solve. Lastly, we touch upon the ethics, impact, legality, and acceptance of imposing these privacy algorithms.
Trillium: Higher-Order Concurrent and Distributed Separation Logic for Intensional Refinement
Venue: arXiv cs.PL 2024
Year: 2024

Expressive state-of-the-art separation logics rely on step-indexing to model semantically complex features and to support modular reasoning about imperative higher-order concurrent and distributed programs. Step-indexing comes, however, with an inherent cost: it restricts the adequacy theorem of program logics to a fairly simple class of safety properties. In this paper, we explore if and how intensional refinement is a viable methodology for strengthening higher-order concurrent (and distributed) separation logic to prove non-trivial safety and liveness properties. Specifically, we introduce Trillium, a language-agnostic separation logic framework for showing intensional refinement relations between traces of a program and a model. We instantiate Trillium with a concurrent language and develop Fairis, a concurrent separation logic, that we use to show liveness properties of concurrent programs under fair scheduling assumptions through a fair liveness-preserving refinement of a model. We also instantiate Trillium with a distributed language and obtain an extension of Aneris, a distributed separation logic, which we use to show refinement relations between distributed systems and TLA+ models.
MFE-NER: Multi-feature Fusion Embedding for Chinese Named Entity Recognition
Venue: arXiv cs.CL 2024
Year: 2024

In Chinese Named Entity Recognition, character substitution is a complicated linguistic phenomenon. Some Chinese characters are quite similar as they share the same components or have similar pronunciations. People replace characters in a named entity with similar characters to generate a new collocation but referring to the same object. As a result, it always leads to unrecognizable or mislabeling errors in the NER task. In this paper, we propose a lightweight method, MFE-NER, which fuses glyph and phonetic features, to help pre-trained language models handle the character substitution problem in the NER task with limited extra cost. Basically, in the glyph domain, we disassemble Chinese characters into Five-Stroke components to represent structure features. In the phonetic domain, an improved phonetic system is proposed in our work, making it reasonable to describe phonetic similarity among Chinese characters. Experiments demonstrate that our method performs especially well in detecting character substitutions while slightly improving the overall performance of Chinese NER.
From the Beginning: Key Transitions in the First 15 Years of DNSSEC
Venue: arXiv cs.CR 2024
Year: 2024

When the global rollout of the DNS Security Extensions (DNSSEC) began in 2005, a first-of-its-kind trial started: The complexity of a core Internet protocol was magnified in favor of better security for the overall Internet. Thereby, the scale of the loosely-federated delegation in DNS became an unprecedented cryptographic key management challenge. Though fundamental for current and future operational success, our community lacks a clear notion of how to empirically evaluate the process of securely transitioning keys. In this paper, we propose two building blocks to formally characterize and assess key transitions. First, the anatomy of key transitions, i.e., measurable and well-defined properties of key changes; and second, a novel classification model based on this anatomy for describing key transition practices in abstract terms. This abstraction allows for classifying operational behavior. We apply our proposed transition anatomy and transition classes to describe the global DNSSEC deployment. Specifically, we use measurements from the first 15 years of the DNSSEC rollout to detect and understand which key transitions have been used to what degree and which rates of errors and warnings occurred. In contrast to prior work, we consider all possible transitions and not only 1:1 key rollovers. Our results show measurable gaps between prescribed key management processes and key transitions in the wild. We also find evidence that such noncompliant transitions are needed in operations.
Learning to be Fair: A Consequentialist Approach to Equitable Decision-Making
Venue: arXiv cs.LG 2024
Year: 2024

In an attempt to make algorithms fair, the machine learning literature has largely focused on equalizing decisions, outcomes, or error rates across race or gender groups. To illustrate, consider a hypothetical government rideshare program that provides transportation assistance to low-income people with upcoming court dates. Following this literature, one might allocate rides to those with the highest estimated treatment effect per dollar, while constraining spending to be equal across race groups. That approach, however, ignores the downstream consequences of such constraints, and, as a result, can induce unexpected harms. For instance, if one demographic group lives farther from court, enforcing equal spending would necessarily mean fewer total rides provided, and potentially more people penalized for missing court. Here we present an alternative framework for designing equitable algorithms that foregrounds the consequences of decisions. In our approach, one first elicits stakeholder preferences over the space of possible decisions and the resulting outcomes--such as preferences for balancing spending parity against court appearance rates. We then optimize over the space of decision policies, making trade-offs in a way that maximizes the elicited utility. To do so, we develop an algorithm for efficiently learning these optimal policies from data for a large family of expressive utility functions. In particular, we use a contextual bandit algorithm to explore the space of policies while solving a convex optimization problem at each step to estimate the best policy based on the available information. This consequentialist paradigm facilitates a more holistic approach to equitable decision-making.
Multi-Task Learning in Natural Language Processing: An Overview
Venue: arXiv cs.AI 2024
Year: 2024

Deep learning approaches have achieved great success in the field of Natural Language Processing (NLP). However, directly training deep neural models often suffer from overfitting and data scarcity problems that are pervasive in NLP tasks. In recent years, Multi-Task Learning (MTL), which can leverage useful information of related tasks to achieve simultaneous performance improvement on these tasks, has been used to handle these problems. In this paper, we give an overview of the use of MTL in NLP tasks. We first review MTL architectures used in NLP tasks and categorize them into four classes, including parallel architecture, hierarchical architecture, modular architecture, and generative adversarial architecture. Then we present optimization techniques on loss construction, gradient regularization, data sampling, and task scheduling to properly train a multi-task model. After presenting applications of MTL in a variety of NLP tasks, we introduce some benchmark datasets. Finally, we make a conclusion and discuss several possible research directions in this field.
Maximum Sum-Rank Distance Codes over Finite Chain Rings
Venue: arXiv cs.IT 2024
Year: 2024

In this work, maximum sum-rank distance (MSRD) codes and linearized Reed-Solomon codes are extended to finite chain rings. It is proven that linearized Reed-Solomon codes are MSRD over finite chain rings, extending the known result for finite fields. For the proof, several results on the roots of skew polynomials are extended to finite chain rings. These include the existence and uniqueness of minimum-degree annihilator skew polynomials and Lagrange interpolator skew polynomials. A general cubic-complexity sum-rank Welch-Berlekamp decoder and a quadratic-complexity sum-rank syndrome decoder (under some assumptions) are then provided over finite chain rings. The latter also constitutes the first known syndrome decoder for linearized Reed--Solomon codes over finite fields. Finally, applications in Space-Time Coding with multiple fading blocks and physical-layer multishot Network Coding are discussed.
Well Googled is Half Done: Multimodal Forecasting of New Fashion Product Sales with Image-based Google Trends
Venue: arXiv cs.CV 2024
Year: 2024

New fashion product sales forecasting is a challenging problem that involves many business dynamics and cannot be solved by classical forecasting approaches. In this paper, we investigate the effectiveness of systematically probing exogenous knowledge in the form of Google Trends time series and combining it with multi-modal information related to a brand-new fashion item, in order to effectively forecast its sales despite the lack of past data. In particular, we propose a neural network-based approach, where an encoder learns a representation of the exogenous time series, while the decoder forecasts the sales based on the Google Trends encoding and the available visual and metadata information. Our model works in a non-autoregressive manner, avoiding the compounding effect of large first-step errors. As a second contribution, we present VISUELLE, a publicly available dataset for the task of new fashion product sales forecasting, containing multimodal information for 5577 real, new products sold between 2016-2019 from Nunalie, an Italian fast-fashion company. The dataset is equipped with images of products, metadata, related sales, and associated Google Trends. We use VISUELLE to compare our approach against state-of-the-art alternatives and several baselines, showing that our neural network-based approach is the most accurate in terms of both percentage and absolute error. It is worth noting that the addition of exogenous knowledge boosts the forecasting accuracy by 1.5% in terms of Weighted Absolute Percentage Error (WAPE), revealing the importance of exploiting informative external information. The code and dataset are both available at https://github.com/HumaticsLAB/GTM-Transformer.
Generalized minimum 0-extension problem and discrete convexity
Venue: arXiv cs.CC 2024
Year: 2024

Given a fixed finite metric space $(V,μ)$, the {\em minimum $0$-extension problem}, denoted as ${\tt 0\mbox{-}Ext}[μ]$, is equivalent to the following optimization problem: minimize function of the form $\min\limits_{x\in V^n} \sum_i f_i(x_i) + \sum_{ij}c_{ij}μ(x_i,x_j)$ where $c_{ij},c_{vi}$ are given nonnegative costs and $f_i:V\rightarrow \mathbb R$ are functions given by $f_i(x_i)=\sum_{v\in V}c_{vi}μ(x_i,v)$. The computational complexity of ${\tt 0\mbox{-}Ext}[μ]$ has been recently established by Karzanov and by Hirai: if metric $μ$ is {\em orientable modular} then ${\tt 0\mbox{-}Ext}[μ]$ can be solved in polynomial time, otherwise ${\tt 0\mbox{-}Ext}[μ]$ is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as $L^\natural$-convex functions. We consider a more general version of the problem in which unary functions $f_i(x_i)$ can additionally have terms of the form $c_{uv;i}μ(x_i,\{u,v\})$ for $\{u,v\}\in F$, where set $F\subseteq\binom{V}{2}$ is fixed. We extend the complexity classification above by providing an explicit condition on $(μ,F)$ for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving ${\tt 0\mbox{-}Ext}[μ]$ on orientable modular graphs.
Fine-grained Meta-Theorems for Vertex Integrity
Venue: arXiv cs.CC 2024
Year: 2024

Vertex Integrity is a graph measure which sits squarely between two more well-studied notions, namely vertex cover and tree-depth, and that has recently gained attention as a structural graph parameter. In this paper we investigate the algorithmic trade-offs involved with this parameter from the point of view of algorithmic meta-theorems for First-Order (FO) and Monadic Second Order (MSO) logic. Our positive results are the following: (i) given a graph $G$ of vertex integrity $k$ and an FO formula $ϕ$ with $q$ quantifiers, deciding if $G$ satisfies $ϕ$ can be done in time $2^{O(k^2q+q\log q)}+n^{O(1)}$; (ii) for MSO formulas with $q$ quantifiers, the same can be done in time $2^{2^{O(k^2+kq)}}+n^{O(1)}$. Both results are obtained using kernelization arguments, which pre-process the input to sizes $2^{O(k^2)}q$ and $2^{O(k^2+kq)}$ respectively. The complexities of our meta-theorems are significantly better than the corresponding meta-theorems for tree-depth, which involve towers of exponentials. However, they are worse than the roughly $2^{O(kq)}$ and $2^{2^{O(k+q)}}$ complexities known for corresponding meta-theorems for vertex cover. To explain this deterioration we present two formula constructions which lead to fine-grained complexity lower bounds and establish that the dependence of our meta-theorems on $k$ is the best possible. More precisely, we show that it is not possible to decide FO formulas with $q$ quantifiers in time $2^{o(k^2q)}$, and that there exists a constant-size MSO formula which cannot be decided in time $2^{2^{o(k^2)}}$, both under the ETH. Hence, the quadratic blow-up in the dependence on $k$ is unavoidable and vertex integrity has a complexity for FO and MSO logic which is truly intermediate between vertex cover and tree-depth.
Neural network relief: a pruning algorithm based on neural activity
Venue: arXiv cs.LG 2024
Year: 2024

Current deep neural networks (DNNs) are overparameterized and use most of their neuronal connections during inference for each task. The human brain, however, developed specialized regions for different tasks and performs inference with a small fraction of its neuronal connections. We propose an iterative pruning strategy introducing a simple importance-score metric that deactivates unimportant connections, tackling overparameterization in DNNs and modulating the firing patterns. The aim is to find the smallest number of connections that is still capable of solving a given task with comparable accuracy, i.e. a simpler subnetwork. We achieve comparable performance for LeNet architectures on MNIST, and significantly higher parameter compression than state-of-the-art algorithms for VGG and ResNet architectures on CIFAR-10/100 and Tiny-ImageNet. Our approach also performs well for the two different optimizers considered -- Adam and SGD. The algorithm is not designed to minimize FLOPs when considering current hardware and software implementations, although it performs reasonably when compared to the state of the art.
Reinforced Natural Language Interfaces via Entropy Decomposition
Venue: arXiv cs.HC 2024
Year: 2024

In this paper, we study the technical problem of developing conversational agents that can quickly adapt to unseen tasks, learn task-specific communication tactics, and help listeners finish complex, temporally extended tasks. We find that the uncertainty of language learning can be decomposed to an entropy term and a mutual information term, corresponding to the structural and functional aspect of language, respectively. Combined with reinforcement learning, our method automatically requests human samples for training when adapting to new tasks and learns communication protocols that are succinct and helpful for task completion. Human and simulation test results on a referential game and a 3D navigation game prove the effectiveness of the proposed method.
Pushing on Text Readability Assessment: A Transformer Meets Handcrafted Linguistic Features
Venue: arXiv cs.CL 2024
Year: 2024

We report two essential improvements in readability assessment: 1. three novel features in advanced semantics and 2. the timely evidence that traditional ML models (e.g. Random Forest, using handcrafted features) can combine with transformers (e.g. RoBERTa) to augment model performance. First, we explore suitable transformers and traditional ML models. Then, we extract 255 handcrafted linguistic features using self-developed extraction software. Finally, we assemble those to create several hybrid models, achieving state-of-the-art (SOTA) accuracy on popular datasets in readability assessment. The use of handcrafted features help model performance on smaller datasets. Notably, our RoBERTA-RF-T1 hybrid achieves the near-perfect classification accuracy of 99%, a 20.3% increase from the previous SOTA.
Time Encoding Quantization of Bandlimited and Finite-Rate-of-Innovation Signals
Venue: arXiv cs.IT 2024
Year: 2024

This paper studies the impact of quantization in integrate-and-fire time encoding machine (IF-TEM) sampler used for bandlimited (BL) and finite-rate-of-innovation (FRI) signals. An upper bound is derived for the mean squared error (MSE) of IF-TEM sampler and is compared against that of classical analog-to-digital converters (ADCs) with uniform sampling and quantization. The interplay between a signal's energy, bandwidth, and peak amplitude is used to identify how the MSE of IF-TEM sampler with quantization is influenced by these parameters. More precisely, the quantization step size of the IF-TEM sampler can be reduced when the maximum frequency of a bandlimited signal or the number of pulses of an FRI signal is increased. Leveraging this insight, specific parameter settings are identified for which the quantized IF-TEM sampler achieves an MSE bound that is roughly 8 dB lower than that of a classical ADC with the same number of bits. Experimental results validate the theoretical conclusions.
A Systematic Survey of Blockchained Federated Learning
Venue: arXiv cs.CR 2024
Year: 2024

With the technological advances in machine learning, effective ways are available to process the huge amount of data generated in real life. However, issues of privacy and scalability will constrain the development of machine learning. Federated learning (FL) can prevent privacy leakage by assigning training tasks to multiple clients, thus separating the central server from the local devices. However, FL still suffers from shortcomings such as single-point-failure and malicious data. The emergence of blockchain provides a secure and efficient solution for the deployment of FL. In this paper, we conduct a comprehensive survey of the literature on blockchained FL (BCFL). First, we investigate how blockchain can be applied to federal learning from the perspective of system composition. Then, we analyze the concrete functions of BCFL from the perspective of mechanism design and illustrate what problems blockchain addresses specifically for FL. We also survey the applications of BCFL in reality. Finally, we discuss some challenges and future research directions.
MetaCOG: A Hierarchical Probabilistic Model for Learning Meta-Cognitive Visual Representations
Venue: arXiv cs.AI 2024
Year: 2024

Humans have the capacity to question what we see and to recognize when our vision is unreliable (e.g., when we realize that we are experiencing a visual illusion). Inspired by this capacity, we present MetaCOG: a hierarchical probabilistic model that can be attached to a neural object detector to monitor its outputs and determine their reliability. MetaCOG achieves this by learning a probabilistic model of the object detector's performance via Bayesian inference -- i.e., a meta-cognitive representation of the network's propensity to hallucinate or miss different object categories. Given a set of video frames processed by an object detector, MetaCOG performs joint inference over the underlying 3D scene and the detector's performance, grounding inference on a basic assumption of object permanence. Paired with three neural object detectors, we show that MetaCOG accurately recovers each detector's performance parameters and improves the overall system's accuracy. We additionally show that MetaCOG is robust to varying levels of error in object detector outputs, showing proof-of-concept for a novel approach to the problem of detecting and correcting errors in vision systems when ground-truth is not available.
Efficient GPU implementation of randomized SVD and its applications
Venue: arXiv cs.LG 2024
Year: 2024

Matrix decompositions are ubiquitous in machine learning, including applications in dimensionality reduction, data compression and deep learning algorithms. Typical solutions for matrix decompositions have polynomial complexity which significantly increases their computational cost and time. In this work, we leverage efficient processing operations that can be run in parallel on modern Graphical Processing Units (GPUs), predominant computing architecture used e.g. in deep learning, to reduce the computational burden of computing matrix decompositions. More specifically, we reformulate the randomized decomposition problem to incorporate fast matrix multiplication operations (BLAS-3) as building blocks. We show that this formulation, combined with fast random number generators, allows to fully exploit the potential of parallel processing implemented in GPUs. Our extensive evaluation confirms the superiority of this approach over the competing methods and we release the results of this research as a part of the official CUDA implementation (https://docs.nvidia.com/cuda/cusolver/index.html).
The core of housing markets from an agent's perspective: Is it worth sprucing up your home?
Venue: arXiv cs.GT 2024
Year: 2024

We study housing markets as introduced by Shapley and Scarf (1974). We investigate the computational complexity of various questions regarding the situation of an agent $a$ in a housing market $H$: we show that it is $\mathsf{NP}$-hard to find an allocation in the core of $H$ where (i) $a$ receives a certain house, (ii) $a$ does not receive a certain house, or (iii) $a$ receives a house other than her own. We prove that the core of housing markets respects improvement in the following sense: given an allocation in the core of $H$ where agent $a$ receives a house $h$, if the value of the house owned by $a$ increases, then the resulting housing market admits an allocation in its core in which $a$ receives either $h$, or a house that $a$ prefers to $h$; moreover, such an allocation can be found efficiently. We further show an analogous result in the Stable Roommates setting by proving that stable matchings in a one-sided market also respect improvement.