OpenRaiser/Intern-Atlas huggingface dataset:
A Cooperative NOMA User Pairing in UAV-Based Wireless Networks
Venue: arXiv cs.IT 2022
Year: 2022

NOMA (non-orthogonal multiple access) will be seen as a promising technology for enhancing spectrum efficiency in future cellular networks. The use of unmanned aerial vehicle (UAV) Amplify-and-Forward (AF) relaying as a moving access point or BS, on the other hand, has emerged as a potential solution to wireless networks' high traffic demands. In this paper, we study joint user pair and resource allocation-based distance to optimize fair throughput in a downlink scenario, which concentrates on UAV-aided communication from different wireless-powered nodes. Several transmission methods are proposed, including NOMA as well as UAV cooperative relaying and two representative node-pairing strategies. The simulation results illustrate that the proposed user pairing strategies for cooperative NOMA and UAV-based cellular networks enhance downlink transmission performance and ensure optimum use of power and bandwidth resources.
The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs
Venue: arXiv cs.CG 2023
Year: 2023

The Voronoi diagram is a certain geometric data structure which has numerous applications in various scientific and technological fields. The theory of algorithms for computing 2D Euclidean Voronoi diagrams of point sites is rich and useful, with several different and important algorithms. However, this theory has been quite steady during the last few decades in the sense that no essentially new algorithms have entered the game. In addition, most of the known algorithms are serial in nature and hence cast inherent difficulties on the possibility to compute the diagram in parallel. In this paper we present the projector algorithm: a new and simple algorithm which enables the (combinatorial) computation of 2D Voronoi diagrams. The algorithm is significantly different from previous ones and some of the involved concepts in it are in the spirit of linear programming and optics. Parallel implementation is naturally supported since each Voronoi cell can be computed independently of the other cells. A new combinatorial structure for representing the cells (and any convex polytope) is described along the way and the computation of the induced Delaunay graph is obtained almost automatically.
SVD Factorization for Tall-and-Fat Matrices on Parallel Architectures
Venue: arXiv cs.DC 2023
Year: 2023

We demonstrate an implementation for an approximate rank-k SVD factorization, combining well-known randomized projection techniques with previously known paralel solutions in order to compute steps of the random projection based SVD procedure. We structure the problem in a way that it reduces to fast computation around $k \times k$ matrices computed on a single machine, greatly easing the computability of the problem. The paper is also a tutorial on paralel linear algebra methods using a plain architecture without burdensome frameworks.
A closed-form solution for the flat-state geometry of cylindrical surface intersections bounded on all sides by orthogonal planes
Venue: arXiv cs.CG 2023
Year: 2023

A closed-form solution for the boundary of the flat state of an orthogonal cross section of contiguous surface geometry formed by the intersection of two cylinders of equal radii oriented in dual directions of rotation about their intersecting axes.
The ERA of FOLE: Foundation
Venue: arXiv cs.DB 2023
Year: 2023

This paper discusses the representation of ontologies in the first-order logical environment {\ttfamily FOLE}. An ontology defines the primitives with which to model the knowledge resources for a community of discourse. These primitives consist of classes, relationships and properties. An ontology uses formal axioms to constrain the interpretation of these primitives. In short, an ontology specifies a logical theory. This paper continues the discussion of the representation and interpretation of ontologies in the first-order logical environment {\ttfamily FOLE}. The formalism and semantics of (many-sorted) first-order logic can be developed in both a \emph{classification form} and an \emph{interpretation form}. Two papers, the current paper, defining the concept of a structure, and ``The {\ttfamily ERA} of {\ttfamily FOLE}: Superstructure'', defining the concept of a sound logic, represent the \emph{classification form}, corresponding to ideas discussed in the ``Information Flow Framework''. Two papers, ``The {\ttfamily FOLE} Table'', defining the concept of a relational table, and ``The {\ttfamily FOLE} Database'', defining the concept of a relational database, represent the \emph{interpretation form}, expanding on material found in the paper ``Database Semantics''. Although the classification form follows the entity-relationship-attribute data model of Chen, the interpretation form incorporates the relational data model of Codd. A fifth paper ``{\ttfamily FOLE} Equivalence'' proves that the classification form is equivalent to the interpretation form. In general, the {\ttfamily FOLE} representation uses a conceptual structures approach, that is completely compatible with the theory of institutions, formal concept analysis and information flow.
Spatially Common Sparsity Based Adaptive Channel Estimation and Feedback for FDD Massive MIMO
Venue: arXiv cs.IT 2023
Year: 2023

