OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Square Detection Over General Alphabets
Venue: arXiv cs.DS 2023
Year: 2023

Squares (fragments of the form $xx$, for some string $x$) are arguably the most natural type of repetition in strings. The basic algorithmic question concerning squares is to check if a given string of length $n$ is square-free, that is, does not contain a fragment of such form. Main and Lorentz [J. Algorithms 1984] designed an $\mathcal{O}(n\log n)$ time algorithm for this problem, and proved a matching lower bound assuming the so-called general alphabet, meaning that the algorithm is only allowed to check if two characters are equal. However, their lower bound also assumes that there are $Ω(n)$ distinct symbols in the string. As an open question, they asked if there is a faster algorithm if one restricts the size of the alphabet. Crochemore [Theor. Comput. Sci. 1986] designed a linear-time algorithm for constant-size alphabets, and combined with more recent results his approach in fact implies such an algorithm for linearly-sortable alphabets. Very recently, Ellert and Fischer [ICALP 2021] significantly relaxed this assumption by designing a linear-time algorithm for general ordered alphabets, that is, assuming a linear order on the characters that permits constant time order comparisons. However, the open question of Main and Lorentz from 1984 remained unresolved for general (unordered) alphabets. In this paper, we show that testing square-freeness of a length-$n$ string over general alphabet of size $σ$ can be done with $\mathcal{O}(n\log σ)$ comparisons, and cannot be done with $o(n\log σ)$ comparisons. We complement this result with an $\mathcal{O}(n\log σ)$ time algorithm in the Word RAM model. Finally, we extend the algorithm to reporting all the runs (maximal repetitions) in the same complexity.
Sim-to-Real Deep Reinforcement Learning based Obstacle Avoidance for UAVs under Measurement Uncertainty
Venue: arXiv cs.RO 2023
Year: 2023

Deep Reinforcement Learning is quickly becoming a popular method for training autonomous Unmanned Aerial Vehicles (UAVs). Our work analyzes the effects of measurement uncertainty on the performance of Deep Reinforcement Learning (DRL) based waypoint navigation and obstacle avoidance for UAVs. Measurement uncertainty originates from noise in the sensors used for localization and detecting obstacles. Measurement uncertainty/noise is considered to follow a Gaussian probability distribution with unknown non-zero mean and variance. We evaluate the performance of a DRL agent trained using the Proximal Policy Optimization (PPO) algorithm in an environment with continuous state and action spaces. The environment is randomized with different numbers of obstacles for each simulation episode in the presence of varying degrees of noise, to capture the effects of realistic sensor measurements. Denoising techniques like the low pass filter and Kalman filter improve performance in the presence of unbiased noise. Moreover, we show that artificially injecting noise into the measurements during evaluation actually improves performance in certain scenarios. Extensive training and testing of the DRL agent under various UAV navigation scenarios are performed in the PyBullet physics simulator. To evaluate the practical validity of our method, we port the policy trained in simulation onto a real UAV without any further modifications and verify the results in a real-world environment.
Computational bounds for the 2048 game
Venue: arXiv cs.DS 2023
Year: 2023

2048 is a single player video game, played by millions mostly on mobile devices. We prove rigorously for the first time that there is an algorithm with winning probability at least 0.99969, and that there is a strategy for achieving the 256 tile guaranteed (with probability 1).
Control of synaptic plasticity in neural networks
Venue: arXiv cs.NE 2023
Year: 2023

The brain is a nonlinear and highly Recurrent Neural Network (RNN). This RNN is surprisingly plastic and supports our astonishing ability to learn and execute complex tasks. However, learning is incredibly complicated due to the brain's nonlinear nature and the obscurity of mechanisms for determining the contribution of each synapse to the output error. This issue is known as the Credit Assignment Problem (CAP) and is a fundamental challenge in neuroscience and Artificial Intelligence (AI). Nevertheless, in the current understanding of cognitive neuroscience, it is widely accepted that a feedback loop systems play an essential role in synaptic plasticity. With this as inspiration, we propose a computational model by combining Neural Networks (NN) and nonlinear optimal control theory. The proposed framework involves a new NN-based actor-critic method which is used to simulate the error feedback loop systems and projections on the NN's synaptic plasticity so as to ensure that the output error is minimized.
Drawings of Complete Multipartite Graphs Up to Triangle Flips
Venue: arXiv cs.CG 2023
Year: 2023

