OpenRaiser/Intern-Atlas huggingface dataset:
A Contribution to the Defense of Liquid Democracy
Venue: arXiv cs.MA 2023
Year: 2023

Liquid democracy is a hybrid direct-representative decision making process that provides each voter with the option of either voting directly or to delegate their vote to another voter, i.e., to a representative of their choice. One of the proposed advantages of liquid democracy is that, in general, it is assumed that voters will delegate their vote to others that are better informed, which leads to more informed and better decisions. Considering an audience from various knowledge domains, we provide an accessible high-level analysis of a prominent critique of liquid democracy by Caragiannis and Micha. Caragiannis and Micha's critique contains three central topics: 1. Analysis using their $α$-delegation model, which does not assume delegation to the more informed; 2. Novel delegation network structures where it is advantageous to delegate to the less informed rather than the more informed; and 3. Due to NP hardness, the implied impracticability of a social network obtaining an optimal delegation structure. We show that in the real world, Caragiannis and Micha's critique of liquid democracy has little or no relevance. Respectively, our critique is based on: 1. The identification of incorrect $α$-delegation model assumptions; 2. A lack of novel delegation structures and their effect in a real-world implementation of liquid democracy, which would be guaranteed with constraints that sensibly distribute voting power; and 3. The irrelevance of an optimal delegation structure if the correct result is guaranteed regardless. We conclude that Caragiannis and Micha's critique has no significant negative relevance to the proposition of liquid democracy.
Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark
Venue: arXiv cs.LG 2023
Year: 2023

This paper introduces an efficient algorithm for persistence diagram computation, given an input piecewise linear scalar field $f$ defined on a $d$-dimensional simplicial complex $K$, with $d \leq 3$. Our work revisits the seminal algorithm "PairSimplices" [31], [103] with discrete Morse theory (DMT) [34], [80], which greatly reduces the number of input simplices to consider. Further, we also extend to DMT and accelerate the stratification strategy described in "PairSimplices" for the fast computation of the $0^{th}$ and $(d - 1)^{th}$ diagrams, noted $D_0(f)$ and $D_{d-1}(f)$. Minima-saddle persistence pairs ($D_0(f)$) and saddle-maximum persistence pairs ($D_{d-1}(f)$) are efficiently computed by processing, with a Union-Find, the unstable sets of $1$-saddles and the stable sets of $(d - 1)$-saddles. This fast pre-computation for the dimensions $0$ and $(d - 1)$ enables an aggressive specialization of [4] to the 3D case, which results in a drastic reduction of the number of input simplices for the computation of $D_1(f)$, the intermediate layer of the sandwich. Finally, we document several performance improvements via shared-memory parallelism. We provide an open-source implementation of our algorithm for reproducibility purposes. We also contribute a reproducible benchmark package, which exploits three-dimensional data from a public repository and compares our algorithm to a variety of publicly available implementations. Extensive experiments indicate that our algorithm improves by two orders of magnitude the time performance of the seminal "PairSimplices" algorithm it extends. Moreover, it also improves memory footprint and time performance over a selection of 14 competing approaches, with a substantial gain over the fastest available approaches, while producing a strictly identical output.
Weighted Average-convexity and Cooperative Games
Venue: arXiv cs.GT 2023
Year: 2023

We generalize the notion of convexity and average-convexity to the notion of weighted average-convexity. We show several results on the relation between weighted average-convexity and cooperative games. First, we prove that if a game is weighted average-convex, then the corresponding weighted Shapley value is in the core. Second, we exhibit necessary conditions for a communication TU-game to preserve the weighted average-convexity. Finally, we provide a complete characterization when the underlying graph is a priority decreasing tree.
Formally Unimodular Packings for the Gaussian Wiretap Channel
Venue: arXiv cs.IT 2023
Year: 2023

This paper introduces the family of lattice-like packings, which generalizes lattices, consisting of packings possessing periodicity and geometric uniformity. The subfamily of formally unimodular (lattice-like) packings is further investigated. It can be seen as a generalization of the unimodular and isodual lattices, and the Construction A formally unimodular packings obtained from formally self-dual codes are presented. Recently, lattice coding for the Gaussian wiretap channel has been considered. A measure called secrecy function was proposed to characterize the eavesdropper's probability of correctly decoding. The aim is to determine the global maximum value of the secrecy function, called (strong) secrecy gain. We further apply lattice-like packings to coset coding for the Gaussian wiretap channel and show that the family of formally unimodular packings shares the same secrecy function behavior as unimodular and isodual lattices. We propose a universal approach to determine the secrecy gain of a Construction A formally unimodular packing obtained from a formally self-dual code. From the weight distribution of a code, we provide a necessary condition for a formally self-dual code such that its Construction A formally unimodular packing is secrecy-optimal. Finally, we demonstrate that formally unimodular packings/lattices can achieve higher secrecy gain than the best-known unimodular lattices.
Semi-supervised Contrastive Outlier removal for Pseudo Expectation Maximization (SCOPE)
Venue: arXiv cs.LG 2023
Year: 2023

