OpenRaiser/Intern-Atlas huggingface dataset:
Strategyproof and Proportionally Fair Facility Location
Venue: arXiv cs.GT 2023
Year: 2023

We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) and explore issues of strategyproofness and proportionality-based fairness. We introduce and analyze a hierarchy of proportionality-based fairness axioms of varying strength: Individual Fair Share (IFS), Unanimous Fair Share (UFS), Proportionality (as in Freeman et al, 2021), and Proportional Fairness (PF). For each axiom, we characterize the family of mechanisms that satisfy the axiom and strategyproofness. We show that imposing strategyproofness renders many of the axioms to be equivalent: the family of mechanisms that satisfy proportionality, unanimity, and strategyproofness is equivalent to the family of mechanisms that satisfy UFS and strategyproofness, which, in turn, is equivalent to the family of mechanisms that satisfy PF and strategyproofness. Furthermore, there is a unique such mechanism: the Uniform Phantom mechanism, which is studied in Freeman et al. (2021). We also characterize the outcomes of the Uniform Phantom mechanism as the unique (pure) equilibrium outcome for any mechanism that satisfies continuity, strict monotonicity, and UFS. Finally, we analyze the approximation guarantees, in terms of optimal social welfare and minimum total cost, obtained by mechanisms that are strategyproof and satisfy each proportionality-based fairness axiom. We show that the Uniform Phantom mechanism provides the best approximation of the optimal social welfare (and also minimum total cost) among all mechanisms that satisfy UFS.
Do Names Echo Semantics? A Large-Scale Study of Identifiers Used in C++'s Named Casts
Venue: arXiv cs.SE 2023
Year: 2023

Developers relax restrictions on a type to reuse methods with other types. While type casts are prevalent, in weakly typed languages such as C++, they are also extremely permissive. Assignments where a source expression is cast into a new type and assigned to a target variable of the new type, can lead to software bugs if performed without care. In this paper, we propose an information-theoretic approach to identify poor implementations of explicit cast operations. Our approach measures accord between the source expression and the target variable using conditional entropy. We collect casts from 34 components of the Chromium project, which collectively account for 27MLOC and random-uniformly sample this dataset to create a manually labelled dataset of 271 casts. Information-theoretic vetting of these 271 casts achieves a peak precision of 81% and a recall of 90%. We additionally present the findings of an in-depth investigation of notable explicit casts, two of which were fixed in recent releases of the Chromium project.
Discovering and Exploiting Sparse Rewards in a Learned Behavior Space
Venue: arXiv cs.LG 2023
Year: 2023

Learning optimal policies in sparse rewards settings is difficult as the learning agent has little to no feedback on the quality of its actions. In these situations, a good strategy is to focus on exploration, hopefully leading to the discovery of a reward signal to improve on. A learning algorithm capable of dealing with this kind of settings has to be able to (1) explore possible agent behaviors and (2) exploit any possible discovered reward. Efficient exploration algorithms have been proposed that require to define a behavior space, that associates to an agent its resulting behavior in a space that is known to be worth exploring. The need to define this space is a limitation of these algorithms. In this work, we introduce STAX, an algorithm designed to learn a behavior space on-the-fly and to explore it while efficiently optimizing any reward discovered. It does so by separating the exploration and learning of the behavior space from the exploitation of the reward through an alternating two-steps process. In the first step, STAX builds a repertoire of diverse policies while learning a low-dimensional representation of the high-dimensional observations generated during the policies evaluation. In the exploitation step, emitters are used to optimize the performance of the discovered rewarding solutions. Experiments conducted on three different sparse reward environments show that STAX performs comparably to existing baselines while requiring much less prior information about the task as it autonomously builds the behavior space.
A McEliece cryptosystem using permutation codes
Venue: arXiv cs.IT 2023
Year: 2023

This paper is an attempt to build a new public-key cryptosystem; similar to the McEliece cryptosystem, using permutation error-correcting codes. We study a public-key cryptosystem built using two permutation error-correcting codes. We show that these cryptosystems are insecure. However, the general framework in these cryptosystems can use any permutation error-correcting code and is interesting. We present an enhanced McEliece cryptosystem which subsumes McEliece cryptosystem based on linear error correcting codes.
Online Learning of Energy Consumption for Navigation of Electric Vehicles
Venue: arXiv cs.LG 2023
Year: 2023