For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended rotation system (ERS) of the drawing is the collection of the rotations of all vertices and crossings. A drawing is simple if each pair of edges has at most one common point. Gioan's Theorem states that for any two simple drawings of the complete graph $K_n$ with the same crossing edge pairs, one drawing can be transformed into the other by a sequence of triangle flips (a.k.a. Reidemeister moves of Type 3). This operation refers to the act of moving one edge of a triangular cell formed by three pairwise crossing edges over the opposite crossing of the cell, via a local transformation. We investigate to what extent Gioan-type theorems can be obtained for wider classes of graphs. A necessary (but in general not sufficient) condition for two drawings of a graph to be transformable into each other by a sequence of triangle flips is that they have the same ERS. As our main result, we show that for the large class of complete multipartite graphs, this necessary condition is in fact also sufficient. We present two different proofs of this result, one of which is shorter, while the other one yields a polynomial time algorithm for which the number of needed triangle flips for graphs on $n$ vertices is bounded by $O(n^{16})$. The latter proof uses a Carathéodory-type theorem for simple drawings of complete multipartite graphs, which we believe to be of independent interest. Moreover, we show that our Gioan-type theorem for complete multipartite graphs is essentially tight in the sense that having the same ERS does not remain sufficient when removing or adding very few edges.
GazePair: Efficient Pairing of Augmented Reality Devices Using Gaze Tracking
Venue: arXiv cs.CR 2023
Year: 2023

As Augmented Reality (AR) devices become more prevalent and commercially viable, the need for quick, efficient, and secure schemes for pairing these devices has become more pressing. Current methods to securely exchange holograms require users to send this information through large data centers, creating security and privacy concerns. Existing techniques to pair these devices on a local network and share information fall short in terms of usability and scalability. These techniques either require hardware not available on AR devices, intricate physical gestures, removal of the device from the head, do not scale to multiple pairing partners, or rely on methods with low entropy to create encryption keys. To that end, we propose a novel pairing system, called GazePair, that improves on all existing local pairing techniques by creating an efficient, effective, and intuitive pairing protocol. GazePair uses eye gaze tracking and a spoken key sequence cue (KSC) to generate identical, independently generated symmetric encryption keys with 64 bits of entropy. GazePair also achieves improvements in pairing success rates and times over current methods. Additionally, we show that GazePair can extend to multiple users. Finally, we assert that GazePair can be used on any Mixed Reality (MR) device equipped with eye gaze tracking.
Infra-Red, In-Situ (IRIS) Inspection of Silicon
Venue: arXiv cs.AR 2023
Year: 2023

This paper introduces the Infra-Red, In Situ (IRIS) inspection method, which uses short-wave IR (SWIR) light to non-destructively "see through" the backside of chips and image them with lightly modified conventional digital CMOS cameras. With a ~1050 nm light source, IRIS is capable of constraining macro- and meso-scale features of a chip. This hardens existing micro-scale self-test verification techniques by ruling out the existence of extra circuitry that can hide a hardware trojan with a test bypass. Thus, self-test techniques used in conjunction with IRIS can ensure the correct construction of security-critical hardware at all size scales.
End-to-end Deformable Attention Graph Neural Network for Single-view Liver Mesh Reconstruction
Venue: arXiv cs.CV 2023
Year: 2023

