OpenRaiser/Intern-Atlas huggingface dataset:
Responsible AI Governance: A Systematic Literature Review
Venue: arXiv cs.CY 2023
Year: 2023

As artificial intelligence transforms a wide range of sectors and drives innovation, it also introduces complex challenges concerning ethics, transparency, bias, and fairness. The imperative for integrating Responsible AI (RAI) principles within governance frameworks is paramount to mitigate these emerging risks. While there are many solutions for AI governance, significant questions remain about their effectiveness in practice. Addressing this knowledge gap, this paper aims to examine the existing literature on AI Governance. The focus of this study is to analyse the literature to answer key questions: WHO is accountable for AI systems' governance, WHAT elements are being governed, WHEN governance occurs within the AI development life cycle, and HOW it is executed through various mechanisms like frameworks, tools, standards, policies, or models. Employing a systematic literature review methodology, a rigorous search and selection process has been employed. This effort resulted in the identification of 61 relevant articles on the subject of AI Governance. Out of the 61 studies analysed, only 5 provided complete responses to all questions. The findings from this review aid research in formulating more holistic and comprehensive Responsible AI (RAI) governance frameworks. This study highlights important role of AI governance on various levels specially organisational in establishing effective and responsible AI practices. The findings of this study provides a foundational basis for future research and development of comprehensive governance models that align with RAI principles.
Towards building a monitoring platform for a challenge-oriented smart specialisation with RIS3-MCAT
Venue: arXiv cs.CY 2023
Year: 2023

In the new research and innovation (R&I) paradigm, aimed at a transformation towards more sustainable, inclusive and fair pathways to address societal and environmental challenges, and at generating new patterns of specialisation and new trajectories for socioeconomic development, it is essential to provide monitoring systems and tools to map and understand the contribution of R&I policies and projects. To address this transformation, we present the RIS3-MCAT platform, the result of a line of work aimed at exploring the potential of open data, semantic analysis, and data visualisation, for monitoring challenge-oriented smart specialisation in Catalonia. RIS3-MCAT is an interactive platform that facilitates access to R&I project data in formats that allow for sophisticated analyses of a large volume of texts, enabling the detailed study of thematic specialisations and challenges beyond classical classification systems. Its conceptualisation, development framework and use are presented in this paper.
A risk-based approach to assessing liability risk for AI-driven harms considering EU liability directive
Venue: arXiv cs.CY 2023
Year: 2023

Artificial intelligence can cause inconvenience, harm, or other unintended consequences in various ways, including those that arise from defects or malfunctions in the AI system itself or those caused by its use or misuse. Responsibility for AI harms or unintended consequences must be addressed to hold accountable the people who caused such harms and ensure that victims receive compensation for any damages or losses they may have sustained. Historical instances of harm caused by AI have led to European Union establishing an AI Liability Directive. The directive aims to lay down a uniform set of rules for access to information, delineate the duty and level of care required for AI development and use, and clarify the burden of proof for damages or harms caused by AI systems, establishing broader protection for victims. The future ability of provider to contest a product liability claim will depend on good practices adopted in designing, developing, and maintaining AI systems in the market. This paper provides a risk-based approach to examining liability for AI-driven injuries. It also provides an overview of existing liability approaches, insights into limitations and complexities in these approaches, and a detailed self-assessment questionnaire to assess the risk associated with liability for a specific AI system from a provider's perspective.
Evaluation of Consumer Behavior Regarding Food Delivery Applications in India
Venue: arXiv cs.HC 2023
Year: 2023

. This paper explores consumer behavior towards food delivery apps, focusing on attributes like restaurant variety, food packaging quality, and application design and user interface. The study reveals that a diverse range of restaurants positively influences consumer satisfaction, leading to increased app usage. Conversely, the quality of food packaging does not significantly impact overall satisfaction. However, the study underscores the crucial role of application design and user interface in shaping consumer behavior. Both factors significantly influence overall satisfaction, with user-friendly interfaces attracting more users and promoting frequent app usage. The findings emphasize the importance of businesses addressing these attributes to enhance customer satisfaction, boost app engagement, and foster long-term customer loyalty. Understanding and catering to consumer preferences in these areas can contribute to the success of food delivery apps in the competitive market.
Going Viral: An Analysis of Advertising of Technology Products on TikTok
Venue: arXiv cs.CY 2023
Year: 2023