This paper proposes a spatially common sparsity based adaptive channel estimation and feedback scheme for frequency division duplex based massive multi-input multi-output (MIMO) systems, which adapts training overhead and pilot design to reliably estimate and feed back the downlink channel state information (CSI) with significantly reduced overhead. Specifically, a non-orthogonal downlink pilot design is first proposed, which is very different from standard orthogonal pilots. By exploiting the spatially common sparsity of massive MIMO channels, a compressive sensing (CS) based adaptive CSI acquisition scheme is proposed, where the consumed time slot overhead only adaptively depends on the sparsity level of the channels. Additionally, a distributed sparsity adaptive matching pursuit algorithm is proposed to jointly estimate the channels of multiple subcarriers. Furthermore, by exploiting the temporal channel correlation, a closed-loop channel tracking scheme is provided, which adaptively designs the non-orthogonal pilot according to the previous channel estimation to achieve an enhanced CSI acquisition. Finally, we generalize the results of the multiple-measurement-vectors case in CS and derive the Cramer-Rao lower bound of the proposed scheme, which enlightens us to design the non-orthogonal pilot signals for the improved performance. Simulation results demonstrate that the proposed scheme outperforms its counterparts, and it is capable of approaching the performance bound.
State machines for large scale computer software and systems
Venue: arXiv cs.FL 2023
Year: 2023

The behavior and architecture of large scale discrete state systems found in computer software and hardware can be specified and analyzed using a particular class of primitive recursive functions. This paper begins with an illustration of the utility of the method via a number of small examples and then via longer specification and verification of the Paxos distributed consensus algorithm. The sequence maps are then shown to provide an alternative representation of deterministic state machines and algebraic products of state machines. Distributed and composite systems, parallel and concurrent computation, and real-time behavior can all be specified naturally with these methods - which require neither extensions to the classical state machine model nor any axiomatic methods or other techniques from formal methods. Compared to state diagrams or tables or the standard set-tuple-transition-maps, sequence maps are more concise and better suited to describing the behavior and compositional architecture of computer systems. Staying strictly within the boundaries of classical deterministic state machines anchors the methods to the algebraic structures of automata and makes the specifications faithful to engineering practice.
On the Existence of Weak One-Way Functions
Venue: arXiv cs.CC 2023
Year: 2023

This note is an attempt to unconditionally prove the existence of weak one way functions (OWF). Starting from a provably intractable decision problem $L_D$ (whose existence is nonconstructively assured from the well-known discrete time-hierarchy theorem from complexity theory), we construct another intractable decision problem $L\subseteq \{0,1\}^*$ that has its words scattered across $\{0,1\}^\ell$ at a relative frequency $p(\ell)$, for which upper and lower bounds can be worked out. The value $p(\ell)$ is computed from the density of the language within $\{0,1\}^\ell$ divided by the total word count $2^\ell$. It corresponds to the probability of retrieving a yes-instance of a decision problem upon a uniformly random draw from $\{0,1\}^\ell$. The trick to find a language with known bounds on $p(\ell)$ relies on switching from $L_D$ to $L_0:=L_D\cap L'$, where $L'$ is an easy-to-decide language with a known density across $\{0,1\}^*$. In defining $L'$ properly (and upon a suitable Gödel numbering), the hardness of deciding $L_D\cap L'$ is inherited from $L_D$, while its density is controlled by that of $L'$. The lower and upper approximation of $p(\ell)$ then let us construct an explicit threshold function (as in random graph theory) that can be used to efficiently and intentionally sample yes- or no-instances of the decision problem (language) $L_0$ (however, without any auxiliary information that could ease the decision like a polynomial witness). In turn, this allows to construct a weak OWF that encodes a bit string $w\in\{0,1\}^*$ by efficiently (in polynomial time) emitting a sequence of randomly constructed intractable decision problems, whose answers correspond to the preimage $w$.
Multiparty testing preorders
Venue: arXiv cs.LO 2023
Year: 2023

Variants of the must testing approach have been successfully applied in service oriented computing for analysing the compliance between (contracts exposed by) clients and servers or, more generally, between two peers. It has however been argued that multiparty scenarios call for more permissive notions of compliance because partners usually do not have full coordination capabilities. We propose two new testing preorders, which are obtained by restricting the set of potential observers. For the first preorder, called uncoordinated, we allow only sets of parallel observers that use different parts of the interface of a given service and have no possibility of intercommunication. For the second preorder, that we call individualistic, we instead rely on parallel observers that perceive as silent all the actions that are not in the interface of interest. We have that the uncoordinated preorder is coarser than the classical must testing preorder and finer than the individualistic one. We also provide a characterisation in terms of decorated traces for both preorders: the uncoordinated preorder is defined in terms of must-sets and Mazurkiewicz traces while the individualistic one is described in terms of classes of filtered traces that only contain designated visible actions and must-sets.
Generative Adversarial Trainer: Defense to Adversarial Perturbations with GAN
Venue: arXiv cs.LG 2023
Year: 2023