Energy efficient navigation constitutes an important challenge in electric vehicles, due to their limited battery capacity. We employ a Bayesian approach to model the energy consumption at road segments for efficient navigation. In order to learn the model parameters, we develop an online learning framework and investigate several exploration strategies such as Thompson Sampling and Upper Confidence Bound. We then extend our online learning framework to the multi-agent setting, where multiple vehicles adaptively navigate and learn the parameters of the energy model. We analyze Thompson Sampling and establish rigorous regret bounds on its performance in the single-agent and multi-agent settings, through an analysis of the algorithm under batched feedback. Finally, we demonstrate the performance of our methods via experiments on several real-world city road networks.
Understanding the Use of e-Prints on Reddit and 4chan's Politically Incorrect Board
Venue: arXiv cs.DL 2023
Year: 2023

The dissemination and reach of scientific knowledge have increased at a blistering pace. In this context, e-Print servers have played a central role by providing scientists with a rapid and open mechanism for disseminating research without waiting for the (lengthy) peer review process. While helping the scientific community in several ways, e-Print servers also provide scientific communicators and the general public with access to a wealth of knowledge without paying hefty subscription fees. This motivates us to study how e-Prints are positioned within Web community discussions. In this paper, we analyze data from two Web communities: 14 years of Reddit data and over 4 from 4chan's Politically Incorrect board. Our findings highlight the presence of e-Prints in both science-enthusiast and general-audience communities. Real-world events and distinct factors influence the e-Prints people's discussions; e.g., there was a surge of COVID-19-related research publications during the early months of the outbreak and increased references to e-Prints in online discussions. Text in e-Prints and in online discussions referencing them has a low similarity, suggesting that the latter are not exclusively talking about the findings in the former. Further, our analysis of a sample of threads highlights: 1) misinterpretation and generalization of research findings, 2) early research findings being amplified as a source for future predictions, and 3) questioning findings from a pseudoscientific e-Print. Overall, our work emphasizes the need to quickly and effectively validate non-peer-reviewed e-Prints that get substantial press/social media coverage to help mitigate wrongful interpretations of scientific outputs.
Whistleblower protection in the digital age -- why 'anonymous' is not enough. From technology to a wider view of governance
Venue: arXiv cs.AI 2023
Year: 2023

When technology enters applications and processes with a long tradition of controversial societal debate, multi-faceted new ethical and legal questions arise. This paper focusses on the process of whistleblowing, an activity with large impacts on democracy and business. Computer science can, for the first time in history, provide for truly anonymous communication. We investigate this in relation to the values and rights of accountability, fairness and data protection, focusing on opportunities and limitations of the anonymity that can be provided computationally; possible consequences of outsourcing whistleblowing support; and challenges for the interpretation and use of some relevant laws. We conclude that to address these questions, whistleblowing and anonymous whistleblowing must rest on three pillars, forming a 'triangle of whistleblowing protection and incentivisation' that combines anonymity in a formal and technical sense; whistleblower protection through laws; and other norms and practices including organisational error culture.
Model Checking Temporal Properties of Recursive Probabilistic Programs
Venue: arXiv cs.FL 2023
Year: 2023

Probabilistic pushdown automata (pPDA) are a standard operational model for programming languages involving discrete random choices and recursive procedures. Temporal properties are useful for specifying the chronological order of events during program execution. Existing approaches for model checking pPDA against temporal properties have focused mostly on $ω$-regular and LTL properties. In this paper, we give decidability and complexity results for the model checking problem of pPDA against $ω$-visibly pushdown languages that can be described by specification logics such as CaRet. These logical formulae allow specifying properties that explicitly take the structured computations arising from procedural programs into account. For example, CaRet is able to match procedure calls with their corresponding future returns, and thus allows to express fundamental program properties such as total and partial correctness.
Predictive Model for Gross Community Production Rate of Coral Reefs using Ensemble Learning Methodologies
Venue: arXiv cs.LG 2023
Year: 2023

Coral reefs play a vital role in maintaining the ecological balance of the marine ecosystem. Various marine organisms depend on coral reefs for their existence and their natural processes. Coral reefs provide the necessary habitat for reproduction and growth for various exotic species of the marine ecosystem. In this article, we discuss the most important parameters which influence the lifecycle of coral and coral reefs such as ocean acidification, deoxygenation and other physical parameters such as flow rate and surface area. Ocean acidification depends on the amount of dissolved Carbon dioxide (CO2). This is due to the release of H+ ions upon the reaction of the dissolved CO2 gases with the calcium carbonate compounds in the ocean. Deoxygenation is another problem that leads to hypoxia which is characterized by a lesser amount of dissolved oxygen in water than the required amount for the existence of marine organisms. In this article, we highlight the importance of physical parameters such as flow rate which influence gas exchange, heat dissipation, bleaching sensitivity, nutrient supply, feeding, waste and sediment removal, growth and reproduction. In this paper, we also bring out these important parameters and propose an ensemble machine learning-based model for analyzing these parameters and provide better rates that can help us to understand and suitably improve the ocean composition which in turn can eminently improve the sustainability of the marine ecosystem, mainly the coral reefs
Simple odd $β$-cycle inequalities for binary polynomial optimization
Venue: arXiv cs.DM 2023
Year: 2023