Social media has transformed the advertising landscape, becoming an essential tool for reaching and connecting with consumers. Its sharing and engagement features amplify brand exposure, while its cost-effective options provide businesses with flexible advertising solutions. TikTok is a more recent social media platform that has gained popularity for advertising, particularly in the realm of e-commerce, due to its large user base and viral nature. TikTok had 1.2 billion monthly active users in Q4 2021, generating an estimated $4.6 billion revenue in 2021. Virality can lead to a massive increase in brand exposure, reaching a vast audience that may not have been accessible through traditional marketing efforts alone. Advertisements for technological products are an example of such viral ads that are abundant on TikTok. The goal of this thesis is to understand how creators, community activity, and the recommendation algorithm influence the virality of advertisements for technology products on TikTok. The study analyzes various aspects of virality, including sentiment analysis, content characteristics, and the role of influencers. It employs data scraping and natural language processing tools to analyze metadata from 2,000 TikTok posts and 274,651, offering insights into the nuances of viral tech product advertising on TikTok.
Research on Resource Allocation under Unlicensed Spectrum Using Q-Learning
Venue: arXiv cs.NI 2023
Year: 2023

In response to the advent of the 5G era, enhancing throughput and increasing transmission efficiency within limited spectrum resources is an important research topic. In the LTE system, utilizing unlicensed spectrum to assist traditional mobile networks, known as License Assisted Access, has emerged as a viable solution to effectively improve transmission efficiency. However, as the unlicensed spectrum also accommodates other users, such as Wi-Fi for mobile communication, there is a need to address the issue of spectrum resource allocation, aiming to achieve fair transmission among different mobile communication users. This research project aims to explore and compare two approaches: traditional communication algorithms and reinforcement learning method Q-leaning, under the condition of achieving maximum system throughput, in order to determine the differences between the two methods.
Workload Distribution with Rateless Encoding: A Low-Latency Computation Offloading Method within Edge Networks
Venue: arXiv cs.DC 2023
Year: 2023

This paper introduces REDC, a comprehensive strategy for offloading computational tasks within mobile Edge Networks (EN) to Distributed Computing (DC) after Rateless Encoding (RE). Despite the efficiency, reliability, and scalability advantages of distributed computing in ENs, straggler-induced latencies and failures pose significant challenges. Coded distributed computing has gained attention for its efficient redundancy computing, alleviating the impact of stragglers. Yet, current research predominantly focuses on tolerating a predefined number of stragglers with minimal encoding redundancy. Furthermore, nodes within edge networks are characterized by their inherent heterogeneity in computation, communication, and storage capacities, and unpredictable straggler effects and failures. To our knowledge, existing encoding offloading approaches lack a systematic design and unified consideration of these characteristics. REDC addresses these issues by adaptively encoding tasks, then distributing the workload based on node variations. In the face of unpredictability failures, the rateless encoding adaptation provides resilience to dynamic straggler effects. Considering the node heterogeneity and system status, tasks are offloaded to optimal subset "valid" nodes. Load distribution decisions are made based on updates to queuing theory modeling through state feedback. The REDC framework is applicable to EN by improving resource utilization and reducing task sequence execution delays. Experimental results demonstrate our method's effectiveness and resilient performance, maintaining efficacy even in the presence of unstable nodes.
A General Homogeneous Matrix Formulation to 3D Rotation Geometric Transformations
Venue: arXiv cs.CV 2024
Year: 2024

We present algebraic projective geometry definitions of 3D rotations so as to bridge a small gap between the applications and the definitions of 3D rotations in homogeneous matrix form. A general homogeneous matrix formulation to 3D rotation geometric transformations is proposed which suits for the cases when the rotation axis is unnecessarily through the coordinate system origin given their rotation axes and rotation angles. General three-dimensional rotation formula~\eqref{eqn:3D homogeneous roation} and~\eqref{eqn:3D rotation matrix vector Euclidean} similar to the Euler-Rodrigues formula were presented. The matrix-vector form of 3D rotation in Euclidean space is especially suited for numerical applications where gimbal lock is a concern.}
Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
Venue: arXiv cs.DS 2024
Year: 2024