We propose a novel technique to make neural network robust to adversarial examples using a generative adversarial network. We alternately train both classifier and generator networks. The generator network generates an adversarial perturbation that can easily fool the classifier network by using a gradient of each image. Simultaneously, the classifier network is trained to classify correctly both original and adversarial images generated by the generator. These procedures help the classifier network to become more robust to adversarial perturbations. Furthermore, our adversarial training framework efficiently reduces overfitting and outperforms other regularization methods such as Dropout. We applied our method to supervised learning for CIFAR datasets, and experimantal results show that our method significantly lowers the generalization error of the network. To the best of our knowledge, this is the first method which uses GAN to improve supervised learning.
The Logarithmic Funnel Heap: An Efficient Priority Queue For Extremely Large Sets
Venue: arXiv cs.DS 2023
Year: 2023

For many data-processing applications, a comprehensive set of efficient operations for the management of priority values is required. Indexed priority queues are particularly promising to satisfy this requirement by design. In this work, we report the design and analysis of an efficient indexed priority queue with a comprehensive set of operations. In particular, $\mathtt{insert}$, $\mathtt{delete}$ and $\mathtt{decrease}$ all run in expected $O(\log^{*}{n})$ time, while $\mathtt{increase}$ is conjectured by means of Monte Carlo simulations to run in expected $O(\log\log{n})$ time. The space complexity as well as the time complexity for the construction of the empty heap data structure is $O(n)$. For certain massive computational problems, such as specific analyses of extremely large graphs and (chemical) simulations, this heap system may exhibit considerable utility.
Exploring the Design Space of Immersive Urban Analytics
Venue: arXiv cs.GR 2023
Year: 2023

Recent years have witnessed the rapid development and wide adoption of immersive head-mounted devices, such as HTC VIVE, Oculus Rift, and Microsoft HoloLens. These immersive devices have the potential to significantly extend the methodology of urban visual analytics by providing critical 3D context information and creating a sense of presence. In this paper, we propose an theoretical model to characterize the visualizations in immersive urban analytics. Further more, based on our comprehensive and concise model, we contribute a typology of combination methods of 2D and 3D visualizations that distinguish between linked views, embedded views, and mixed views. We also propose a supporting guideline to assist users in selecting a proper view under certain circumstances by considering visual geometry and spatial distribution of the 2D and 3D visualizations. Finally, based on existing works, possible future research opportunities are explored and discussed.
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
Venue: arXiv cs.LO 2023
Year: 2023

The ellipsoid method is an algorithm that solves the (weak) feasibility and linear optimization problems for convex sets by making oracle calls to their (weak) separation problem. We observe that the previously known method for showing that this reduction can be done in fixed-point logic with counting (FPC) for linear and semidefinite programs applies to any family of explicitly bounded convex sets. We use this observation to show that the exact feasibility problem for semidefinite programs is expressible in the infinitary version of FPC. As a corollary we get that, for the isomorphism problem, the Lasserre/Sums-of-Squares semidefinite programming hierarchy of relaxations collapses to the Sherali-Adams linear programming hierarchy, up to a small loss in the degree.
Improving Native Ads CTR Prediction by Large Scale Event Embedding and Recurrent Networks
Venue: arXiv cs.LG 2023
Year: 2023

Click through rate (CTR) prediction is very important for Native advertisement but also hard as there is no direct query intent. In this paper we propose a large-scale event embedding scheme to encode the each user browsing event by training a Siamese network with weak supervision on the users' consecutive events. The CTR prediction problem is modeled as a supervised recurrent neural network, which naturally model the user history as a sequence of events. Our proposed recurrent models utilizing pretrained event embedding vectors and an attention layer to model the user history. Our experiments demonstrate that our model significantly outperforms the baseline and some variants.
Homology-Preserving Multi-Scale Graph Skeletonization Using Mapper on Graphs
Venue: arXiv cs.SI 2023
Year: 2023

Node-link diagrams are a popular method for representing graphs that capture relationships between individuals, businesses, proteins, and telecommunication endpoints. However, node-link diagrams may fail to convey insights regarding graph structures, even for moderately sized data of a few hundred nodes, due to visual clutter. We propose to apply the mapper construction -- a popular tool in topological data analysis -- to graph visualization, which provides a strong theoretical basis for summarizing the data while preserving their core structures. We develop a variation of the mapper construction targeting weighted, undirected graphs, called {\mog}, which generates homology-preserving skeletons of graphs. We further show how the adjustment of a single parameter enables multi-scale skeletonization of the input graph. We provide a software tool that enables interactive explorations of such skeletons and demonstrate the effectiveness of our method for synthetic and real-world data.
Near Optimal Linear Algebra in the Online and Sliding Window Models
Venue: arXiv cs.DS 2023
Year: 2023