Semi-supervised learning is the problem of training an accurate predictive model by combining a small labeled dataset with a presumably much larger unlabeled dataset. Many methods for semi-supervised deep learning have been developed, including pseudolabeling, consistency regularization, and contrastive learning techniques. Pseudolabeling methods however are highly susceptible to confounding, in which erroneous pseudolabels are assumed to be true labels in early iterations, thereby causing the model to reinforce its prior biases and thereby fail to generalize to strong predictive performance. We present a new approach to suppress confounding errors through a method we describe as Semi-supervised Contrastive Outlier removal for Pseudo Expectation Maximization (SCOPE). Like basic pseudolabeling, SCOPE is related to Expectation Maximization (EM), a latent variable framework which can be extended toward understanding cluster-assumption deep semi-supervised algorithms. However, unlike basic pseudolabeling which fails to adequately take into account the probability of the unlabeled samples given the model, SCOPE introduces an outlier suppression term designed to improve the behavior of EM iteration given a discrimination DNN backbone in the presence of outliers. Our results show that SCOPE greatly improves semi-supervised classification accuracy over a baseline, and furthermore when combined with consistency regularization achieves the highest reported accuracy for the semi-supervised CIFAR-10 classification task using 250 and 4000 labeled samples. Moreover, we show that SCOPE reduces the prevalence of confounding errors during pseudolabeling iterations by pruning erroneous high-confidence pseudolabeled samples that would otherwise contaminate the labeled set in subsequent retraining iterations.
Equilibria and Convergence in Fire Sale Games
Venue: arXiv cs.GT 2023
Year: 2023

The complex interactions between algorithmic trading agents can have a severe influence on the functioning of our economy, as witnessed by recent banking crises and trading anomalies. A common phenomenon in these situations are fire sales, a contagious process of asset sales that trigger further sales. We study the existence and structure of equilibria in a game-theoretic model of fire sales. We prove that for a wide parameter range (e.g., convex price impact functions), equilibria exist and form a complete lattice. This is contrasted with a non-existence result for concave price impact functions. Moreover, we study the convergence of best-response dynamics towards equilibria when they exist. In general, best-response dynamics may cycle. However, in many settings they are guaranteed to converge to the socially optimal equilibrium when starting from a natural initial state. Moreover, we discuss a simplified variant of the dynamics that is less informationally demanding and converges to the same equilibria. We compare the dynamics in terms of convergence speed.
An $hp$-adaptive multi-element stochastic collocation method for surrogate modeling with information re-use
Venue: arXiv cs.CE 2023
Year: 2023

This paper introduces an $hp$-adaptive multi-element stochastic collocation method, which additionally allows to re-use existing model evaluations during either $h$- or $p$-refinement. The collocation method is based on weighted Leja nodes. After $h$-refinement, local interpolations are stabilized by adding and sorting Leja nodes on each newly created sub-element in a hierarchical manner. For $p$-refinement, the local polynomial approximations are based on total-degree or dimension-adaptive bases. The method is applied in the context of forward and inverse uncertainty quantification to handle non-smooth or strongly localised response surfaces. The performance of the proposed method is assessed in several test cases, also in comparison to competing methods.
An extension of process calculus for asynchronous communications between agents with epistemic states
Venue: arXiv cs.AI 2023
Year: 2023

It plays a central role in intelligent agent systems to model agent's epistemic state and its change. Asynchrony plays a key role in distributed systems, in which the messages transmitted may not be received instantly by the agents. To characterize asynchronous communications, asynchronous announcement logic (AAL) has been presented, which focuses on the logic laws of the change of epistemic state after receiving information. However AAL does not involve the interactive behaviours between an agent and its environment. Through enriching the well-known pi-calculus by adding the operators for passing basic facts and applying the well-known action model logic to describe agents' epistemic states, this paper presents the e-calculus to model epistemic interactions between agents with epistemic states. The e-calculus can be adopted to characterize synchronous and asynchronous communications between agents. To capture the asynchrony, a buffer pools is constructed to store the basic facts announced and each agent reads these facts from this buffer pool in some order. Based on the transmission of link names, the e-calculus is able to realize reading from this buffer pool in different orders. This paper gives two examples: one is to read in the order in which the announced basic facts are sent (First-in-first-out, FIFO), and the other is in an arbitrary order.
Towards Measuring Vulnerabilities and Exposures in Open-Source Packages
Venue: arXiv cs.SE 2023
Year: 2023