Given a context free language $\mathcal{L(G)}$ over alphabet $Σ$ and a string $s \in Σ^*$, {\em the language edit distance} problem seeks the minimum number of edits (insertions, deletions and substitutions) required to convert $s$ into a valid member of $\mathcal{L(G)}$. The well-known dynamic programming algorithm solves this problem in $O(n^3)$ time (ignoring grammar size) where $n$ is the string length [Aho, Peterson 1972, Myers 1985]. Despite its numerous applications, to date there exists no algorithm that computes exact or approximate language edit distance problem in true subcubic time. In this paper we give the first such algorithm that approximates language edit distance in subcubic time. For any arbitrary $ε> 0$, our algorithm runs in $\tilde{O}(\frac{n^{2.491}}{ε^2})$ time and returns an estimate within a multiplicative approximation factor of $(1+ε)$. Moreover, an additive $εn$ approximation can be computed in $O(\frac{n^2}{ε^{0.825}})$ time. To complement our upper bound results, we show that exact computation of language edit distance with insertion-only edits in truly subcubic time will imply a truly subcubic algorithm for all-pairs shortest paths which is a long-standing open question in computer science.
Timed Multiset Rewriting and the Verification of Time-Sensitive Distributed Systems
Venue: arXiv cs.LO 2024
Year: 2024

Time-Sensitive Distributed Systems (TSDS), such as applications using autonomous drones, achieve goals under possible environment interference (\eg, winds). Moreover, goals are often specified using explicit time constraints which must be satisfied by the system \emph{perpetually}. For example, drones carrying out the surveillance of some area must always have \emph{recent pictures}, \ie, at most $M$ time units old, of some strategic locations. This paper proposes a Multiset Rewriting language with explicit time for specifying and analysing TSDSes. We introduce two properties, \emph{realizability} (some trace is good) and \emph{survivability} (where, in addition, all admissible traces are good). A good trace is an infinite trace in which goals are perpetually satisfied. We propose a class of systems called \emph{progressive timed systems} (PTS), where intuitively only a finite number of actions can be carried out in a bounded time period. We prove that for this class of systems both the realizability and the survivability problems are PSPACE-complete. Furthermore, if we impose a bound on time (as in bounded model-checking), we show that for PTS, realizability becomes NP-complete, while survivability is in the $Δ_2^p$ class of the polynomial hierarchy. Finally, we demonstrate that the rewriting logic system Maude can be used to automate time bounded verification of PTS.
Query Complexity of Tournament Solutions
Venue: arXiv cs.DS 2024
Year: 2024

A directed graph where there is exactly one edge between every pair of vertices is called a {\em tournament}. Finding the "best" set of vertices of a tournament is a well studied problem in social choice theory. A {\em tournament solution} takes a tournament as input and outputs a subset of vertices of the input tournament. However, in many applications, for example, choosing the best set of drugs from a given set of drugs, the edges of the tournament are given only implicitly and knowing the orientation of an edge is costly. In such scenarios, we would like to know the best set of vertices (according to some tournament solution) by "querying" as few edges as possible. We, in this paper, precisely study this problem for commonly used tournament solutions: given an oracle access to the edges of a tournament T, find $f(T)$ by querying as few edges as possible, for a tournament solution f. We first show that the set of Condorcet non-losers in a tournament can be found by querying $2n-\lfloor \log n \rfloor -2$ edges only and this is tight in the sense that every algorithm for finding the set of Condorcet non-losers needs to query at least $2n-\lfloor \log n \rfloor -2$ edges in the worst case, where $n$ is the number of vertices in the input tournament. We then move on to study other popular tournament solutions and show that any algorithm for finding the Copeland set, the Slater set, the Markov set, the bipartisan set, the uncovered set, the Banks set, and the top cycle must query $Ω(n^2)$ edges in the worst case. On the positive side, we are able to circumvent our strong query complexity lower bound results by proving that, if the size of the top cycle of the input tournament is at most $k$, then we can find all the tournament solutions mentioned above by querying $O(nk + \frac{n\log n}{\log(1-\frac{1}{k})})$ edges only.
A Sequence Construction of Cyclic Codes over Finite Fields
Venue: arXiv cs.IT 2024
Year: 2024