We initiate the study of numerical linear algebra in the sliding window model, where only the most recent $W$ updates in a stream form the underlying data set. We first introduce a unified row-sampling based framework that gives randomized algorithms for spectral approximation, low-rank approximation/projection-cost preservation, and $\ell_1$-subspace embeddings in the sliding window model, which often use nearly optimal space and achieve nearly input sparsity runtime. Our algorithms are based on "reverse online" versions of offline sampling distributions such as (ridge) leverage scores, $\ell_1$ sensitivities, and Lewis weights to quantify both the importance and the recency of a row. Our row-sampling framework rather surprisingly implies connections to the well-studied online model; our structural results also give the first sample optimal (up to lower order terms) online algorithm for low-rank approximation/projection-cost preservation. Using this powerful primitive, we give online algorithms for column/row subset selection and principal component analysis that resolves the main open question of Bhaskara et. al.,(FOCS 2019). We also give the first online algorithm for $\ell_1$-subspace embeddings. We further formalize the connection between the online model and the sliding window model by introducing an additional unified framework for deterministic algorithms using a merge and reduce paradigm and the concept of online coresets. Our sampling based algorithms in the row-arrival online model yield online coresets, giving deterministic algorithms for spectral approximation, low-rank approximation/projection-cost preservation, and $\ell_1$-subspace embeddings in the sliding window model that use nearly optimal space.
More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
Venue: arXiv cs.DS 2023
Year: 2023

In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. We design a meta-algorithm that solves all these problems and whose running time is upper bounded by $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ where $k$ is respectively the clique-width, $\mathbf{Q}$-rank-width, rank-width and maximum induced matching width of a given decomposition. Our approach simplifies and unifies the known algorithms for each of the parameters and its running time matches asymptotically also the running times of the best known algorithms for basic NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the $d$-neighbor equivalence defined in [Bui-Xuan, Telle and Vatshelle, TCS 2013] and the rank-based approach introduced in [Bodlaender, Cygan, Kratsch and Nederlof, ICALP 2013]. The results we obtain highlight the importance of the $d$-neighbor equivalence relation on the algorithmic applications of width measures. We also prove that our framework could be useful for $W[1]$-hard problems parameterized by clique-width such as Max Cut and Maximum Minimal Cut. For these latter problems, we obtain $n^{O(k)}$, $n^{O(k)}$ and $n^{2^{O(k)}}$ time algorithms where $k$ is respectively the clique-width, the $\mathbf{Q}$-rank-width and the rank-width of the input graph.
Stylized innovation: generating timelines by interrogating incrementally available randomised dictionaries
Venue: arXiv cs.AI 2023
Year: 2023

A key challenge when trying to understand innovation is that it is a dynamic, ongoing process, which can be highly contingent on ephemeral factors such as culture, economics, or luck. This means that any analysis of the real-world process must necessarily be historical - and thus probably too late to be most useful - but also cannot be sure what the properties of the web of connections between innovations is or was. Here I try to address this by designing and generating a set of synthetic innovation web "dictionaries" that can be used to host sampled innovation timelines, probe the overall statistics and behaviours of these processes, and determine the degree of their reliance on the structure or generating algorithm. Thus, inspired by the work of Fink, Reeves, Palma and Farr (2017) on innovation in language, gastronomy, and technology, I study how new symbol discovery manifests itself in terms of additional "word" vocabulary being available from dictionaries generated from a finite number of symbols. Several distinct dictionary generation models are investigated using numerical simulation, with emphasis on the scaling of knowledge as dictionary generators and parameters are varied, and the role of which order the symbols are discovered in.
Perfectly Secure Communication, based on Graph-Topological Addressing in Unique-Neighborhood Networks
Venue: arXiv cs.CR 2023
Year: 2023

We consider network graphs $G=(V,E)$ in which adjacent nodes share common secrets. In this setting, certain techniques for perfect end-to-end security (in the sense of confidentiality, authenticity (implying integrity) and availability, i.e., CIA+) can be made applicable without end-to-end shared secrets and without computational intractability assumptions. To this end, we introduce and study the concept of a unique-neighborhood network, in which nodes are uniquely identifiable upon their graph-topological neighborhood. While the concept is motivated by authentication, it may enjoy wider applicability as being a technology-agnostic (yet topology aware) form of addressing nodes in a network.