Much of the current software depends on open-source components, which in turn have complex dependencies on other open-source libraries. Vulnerabilities in open source therefore have potentially huge impacts. The goal of this work is to get a quantitative overview of the frequency and evolution of existing vulnerabilities in popular software repositories and package managers. To this end, we provide an up-to-date overview of the open source landscape and its most popular package managers, we discuss approaches to map entries of the Common Vulnerabilities and Exposures (CVE) list to open-source libraries and we show the frequency and distribution of existing CVE entries with respect to popular programming languages.
LViT: Language meets Vision Transformer in Medical Image Segmentation
Venue: arXiv cs.CV 2023
Year: 2023

Deep learning has been widely used in medical image segmentation and other aspects. However, the performance of existing medical image segmentation models has been limited by the challenge of obtaining sufficient high-quality labeled data due to the prohibitive data annotation cost. To alleviate this limitation, we propose a new text-augmented medical image segmentation model LViT (Language meets Vision Transformer). In our LViT model, medical text annotation is incorporated to compensate for the quality deficiency in image data. In addition, the text information can guide to generate pseudo labels of improved quality in the semi-supervised learning. We also propose an Exponential Pseudo label Iteration mechanism (EPI) to help the Pixel-Level Attention Module (PLAM) preserve local image features in semi-supervised LViT setting. In our model, LV (Language-Vision) loss is designed to supervise the training of unlabeled images using text information directly. For evaluation, we construct three multimodal medical segmentation datasets (image + text) containing X-rays and CT images. Experimental results show that our proposed LViT has superior segmentation performance in both fully-supervised and semi-supervised setting. The code and datasets are available at https://github.com/HUANGLIZI/LViT.
Verified Causal Broadcast with Liquid Haskell
Venue: arXiv cs.PL 2023
Year: 2023

Protocols to ensure that messages are delivered in causal order are a ubiquitous building block of distributed systems. For instance, distributed data storage systems can use causally ordered message delivery to ensure causal consistency, and CRDTs can rely on the existence of an underlying causally-ordered messaging layer to simplify their implementation. A causal delivery protocol ensures that when a message is delivered to a process, any causally preceding messages sent to the same process have already been delivered to it. While causal delivery protocols are widely used, verification of their correctness is less common, much less machine-checked proofs about executable implementations. We implemented a standard causal broadcast protocol in Haskell and used the Liquid Haskell solver-aided verification system to express and mechanically prove that messages will never be delivered to a process in an order that violates causality. We express this property using refinement types and prove that it holds of our implementation, taking advantage of Liquid Haskell's underlying SMT solver to automate parts of the proof and using its manual theorem-proving features for the rest. We then put our verified causal broadcast implementation to work as the foundation of a distributed key-value store.
3D-Aware Video Generation
Venue: arXiv cs.CV 2023
Year: 2023

Generative models have emerged as an essential building block for many image synthesis and editing tasks. Recent advances in this field have also enabled high-quality 3D or video content to be generated that exhibits either multi-view or temporal consistency. With our work, we explore 4D generative adversarial networks (GANs) that learn unconditional generation of 3D-aware videos. By combining neural implicit representations with time-aware discriminator, we develop a GAN framework that synthesizes 3D video supervised only with monocular videos. We show that our method learns a rich embedding of decomposable 3D structures and motions that enables new visual effects of spatio-temporal renderings while producing imagery with quality comparable to that of existing 3D or video GANs.
SoK: Content Moderation in Social Media, from Guidelines to Enforcement, and Research to Practice
Venue: arXiv cs.CY 2023
Year: 2023

Social media platforms have been establishing content moderation guidelines and employing various moderation policies to counter hate speech and misinformation. The goal of this paper is to study these community guidelines and moderation practices, as well as the relevant research publications, to identify the research gaps, differences in moderation techniques, and challenges that should be tackled by the social media platforms and the research community. To this end, we study and analyze fourteen most popular social media content moderation guidelines and practices, and consolidate them. We then introduce three taxonomies drawn from this analysis as well as covering over two hundred interdisciplinary research papers about moderation strategies. We identify the differences between the content moderation employed in mainstream and fringe social media platforms. Finally, we have in-depth applied discussions on both research and practical challenges and solutions.
Pre-stressed Bi-stable Hair Clip Mechanism for Faster Swimming Robots
Venue: arXiv cs.RO 2023
Year: 2023