Intensity modulated radiotherapy (IMRT) is one of the most common modalities for treating cancer patients. One of the biggest challenges is precise treatment delivery that accounts for varying motion patterns originating from free-breathing. Currently, image-guided solutions for IMRT is limited to 2D guidance due to the complexity of 3D tracking solutions. We propose a novel end-to-end attention graph neural network model that generates in real-time a triangular shape of the liver based on a reference segmentation obtained at the preoperative phase and a 2D MRI coronal slice taken during the treatment. Graph neural networks work directly with graph data and can capture hidden patterns in non-Euclidean domains. Furthermore, contrary to existing methods, it produces the shape entirely in a mesh structure and correctly infers mesh shape and position based on a surrogate image. We define two on-the-fly approaches to make the correspondence of liver mesh vertices with 2D images obtained during treatment. Furthermore, we introduce a novel task-specific identity loss to constrain the deformation of the liver in the graph neural network to limit phenomenons such as flying vertices or mesh holes. The proposed method achieves results with an average error of 3.06 +- 0.7 mm and Chamfer distance with L2 norm of 63.14 +- 27.28.
On the ethics of constructing conscious AI
Venue: arXiv cs.AI 2023
Year: 2023

In its pragmatic turn, the new discipline of AI ethics came to be dominated by humanity's collective fear of its creatures, as reflected in an extensive and perennially popular literary tradition. Dr. Frankenstein's monster in the novel by Mary Shelley rising against its creator; the unorthodox golem in H. Leivick's 1920 play going on a rampage; the rebellious robots of Karel Čapek -- these and hundreds of other examples of the genre are the background against which the preoccupation of AI ethics with preventing robots from behaving badly towards people is best understood. In each of these three fictional cases (as well as in many others), the miserable artificial creature -- mercilessly exploited, or cornered by a murderous mob, and driven to violence in self-defense -- has its author's sympathy. In real life, with very few exceptions, things are different: theorists working on the ethics of AI completely ignore the possibility of robots needing protection from their creators. The present book chapter takes up this, less commonly considered, ethical angle of AI.
Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
Venue: arXiv cs.DS 2023
Year: 2023

We investigate a relaxation of the notion of treewidth-fragility, namely tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for independent packing problems on fractionally tree-independence-number-fragile graph classes. Our approach unifies and extends several known polynomial-time approximation schemes on seemingly unrelated graph classes, such as classes of intersection graphs of fat objects in a fixed dimension or proper minor-closed classes. We also study the related notion of layered tree-independence number, a relaxation of layered treewidth.
Low Complexity Time Synchronization for Zero-padding based Waveforms
Venue: arXiv cs.IT 2023
Year: 2023

The discussion on using zero padding (ZP) instead of a cyclic prefix (CP) for enhancing channel estimation and equalization performance is a recurring topic in waveform design for future wireless systems that high spectral efficiency and location awareness are the key factors. This is particularly true for orthogonal signals, such as orthogonal frequency-division multiplexing (OFDM). ZP-OFDM is appealing for joint communications and sensing (JCS) in 6G networks because it takes the advantage of both OFDM and pulse radar. In term of communication, ZP-OFDM compared to CP-OFDM, has higher power efficiency and lower bit error rate (BER). However, time synchronization is challenging in ZP-OFDM systems due to the lack of CP. In terms of sensing, ZP facilitates ranging methods, such as time-sum-of-arrival (TSOA). In this paper, we propose a moment-based timing offset (TO) estimator for multiple-input multiple-output (MIMO) ZP-OFDM system without the need for pilots. We then introduce the which significantly improves the estimation accuracy of the previous estimator. We show that the proposed method asymptotically reaches the maximum likelihood (ML) estimator. Simulation results show very high probability of lock-in for the proposed estimators under various practical scenarios.
Using channel correlation to improve decoding -- ORBGRAND-AI
Venue: arXiv cs.IT 2023
Year: 2023