We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd $β$-cycle inequalities valid for this polytope, showed that these generally have Chv{á}tal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a weaker version, called simple odd $β$-cycle inequalities, for which we establish a strongly polynomial-time separation algorithm for arbitrary instances. These inequalities still have Chv{á}tal rank 2 in general and still suffice to describe the multilinear polytope for cycle hypergraphs. Finally, we report about computational results of our prototype implementation. The simple odd $β$-cycle inequalities sometimes help to close more of the integrality gap in the experiments; however, the preliminary implementation has substantial computational cost, suggesting room for improvement in the separation algorithm.
Enumerating Independent Linear Inferences
Venue: arXiv cs.LO 2023
Year: 2023

A linear inference is a valid inequality of Boolean algebra in which each variable occurs at most once on each side. In this work we leverage recently developed graphical representations of linear formulae to build an implementation that is capable of more efficiently searching for switch-medial-independent inferences. We use it to find four `minimal' 8-variable independent inferences and also prove that no smaller ones exist; in contrast, a previous approach based directly on formulae reached computational limits already at 7 variables. Two of these new inferences derive some previously found independent linear inferences. The other two (which are dual) exhibit structure seemingly beyond the scope of previous approaches we are aware of; in particular, their existence contradicts a conjecture of Das and Strassburger. We were also able to identify 10 minimal 9-variable linear inferences independent of all the aforementioned inferences, comprising 5 dual pairs, and present applications of our implementation to recent `graph logics'.
Leveraging the Graph Structure of Neural Network Training Dynamics
Venue: arXiv cs.LG 2023
Year: 2023

Understanding the training dynamics of deep neural networks (DNNs) is important as it can lead to improved training efficiency and task performance. Recent works have demonstrated that representing the wirings of static graph cannot capture how DNNs change over the course of training. Thus, in this work, we propose a compact, expressive temporal graph framework that effectively captures the dynamics of many workhorse architectures in computer vision. Specifically, it extracts an informative summary of graph properties (e.g., eigenvector centrality) over a sequence of DNN graphs obtained during training. We demonstrate that our framework captures useful dynamics by accurately predicting trained, task performance when using a summary over early training epochs (<5) across four different architectures and two image datasets. Moreover, by using a novel, highly-scalable DNN graph representation, we also show that the proposed framework captures generalizable dynamics as summaries extracted from smaller-width networks are effective when evaluated on larger widths.
Social Fraud Detection Review: Methods, Challenges and Analysis
Venue: arXiv cs.LG 2023
Year: 2023

Social reviews have dominated the web and become a plausible source of product information. People and businesses use such information for decision-making. Businesses also make use of social information to spread fake information using a single user, groups of users, or a bot trained to generate fraudulent content. Many studies proposed approaches based on user behaviors and review text to address the challenges of fraud detection. To provide an exhaustive literature review, social fraud detection is reviewed using a framework that considers three key components: the review itself, the user who carries out the review, and the item being reviewed. As features are extracted for the component representation, a feature-wise review is provided based on behavioral, text-based features and their combination. With this framework, a comprehensive overview of approaches is presented including supervised, semi-supervised, and unsupervised learning. The supervised approaches for fraud detection are introduced and categorized into two sub-categories; classical, and deep learning. The lack of labeled datasets is explained and potential solutions are suggested. To help new researchers in the area develop a better understanding, a topic analysis and an overview of future directions is provided in each step of the proposed systematic framework.
Generating faster algorithms for d-Path Vertex Cover
Venue: arXiv cs.DS 2023
Year: 2023

Many algorithms which exactly solve hard problems require branching on more or less complex structures in order to do their job. Those who design such algorithms often find themselves doing a meticulous analysis of numerous different cases in order to identify these structures and design suitable branching rules, all done by hand. This process tends to be error prone and often the resulting algorithm may be difficult to implement in practice. In this work, we aim to automate a part of this process and focus on simplicity of the resulting implementation. We showcase our approach on the following problem. For a constant $d$, the $d$-Path Vertex Cover problem ($d$-PVC) is as follows: Given an undirected graph and an integer $k$, find a subset of at most $k$ vertices of the graph, such that their deletion results in a graph not containing a path on $d$ vertices as a subgraph. We develop a fully automated framework to generate parameterized branching algorithms for the problem and obtain algorithms outperforming those previously known for $3 \le d \le 8$. E.g., we show that $5$-PVC can be solved in $O(2.7^k\cdot n^{O(1)})$ time.
A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations
Venue: arXiv cs.AI 2023
Year: 2023