Structural instability is a hazard that leads to catastrophic failure and is generally avoided through special designs. A trend, however, has emerged over the past decades pointing to the harnessing of mechanisms with instability. Inspired by the snapping of a hair clip, we are finessing the unique characteristics of the lateral-torsional buckling of beams and the snap-through of pre-buckled dome-like thin-wall structures in a new field: the in-plane prestressed mechanism. Analyses reveal how the 2D-3D assembly of an in-plane prestressed actuator (IPA) is achieved and how the post-buckling energy landscape is pictured. Combining them with soft robotics, we show that the inclusion of a bistable IPA can enormously enhance the performance of an underwater fish robot as well as inspire a finger-like soft gripper.
On graphs coverable by k shortest paths
Venue: arXiv cs.DM 2023
Year: 2023

We show that if the edges or vertices of an undirected graph $G$ can be covered by $k$ shortest paths, then the pathwidth of $G$ is upper-bounded by a single-exponential function of $k$. As a corollary, we prove that the problem Isometric Path Cover with Terminals (which, given a graph $G$ and a set of $k$ pairs of vertices called terminals, asks whether $G$ can be covered by $k$ shortest paths, each joining a pair of terminals) is FPT with respect to the number of terminals. The same holds for the similar problem Strong Geodetic Set with Terminals (which, given a graph $G$ and a set of $k$ terminals, asks whether there exist $\binom{k}{2}$ shortest paths covering $G$, each joining a distinct pair of terminals). Moreover, this implies that the related problems Isometric Path Cover and Strong Geodetic Set (defined similarly but where the set of terminals is not part of the input) are in XP with respect to parameter $k$.
CTrGAN: Cycle Transformers GAN for Gait Transfer
Venue: arXiv cs.CV 2023
Year: 2023

We introduce a novel approach for gait transfer from unconstrained videos in-the-wild. In contrast to motion transfer, the objective here is not to imitate the source's motions by the target, but rather to replace the walking source with the target, while transferring the target's typical gait. Our approach can be trained only once with multiple sources and is able to transfer the gait of the target from unseen sources, eliminating the need for retraining for each new source independently. Furthermore, we propose a novel metrics for gait transfer based on gait recognition models that enable to quantify the quality of the transferred gait, and show that existing techniques yield a discrepancy that can be easily detected. We introduce Cycle Transformers GAN (CTrGAN), that consist of a decoder and encoder, both Transformers, where the attention is on the temporal domain between complete images rather than the spatial domain between patches. Using a widely-used gait recognition dataset, we demonstrate that our approach is capable of producing over an order of magnitude more realistic personalized gaits than existing methods, even when used with sources that were not available during training. As part of our solution, we present a detector that determines whether a video is real or generated by our model.
Metaverse for Wireless Systems: Vision, Enablers, Architecture, and Future Directions
Venue: arXiv cs.NI 2023
Year: 2023

Recently, significant research efforts have been initiated to enable the next-generation, namely, the sixth-generation (6G) wireless systems. In this article, we present a vision of metaverse towards effectively enabling the development of 6G wireless systems. A metaverse will use virtual representation (e.g., digital twin), digital avatars, and interactive experience technologies (e.g., extended reality) to assist analyses, optimizations, and operations of various wireless applications. Specifically, the metaverse can offer virtual wireless system operations through the digital twin that allows network designers, mobile developers, and telecommunications engineers to monitor, observe, analyze, and simulations their solutions collaboratively and virtually. We first introduce a general architecture for metaverse-based wireless systems. We discuss key driving applications, design trends, and key enablers of metaverse-based wireless systems. Finally, we present several open challenges and their potential solutions.
Learning Job Titles Similarity from Noisy Skill Labels
Venue: arXiv cs.IR 2023
Year: 2023

Measuring semantic similarity between job titles is an essential functionality for automatic job recommendations. This task is usually approached using supervised learning techniques, which requires training data in the form of equivalent job title pairs. In this paper, we instead propose an unsupervised representation learning method for training a job title similarity model using noisy skill labels. We show that it is highly effective for tasks such as text ranking and job normalization.
On the Computational Efficiency of Adaptive and Dynamic Regret Minimization
Venue: arXiv cs.LG 2023
Year: 2023

In online convex optimization, the player aims to minimize regret, or the difference between her loss and that of the best fixed decision in hindsight over the entire repeated game. Algorithms that minimize (standard) regret may converge to a fixed decision, which is undesirable in changing or dynamic environments. This motivates the stronger metrics of performance, notably adaptive and dynamic regret. Adaptive regret is the maximum regret over any continuous sub-interval in time. Dynamic regret is the difference between the total cost and that of the best sequence of decisions in hindsight. State-of-the-art performance in both adaptive and dynamic regret minimization suffers a computational penalty - typically on the order of a multiplicative factor that grows logarithmically in the number of game iterations. In this paper we show how to reduce this computational penalty to be doubly logarithmic in the number of game iterations, and retain near optimal adaptive and dynamic regret bounds.