To meet the Ultra Reliable Low Latency Communication (URLLC) needs of modern applications, there have been significant advances in the development of short error correction codes and corresponding soft detection decoders. A substantial hindrance to delivering low-latency is, however, the reliance on interleaving to break up omnipresent channel correlations to ensure that decoder input matches decoder assumptions. Consequently, even when using short codes, the need to wait to interleave data at the sender and de-interleave at the receiver results in significant latency that acts contrary to the goals of URLLC. Moreover, interleaving reduces channel capacity, so that potential decoding performance is degraded. Here we introduce a variant of Ordered Reliability Bits Guessing Random Additive Noise Decoding (ORBGRAND), which we call ORBGRAND-Approximate Independence (ORBGRAND-AI), a soft-detection decoder that can decode any moderate redundancy code and overcomes the limitation of existing decoding paradigms by leveraging channel correlations and circumventing the need for interleaving. By leveraging correlation, not only is latency reduced, but error correction performance can be enhanced by multiple dB, while decoding complexity is also reduced, offering one potential solution for the provision of URLLC.
Superhuman Artificial Intelligence Can Improve Human Decision Making by Increasing Novelty
Venue: arXiv cs.AI 2023
Year: 2023

How will superhuman artificial intelligence (AI) affect human decision making? And what will be the mechanisms behind this effect? We address these questions in a domain where AI already exceeds human performance, analyzing more than 5.8 million move decisions made by professional Go players over the past 71 years (1950-2021). To address the first question, we use a superhuman AI program to estimate the quality of human decisions across time, generating 58 billion counterfactual game patterns and comparing the win rates of actual human decisions with those of counterfactual AI decisions. We find that humans began to make significantly better decisions following the advent of superhuman AI. We then examine human players' strategies across time and find that novel decisions (i.e., previously unobserved moves) occurred more frequently and became associated with higher decision quality after the advent of superhuman AI. Our findings suggest that the development of superhuman AI programs may have prompted human players to break away from traditional strategies and induced them to explore novel moves, which in turn may have improved their decision-making.
The Evaluation of a New Daylighting System's Energy Performance: Reversible Daylighting System (RDS)
Venue: arXiv cs.CY 2023
Year: 2023

This paper evaluates the energy performance of a new daylighting system, patented by the author, in a regular closed office space. The advantage of this new system as opposed to conventional venetian blinds is its rotating capability, which improves the energy efficiency of the space. Computer simulation method has been conducted to examine the performance of this new system on the south aperture of a closed-office space with 30% Window to Wall ratio (WWR) in three cities in Iran with different climate zones based on ASHRAE: Tehran (3B), Tabriz (4B), and Yazd (2B). The simulation has been implemented in Honeybee platform with EnergyPlus engine to simulate the combined total load consisting of heating, cooling, and lighting loads. To control lighting, a dimming control is applied to the space. The results of the study represent the benefits of the reversible daylighting system (RDS) over the state of the art venetian blinds to improve the energy efficiency of the space through just changing the location of the blind during heating/cooling demand time of the year.
Investigating the Characteristics and Performance of Augmented Reality Applications on Head-Mounted Displays: A Study of the Hololens Application Store
Venue: arXiv cs.MM 2023
Year: 2023

Augmented Reality (AR) based on Head-Mounted Displays (HMDs) has gained significant traction over the recent years. Nevertheless, it remains unclear what AR HMD-based applications have been developed over the years and what their system performance is when they are run on HMDs. In this paper, we aim to shed light into this direction. Our study focuses on the applications available on the Microsoft Hololens application store given the wide use of the Hololens headset. Our study has two major parts: (i) we collect metadata about the applications available on the Microsoft Hololens application store to understand their characteristics (e.g., categories, pricing, permissions requested, hardware and software compatibility); and (ii) we interact with these applications while running on a Hololens 2 headset and collect data about systems-related metrics (e.g., memory and storage usage, time spent on CPU and GPU related operations) to investigate the systems performance of applications. Our study has resulted in several interesting findings, which we share with the research community.
Automated Vulnerability Detection in Source Code Using Quantum Natural Language Processing
Venue: arXiv cs.LG 2023
Year: 2023