Cyclic codes over finite fields are widely implemented in data storage systems, communication systems, and consumer electronics, as they have very efficient encoding and decoding algorithms. They are also important in theory, as they are closely connected to several areas in mathematics. There are a few fundamental ways of constructing all cyclic codes over finite fields, including the generator matrix approach, the generator polynomial approach, the generating idempotent approach, and the $q$-polynomial approach. Another one is a sequence approach, which has been intensively investigated in the past decade. The objective of this paper is to survey the progress in the past decade in this direction.
Verifying Concurrent Stacks by Divergence-Sensitive Bisimulation
Venue: arXiv cs.PL 2024
Year: 2024

The verification of linearizability -- a key correctness criterion for concurrent objects -- is based on trace refinement whose checking is PSPACE-complete. This paper suggests to use \emph{branching} bisimulation instead. Our approach is based on comparing an abstract specification in which object methods are executed atomically to a real object program. Exploiting divergence sensitivity, this also applies to progress properties such as lock-freedom. These results enable the use of \emph{polynomial-time} divergence-sensitive branching bisimulation checking techniques for verifying linearizability and progress. We conducted the experiment on concurrent lock-free stacks to validate the efficiency and effectiveness of our methods.
Fast Similarity Sketching
Venue: arXiv cs.DS 2024
Year: 2024

We consider the $\textit{Similarity Sketching}$ problem: Given a universe $[u] = \{0,\ldots, u-1\}$ we want a random function $S$ mapping subsets $A\subseteq [u]$ into vectors $S(A)$ of size $t$, such that the Jaccard similarity $J(A,B) = |A\cap B|/|A\cup B|$ between sets $A$ and $B$ is preserved. More precisely, define $X_i = [S(A)[i] = S(B)[i]]$ and $X = \sum_{i\in [t]} X_i$. We want $E[X_i]=J(A,B)$, and we want $X$ to be strongly concentrated around $E[X] = t \cdot J(A,B)$ (i.e. Chernoff-style bounds). This is a fundamental problem which has found numerous applications in data mining, large-scale classification, computer vision, similarity search, etc. via the classic MinHash algorithm. The vectors $S(A)$ are also called $\textit{sketches}$. Strong concentration is critical, for often we want to sketch many sets $B_1,\ldots,B_n$ so that we later, for a query set $A$, can find (one of) the most similar $B_i$. It is then critical that no $B_i$ looks much more similar to $A$ due to errors in the sketch. The seminal $t\times\textit{MinHash}$ algorithm uses $t$ random hash functions $h_1,\ldots, h_t$, and stores $\left ( \min_{a\in A} h_1(A),\ldots, \min_{a\in A} h_t(A) \right )$ as the sketch of $A$. The main drawback of MinHash is, however, its $O(t\cdot |A|)$ running time, and finding a sketch with similar properties and faster running time has been the subject of several papers. (continued...)
Security Camera Movie and ERP Data Matching System to Prevent Theft
Venue: arXiv cs.CY 2024
Year: 2024

"(c) 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works." In this paper, we propose a SaaS service which prevents shoplifting using image analysis and ERP. In Japan, total damage of shoplifting reaches 450 billion yen. Based on cloud and data analysis technology, we propose a shoplifting prevention service with image analysis of security camera and ERP data check for small shops. We evaluated movie analysis. Y. Yamato, Y. Fukumoto and H. Kumazaki, "Security Camera Movie and ERP Data Matching System to Prevent Theft," IEEE Consumer Communications and Networking Conference (CCNC 2017), pp.1021-1022, DOI: 10.1109/CCNC.2017.7983275, Jan. 2017.
A technique for solving the polygon inclusion problems
Venue: arXiv cs.CG 2024
Year: 2024