This two-part comprehensive survey is devoted to a computing framework most commonly known under the names Hyperdimensional Computing and Vector Symbolic Architectures (HDC/VSA). Both names refer to a family of computational models that use high-dimensional distributed representations and rely on the algebraic properties of their key operations to incorporate the advantages of structured symbolic representations and vector distributed representations. Notable models in the HDC/VSA family are Tensor Product Representations, Holographic Reduced Representations, Multiply-Add-Permute, Binary Spatter Codes, and Sparse Binary Distributed Representations but there are other models too. HDC/VSA is a highly interdisciplinary field with connections to computer science, electrical engineering, artificial intelligence, mathematics, and cognitive science. This fact makes it challenging to create a thorough overview of the field. However, due to a surge of new researchers joining the field in recent years, the necessity for a comprehensive survey of the field has become extremely important. Therefore, amongst other aspects of the field, this Part I surveys important aspects such as: known computational models of HDC/VSA and transformations of various input data types to high-dimensional distributed representations. Part II of this survey is devoted to applications, cognitive computing and architectures, as well as directions for future work. The survey is written to be useful for both newcomers and practitioners.
Construction of Spectrally-Null-Constrained Zero-Correlation Zone Sequences with Flexible Support
Venue: arXiv cs.IT 2023
Year: 2023

In recent years, traditional zero-correlation zone (ZCZ) sequences are being studied due to support interference-free quasi-synchronous code division multiple access (QS-CDMA) systems. However, in cognitive radio (CR) network, it is desirable to design ZCZ sequences having spectral null constraint (SNC) property to achieve low spectral density profile. This paper focuses on the construction of SNC-ZCZ sequences having flexible support, where support refers to a collection of indices corresponding to non-zero entries in the sequence. The proposed SNC-ZCZ sequences reduce to traditional ZCZ sequences when the size of the support becomes equal to the length of the sequence. To obtain ZCZ sequences, we first propose construction of traditional/SNC-Complete complementary codes (SNC-CCCs) using a class of extended Boolean functions (EBFs). With the help of this class we propose another class of EBFs that generates asymptotically optimal traditional/SNC-ZCZ sequences of prime-power lengths with respect to Tang-Fan-Matsufuzi bound. Furthermore, a relation between the second-order cosets of first-order generalized Reed-Muller code and the proposed traditional ZCZ sequences is also established.
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs
Venue: arXiv cs.DS 2023
Year: 2023

Given an $n$-vertex planar embedded digraph $G$ with non-negative edge weights and a face $f$ of $G$, Klein presented a data structure with $O(n\log n)$ space and preprocessing time which can answer any query $(u,v)$ for the shortest path distance in $G$ from $u$ to $v$ or from $v$ to $u$ in $O(\log n)$ time, provided $u$ is on $f$. This data structure is a key tool in a number of state-of-the-art algorithms and data structures for planar graphs. Klein's data structure relies on dynamic trees and the persistence technique as well as a highly non-trivial interaction between primal shortest path trees and their duals. The construction of our data structure follows a completely different and in our opinion very simple divide-and-conquer approach that solely relies on Single-Source Shortest Path computations and contractions in the primal graph. Our space and preprocessing time bound is $O(n\log |f|)$ and query time is $O(\log |f|)$ which is an improvement over Klein's data structure when $f$ has small size.
Single- versus Multi-Carrier Terahertz-Band Communications: A Comparative Study
Venue: arXiv cs.IT 2023
Year: 2023

The prospects of utilizing single-carrier (SC) and multi-carrier (MC) waveforms in future terahertz (THz)-band communication systems remain unresolved. On the one hand, the limited multi-path components at high frequencies result in frequency-flat channels that favor low-complexity wideband SC systems. On the other hand, frequency-dependent molecular absorption and transceiver characteristics and the existence of multi-path components in indoor sub-THz systems can still result in frequency-selective channels, favoring off-the-shelf MC schemes such as orthogonal frequency-division multiplexing (OFDM). Variations of SC/MC designs result in different THz spectrum utilization, but spectral efficiency is not the primary concern with substantial available bandwidths; baseband complexity, power efficiency, and hardware impairment constraints are predominant. This paper presents a comprehensive study of SC/MC modulations for THz communications, utilizing an accurate wideband THz channel model and highlighting the various performance and complexity trade-offs of the candidate schemes. Simulations demonstrate that discrete-Fourier-transform spread orthogonal time-frequency space (DFT-s-OTFS) achieves a lower peak-to-average power ratio (PAPR) than OFDM and OTFS and enhances immunity to THz impairments and Doppler spreads, but at an increased complexity cost. Moreover, DFT-s-OFDM is a promising candidate that increases robustness to THz impairments and phase noise (PHN) at a low PAPR and overall complexity.