One of the most important challenges in the field of software code audit is the presence of vulnerabilities in software source code. These flaws are highly likely ex-ploited and lead to system compromise, data leakage, or denial of ser-vice. C and C++ open source code are now available in order to create a large-scale, classical machine-learning and quantum machine-learning system for function-level vulnerability identification. We assembled a siz-able dataset of millions of open-source functions that point to poten-tial exploits. We created an efficient and scalable vulnerability detection method based on a deep neural network model Long Short Term Memory (LSTM), and quantum machine learning model Long Short Term Memory (QLSTM), that can learn features extracted from the source codes. The source code is first converted into a minimal intermediate representation to remove the pointless components and shorten the de-pendency. Therefore, We keep the semantic and syntactic information using state of the art word embedding algorithms such as Glove and fastText. The embedded vectors are subsequently fed into the classical and quantum convolutional neural networks to classify the possible vulnerabilities. To measure the performance, we used evaluation metrics such as F1 score, precision, re-call, accuracy, and total execution time. We made a comparison between the results derived from the classical LSTM and quantum LSTM using basic feature representation as well as semantic and syntactic represen-tation. We found that the QLSTM with semantic and syntactic features detects significantly accurate vulnerability and runs faster than its classical counterpart.
The Life Cycle of Knowledge in Big Language Models: A Survey
Venue: arXiv cs.CL 2023
Year: 2023

Knowledge plays a critical role in artificial intelligence. Recently, the extensive success of pre-trained language models (PLMs) has raised significant attention about how knowledge can be acquired, maintained, updated and used by language models. Despite the enormous amount of related studies, there still lacks a unified view of how knowledge circulates within language models throughout the learning, tuning, and application processes, which may prevent us from further understanding the connections between current progress or realizing existing limitations. In this survey, we revisit PLMs as knowledge-based systems by dividing the life circle of knowledge in PLMs into five critical periods, and investigating how knowledge circulates when it is built, maintained and used. To this end, we systematically review existing studies of each period of the knowledge life cycle, summarize the main challenges and current limitations, and discuss future directions.
Clustering with Simplicial Complexes
Venue: arXiv cs.LG 2023
Year: 2023

In this work, we propose a new clustering algorithm to group nodes in networks based on second-order simplices (aka filled triangles) to leverage higher-order network interactions. We define a simplicial conductance function, which on minimizing, yields an optimal partition with a higher density of filled triangles within the set while the density of filled triangles is smaller across the sets. To this end, we propose a simplicial adjacency operator that captures the relation between the nodes through second-order simplices. This allows us to extend the well-known Cheeger inequality to cluster a simplicial complex. Then, leveraging the Cheeger inequality, we propose the simplicial spectral clustering algorithm. We report results from numerical experiments on synthetic and real-world network data to demonstrate the efficacy of the proposed approach.
Carbon-Neutralized Joint User Association and Base Station Switching for Green Cellular Networks
Venue: arXiv cs.DC 2023
Year: 2023

Mitigating climate change and its impacts is one of the sustainable development goals (SDGs) required by United Nations for an urgent action. Increasing carbon emissions due to human activities is the root cause to climate change. Telecommunication networks that provide service connectivity to mobile users contribute great amount of carbon emissions by consuming lots of non-renewable energy sources. Beyond the improvement on energy efficiency, to reduce the carbon footprint, telecom operators are increasing their adoption of renewable energy (e.g., wind power). The high variability of renewable energy in time and location; however, creates difficulties for operators when utilizing renewables for the reduction of carbon emissions. In this paper, we consider a heterogeneous network consisted of one macro base station (MBS) and multiple small base stations (SBSs) where each base station (BS) is powered by both of renewable and non-renewable energy. Different from the prior works that target on the total power consumption, we propose a novel scheme to minimize the carbon footprint of networks by dynamically switching the ON/OFF modes of SBSs and adjusting the association between users and BSs to access renewables as much as possible. Our numerical analysis shows that the proposed scheme significantly reduces up to 86% of the nonrenewable energy consumption compared to two representative baselines.