We propose a technique called Rotate-and-Kill for solving the polygon inclusion and circumscribing problems. By applying this technique, we obtain $O(n)$ time algorithms for computing (1) the maximum area triangle in a given $n$-sided convex polygon $P$, (2) the minimum area triangle enclosing $P$, (3) the minimum area triangle enclosing $P$ touching edge-to-edge, i.e. the minimum area triangle that is the intersection of three half-planes out of the $n$ half-planes defining $P$, and (4) the minimum perimeter triangle enclosing $P$ touching edge-to-edge. Our algorithm for computing the maximum area triangle is simpler than the alternatives given in [Chandran and Mount, IJCGA'92] and [Kallus, arXiv'17]. Our algorithms for computing the minimum area or perimeter triangle enclosing $P$ touching edge-to-edge improve the $O(n\log n)$ or $O(n\log^2n)$ time algorithms given in [Boyce \emph{et al.}, STOC'82], [Aggarwal \emph{et al.}, Algorithmica'87], [Aggarwal and J. Park., FOCS'88], [Aggarwal \emph{et al.}, DCG'94], and [Schieber, SODA'95].
Game Theoretic Semi-Distributed D2D Resource Allocation Underlaying an LTE Network
Venue: arXiv cs.IT 2024
Year: 2024

To devise D2D resource allocation algorithms in underlay D2D communications the channel state information (CSI) between the D2D transmitters and the BS and the D2D receiver CSI (DCSI-R) needs to be transmitted to the BS. However, this increases the control overhead and power wastage which increases with a fast fading channel since the CSI needs to be transmitted in every time slot. Most of the existing works assume DCSI-R availability at the BS. However, a few works assume its unavailability and determine the Nash equilibrium which may not be Pareto optimal. We address this problem and within a game theoretic framework propose a suboptimal semi-distributed D2D resource allocation algorithm. We consider the channel to exhibit path loss. Our goal is to maximize the social utility of the D2D users while meeting their utility requirements and the signal-to-interference-plus-noise ratio (SINR) requirements of the CUs to reach a Pareto optimal solution. Next, we consider shadowing, fast fading and mobility of CUs and propose another algorithm which is a modification of our first proposed algorithm. Through simulations we observe that the first algorithm does not perform well practically but the second algorithm is very robust to channel randomness and CU mobility.
An extended type system with lambda-typed lambda-expressions (extended version)
Venue: arXiv cs.LO 2024
Year: 2024

We present the type system $\mathtt{d}$, an extended type system with lambda-typed lambda-expressions. It is related to type systems originating from the Automath project. $\mathtt{d}$ extends existing lambda-typed systems by an existential abstraction operator as well as propositional operators. $β$-reduction is extended to also normalize negated expressions using a subset of the laws of classical negation, hence $\mathtt{d}$ is normalizing both proofs and formulas which are handled uniformly as functional expressions. $\mathtt{d}$ is using a reflexive typing axiom for a constant $τ$ to which no function can be typed. Some properties are shown including confluence, subject reduction, uniqueness of types, strong normalization, and consistency. We illustrate how, when using $\mathtt{d}$, due to its limited logical strength additional axioms must be added both for negation and for the mathematical structures whose deductions are to be formalized. Several appendices deal with extensions and variations of the proposed system.
An Unsupervised Learning Classifier with Competitive Error Performance
Venue: arXiv cs.LG 2024
Year: 2024

An unsupervised learning classification model is described. It achieves classification error probability competitive with that of popular supervised learning classifiers such as SVM or kNN. The model is based on the incremental execution of small step shift and rotation operations upon selected discriminative hyperplanes at the arrival of input samples. When applied, in conjunction with a selected feature extractor, to a subset of the ImageNet dataset benchmark, it yields 6.2 % Top 3 probability of error; this exceeds by merely about 2 % the result achieved by (supervised) k-Nearest Neighbor, both using same feature extractor. This result may also be contrasted with popular unsupervised learning schemes such as k-Means which is shown to be practically useless on same dataset.