OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic data structures for parameterized string problems
Venue: arXiv cs.DS 2022
Year: 2022

We revisit classic string problems considered in the area of parameterized complexity, and study them through the lens of dynamic data structures. That is, instead of asking for a static algorithm that solves the given instance efficiently, our goal is to design a data structure that efficiently maintains a solution, or reports a lack thereof, upon updates in the instance. We first consider the Closest String problem, for which we design randomized dynamic data structures with amortized update times $d^{\mathcal{O}(d)}$ and $|Σ|^{\mathcal{O}(d)}$, respectively, where $Σ$ is the alphabet and $d$ is the assumed bound on the maximum distance. These are obtained by combining known static approaches to Closest String with color-coding. Next, we note that from a result of Frandsen et al.~[J. ACM'97] one can easily infer a meta-theorem that provides dynamic data structures for parameterized string problems with worst-case update time of the form $\mathcal{O}(\log \log n)$, where $k$ is the parameter in question and $n$ is the length of the string. We showcase the utility of this meta-theorem by giving such data structures for problems Disjoint Factors and Edit Distance. We also give explicit data structures for these problems, with worst-case update times $\mathcal{O}(k2^{k}\log \log n)$ and $\mathcal{O}(k^2\log \log n)$, respectively. Finally, we discuss how a lower bound methodology introduced by Amarilli et al.~[ICALP'21] can be used to show that obtaining update time $\mathcal{O}(f(k))$ for Disjoint Factors and Edit Distance is unlikely already for a constant value of the parameter $k$.
Can Information Behaviour Inform Machine Learning?
Venue: arXiv cs.LG 2022
Year: 2022

The objective of this paper is to explore the opportunities for human information behaviour research to inform and influence the field of machine learning and the resulting machine information behaviour. Using the development of foundation models in machine learning as an example, the paper illustrates how human information behaviour research can bring to machine learning a more nuanced view of information and informing, a better understanding of information need and how that affects the communication among people and systems, guidance on the nature of context and how to operationalize that in models and systems, and insights into bias, misinformation, and marginalization. Despite their clear differences, the fields of information behaviour and machine learning share many common objectives, paradigms, and key research questions. The example of foundation models illustrates that human information behaviour research has much to offer in addressing some of the challenges emerging in the nascent area of machine information behaviour.
A Position-Free Path Integral for Homogeneous Slabs and Multiple Scattering on Smith Microfacets
Venue: arXiv cs.GR 2022
Year: 2022

We consider the problem of multiple scattering on Smith microfacets. This problem is equivalent to computing volumetric light transport in a homogeneous slab. Although the symmetry of the slab allows for significant simplification, fully analytic solutions are scarce and not general enough for most applications. Standard Monte Carlo simulation, although general, is expensive and leads to variance that must be dealt with. We present the first unbiased, truly position-free path integral for evaluating the BSDF of a homogeneous slab. We collapse the spatially-1D path integral of previous works to a position-free form using an analytical preintegration of collision distances. Evaluation of the resulting path integral, which now contains only directions, reduces to simple recursive manipulation of exponential distributions. Applying Monte Carlo to solve the reduced integration problem leads to lower variance. Our new algorithm allows us to render multiple scattering on Smith microfacets with less variance than prior work, and, in the case of conductors, to do so without any bias. Additionally, our algorithm can also be used to accelerate the rendering of BSDFs containing volumetrically scattering layers, at reduced variance compared to standard Monte Carlo integration.
A Unified Approach to Semantic Information and Communication based on Probabilistic Logic
Venue: arXiv cs.IT 2022
Year: 2022

Traditionally, studies on technical communication (TC) are based on stochastic modeling and manipulation. This is not sufficient for semantic communication (SC) where semantic elements are logically connected, rather than stochastically correlated. To fill this void, by leveraging a logical programming language called probabilistic logic (ProbLog), we propose a unified approach to semantic information and communication through the interplay between TC and SC. On top of the well-established existing TC layer, we introduce a SC layer that utilizes knowledge bases of communicating parties for the exchange of semantic information. These knowledge bases are logically described, manipulated, and exploited using ProbLog. To make these SC and TC layers interact, we propose various measures based on the entropy of a clause in a knowledge base. These measures allow us to delineate various technical issues on SC such as a message selection problem for improving the knowledge base at a receiver. Extending this, we showcase selected examples in which SC and TC layers interact with each other while taking into account constraints on physical channels and efficiently utilizing channel resources.
A Two Parameters Equation for Word Rank-Frequency Relation
Venue: arXiv cs.CL 2022
Year: 2022

Let $f (\cdot)$ be the absolute frequency of words and $r$ be the rank of words in decreasing order of frequency, then the following function can fit the rank-frequency relation \[ f (r;s,t) = \left(\frac{r_{\tt max}}{r}\right)^{1-s} \left(\frac{r_{\tt max}+t \cdot r_{\tt exp}}{r+t \cdot r_{\tt exp}}\right)^{1+(1+t)s} \] where $r_{\tt max}$ and $r_{\tt exp}$ are the maximum and the expectation of the rank, respectively; $s>0$ and $t>0$ are parameters estimated from data. On well-behaved data, there should be $s<1$ and $s \cdot t < 1$.
Giallar: Push-Button Verification for the Qiskit Quantum Compiler
Venue: arXiv cs.PL 2022
Year: 2022

This paper presents Giallar, a fully-automated verification toolkit for quantum compilers. Giallar requires no manual specifications, invariants, or proofs, and can automatically verify that a compiler pass preserves the semantics of quantum circuits. To deal with unbounded loops in quantum compilers, Giallar abstracts three loop templates, whose loop invariants can be automatically inferred. To efficiently check the equivalence of arbitrary input and output circuits that have complicated matrix semantics representation, Giallar introduces a symbolic representation for quantum circuits and a set of rewrite rules for showing the equivalence of symbolic quantum circuits. With Giallar, we implemented and verified 44 (out of 56) compiler passes in 13 versions of the Qiskit compiler, the open-source quantum compiler standard, during which three bugs were detected in and confirmed by Qiskit. Our evaluation shows that most of Qiskit compiler passes can be automatically verified in seconds and verification imposes only a modest overhead to compilation performance.
Initial Beamforming for Millimeter-Wave and Terahertz Communications in 6G Mobile Systems
Venue: arXiv cs.IT 2022
Year: 2022

To meet the demand of supreme data rates in terabits-per-second, the next-generation mobile system needs to exploit the abundant spectrum in the millimeter-wave and terahertz bands. However, high-frequency transmission heavily relies on large-scale antenna arrays to reap high beamforming gain, used to compensate for severe propagation loss. It raises a problem of omni-directional beamforming during the phase of initial access, where a base station is required to broadcast synchronization signals and system information to all users within its coverage. This paper proposes a novel initial beamforming scheme, which provides instantaneous gain equally in all directions by forming a pair of complementary beams. Numerical results verify that it can achieve omni-directional coverage with the optimal performance that remarkably outperforms the previous scheme called random beamforming. It is applicable for any form of large-scale arrays, and all three architecture, i.e., digital, analog, and hybrid beamforming.
What a Publication Tells You -- Benefits of Narrative Information Access in Digital Libraries
Venue: arXiv cs.DL 2022
Year: 2022

Knowledge bases allow effective access paths in digital libraries. Here users can specify their information need as graph patterns for precise searches and structured overviews (by allowing variables in queries). But especially when considering textual sources that contain narrative information, i.e., short stories of interest, harvesting statements from them to construct knowledge bases may be a serious threat to the statements' validity. A piece of information, originally stated in a coherent line of arguments, could be used in a knowledge base query processing without considering its vital context conditions. And this can lead to invalid results. That is why we argue to move towards narrative information access by considering contexts in the query processing step. In this way digital libraries can allow users to query for narrative information and supply them with valid answers. In this paper we define narrative information access, demonstrate its benefits for Covid 19 related questions, and argue on the generalizability for other domains such as political sciences.
Automated Driving Systems: Impact of Haptic Guidance on Driving Performance after a Take Over Request
Venue: arXiv cs.HC 2022
Year: 2022

In conditional automation, a response from the driver is expected when a take over request is issued due to unexpected events, emergencies, or reaching the operational design domain boundaries. Cooperation between the automated driving system and the driver can help to guarantee a safe and pleasant transfer if the driver is guided through a haptic guidance system that applies a slight counter-steering force to the steering wheel. We examine in this work the impact of haptic guidance systems on driving performance after a take over request was triggered to avoid sudden obstacles on the road. We studied different driver conditions that involved Non-Driving Related Tasks (NRDT). Results showed that haptic guidance systems increased road safety by reducing the lateral error, the distance and reaction time to a sudden obstacle and the number of collisions.
La Résistance: Harnessing Heterogeneous Resources for Adaptive Resiliency in 6G Networks
Venue: arXiv cs.NI 2022
Year: 2022

Recent years have seen more critical applications designed to protect human lives (e.g., environmental sensing, emergency response, and tactical defense) being deployed over wireless networks. These critical deployments expect higher data rates, ultra-low latency, and ultra-high reliability. 6G wireless networks are expected to fill the gap in terms of the first two aspects (i.e., higher data rates and ultra-low latency), however providing ultra-high reliability is a wide open challenge. All is well when everything works but when there is a failure or a security attack, the entire system collapses exposing the associated human lives to imminent danger. Avoiding this requires the strongest of assurances that safety and security aspects are protected no matter what. Large scale critical applications are waiting for this piece of the puzzle to be solved. At this juncture, we envision the bold theme of La Résistance 6G (LR6G) that would pave the way for deploying mission-critical applications and services over 6G networks. It aims to achieve ultra-high reliability and resiliency to any disruptions, be it failures or security attacks. A few disruptions are easy to handle such as a cloud VM or primary link failure. In both of these cases, applications can be restored by activating the standby resource. However, some disruptions can be detrimental such as when a cut-vertex fails or when the disruption leaves the critical application to fail without access to a standby resource. These critical applications (e.g. Smart Manufacturing, Smart City, Ocean monitoring, Wildfire monitoring, etc.) are highly distributed in nature. They must continue to deliver their mission objectives during a disruption to protect human lives. In this paper, we present our LR6G vision and outline the challenges towards achieving this vision.
Adaptive Task Planning for Large-Scale Robotized Warehouses
Venue: arXiv cs.RO 2022
Year: 2022

Robotized warehouses are deployed to automatically distribute millions of items brought by the massive logistic orders from e-commerce. A key to automated item distribution is to plan paths for robots, also known as task planning, where each task is to deliver racks with items to pickers for processing and then return the rack back. Prior solutions are unfit for large-scale robotized warehouses due to the inflexibility to time-varying item arrivals and the low efficiency for high throughput. In this paper, we propose a new task planning problem called TPRW, which aims to minimize the end-to-end makespan that incorporates the entire item distribution pipeline, known as a fulfilment cycle. Direct extensions from state-of-the-art path finding methods are ineffective to solve the TPRW problem because they fail to adapt to the bottleneck variations of fulfillment cycles. In response, we propose Efficient Adaptive Task Planning, a framework for large-scale robotized warehouses with time-varying item arrivals. It adaptively selects racks to fulfill at each timestamp via reinforcement learning, accounting for the time-varying bottleneck of the fulfillment cycles. Then it finds paths for robots to transport the selected racks. The framework adopts a series of efficient optimizations on both time and memory to handle large-scale item throughput. Evaluations on both synthesized and real data show an improvement of $37.1\%$ in effectiveness and $75.5\%$ in efficiency over the state-of-the-arts.
APP-Net: Auxiliary-point-based Push and Pull Operations for Efficient Point Cloud Classification
Venue: arXiv cs.CV 2022
Year: 2022

Aggregating neighbor features is essential for point cloud classification. In the existing work, each point in the cloud may inevitably be selected as the neighbors of multiple aggregation centers, as all centers will gather neighbor features from the whole point cloud independently. Thus each point has to participate in the calculation repeatedly and generates redundant duplicates in the memory, leading to intensive computation costs and memory consumption. Meanwhile, to pursue higher accuracy, previous methods often rely on a complex local aggregator to extract fine geometric representation, which further slows down the classification pipeline. To address these issues, we propose a new local aggregator of linear complexity for point cloud classification, coined as APP. Specifically, we introduce an auxiliary container as an anchor to exchange features between the source point and the aggregating center. Each source point pushes its feature to only one auxiliary container, and each center point pulls features from only one auxiliary container. This avoids the re-computation issue of each source point. To facilitate the learning of the local structure of cloud point, we use an online normal estimation module to provide the explainable geometric information to enhance our APP modeling capability. Our built network is more efficient than all the previous baselines with a clear margin while still consuming a lower memory. Experiments on both synthetic and real datasets demonstrate that APP-Net reaches comparable accuracies to other networks. It can process more than 10,000 samples per second with less than 10GB of memory on a single GPU. We will release the code in https://github.com/MCG-NJU/APP-Net.
Power to the springs: Passive elements are sufficient to drive push-off in human walking
Venue: arXiv cs.RO 2022
Year: 2022

For the impulsive ankle push-off (APO) observed in human walking two muscle-tendon-units (MTUs) spanning the ankle joint play an important role: Gastrocnemius (GAS) and Soleus (SOL). GAS and SOL load the Achilles tendon to store elastic energy during stance followed by a rapid energy release during APO. We use a neuromuscular simulation (NMS) and a bipedal robot to investigate the role of GAS and SOL on the APO. We optimize the simulation for a robust gait and then sequentially replace the MTUs of (1) GAS, (2) SOL and (3) GAS and SOL by linear springs. To validate the simulation, we implement NMS-3 on a bipedal robot. Simulation and robot walk steady for all trials showing an impulsive APO. Our results imply that the elastic MTU properties shape the impulsive APO. For prosthesis or robot design that is, no complex ankle actuation is needed to obtain an impulsive APO, if more mechanical intelligence is incorporated in the design.
Studying Retrievability of Publications and Datasets in an Integrated Retrieval System
Venue: arXiv cs.IR 2022
Year: 2022

In this paper, we investigate the retrievability of datasets and publications in a real-life Digital Library (DL). The measure of retrievability was originally developed to quantify the influence that a retrieval system has on the access to information. Retrievability can also enable DL engineers to evaluate their search engine to determine the ease with which the content in the collection can be accessed. Following this methodology, in our study, we propose a system-oriented approach for studying dataset and publication retrieval. A speciality of this paper is the focus on measuring the accessibility biases of various types of DL items and including a metric of usefulness. Among other metrics, we use Lorenz curves and Gini coefficients to visualize the differences of the two retrievable document types (specifically datasets and publications). Empirical results reported in the paper show a distinguishable diversity in the retrievability scores among the documents of different types.
Multi-dimensional parameter-space partitioning of spatio-temporal simulation ensembles
Venue: arXiv cs.HC 2022
Year: 2022

Numerical simulations are commonly used to understand the parameter dependence of given spatio-temporal phenomena. Sampling a multi-dimensional parameter space and running the respective simulations leads to an ensemble of a large number of spatio-temporal simulation runs. A main objective for analyzing the ensemble is to partition (or segment) the multi-dimensional parameter space into connected regions of simulation runs with similar behavior. To facilitate such an analysis, we propose a novel visualization method for multi-dimensional parameter-space partitions. Our visualization is based on the concept of a hyper-slicer, which allows for undistorted views of the parameter-space segments' extent and transitions. For navigation within the parameter space, interactions with a 2D embedding of the parameter-space samples, including their segment memberships, are supported. Parameter-space partitions are generated in a semi-automatic fashion by analyzing the similarity space of the ensemble's simulation runs. Clusters of similar simulation runs induce the segments of the parameter-space partition. We link the parameter-space partitioning visualizations to similarity-space visualizations of the ensemble's simulation runs and embed them into an interactive visual analysis tool that supports the analysis of all facets of the spatio-temporal simulation ensemble targeted at the overarching goal of analyzing the parameter-space partitioning. The partitioning can then be visually analyzed and interactively refined. We evaluated our approach with experts within case studies from three different domains.
A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits
Venue: arXiv cs.LG 2022
Year: 2022

The stochastic $K$-armed bandit problem has been studied extensively due to its applications in various domains ranging from online advertising to clinical trials. In practice however, the number of arms can be very large resulting in large memory requirements for simultaneously processing them. In this paper we consider a streaming setting where the arms are presented in a stream and the algorithm uses limited memory to process these arms. Here, the goal is not only to minimize regret, but also to do so in minimal memory. Previous algorithms for this problem operate in one of the two settings: they either use $Ω(\log \log T)$ passes over the stream (Rathod, 2021; Chaudhuri and Kalyanakrishnan, 2020; Liau et al., 2018), or just a single pass (Maiti et al., 2021). In this paper we study the trade-off between memory and regret when $B$ passes over the stream are allowed, for any $B \geq 1$, and establish tight regret upper and lower bounds for any $B$-pass algorithm. Our results uncover a surprising *sharp transition phenomenon*: $O(1)$ memory is sufficient to achieve $\widetildeΘ\Big(T^{\frac{1}{2} + \frac{1}{2^{B+2}-2}}\Big)$ regret in $B$ passes, and increasing the memory to any quantity that is $o(K)$ has almost no impact on further reducing this regret, unless we use $Ω(K)$ memory. Our main technical contribution is our lower bound which requires the use of information-theoretic techniques as well as ideas from round elimination to show that the *residual problem* remains challenging over subsequent passes.
Big Tech Companies Impact on Research at the Faculty of Information Technology and Electrical Engineering
Venue: arXiv cs.CY 2022
Year: 2022

Artificial intelligence is gaining momentum, ongoing pandemic is fuel to that with more opportunities in every sector specially in health and education sector. But with the growth in technology, challenges associated with ethics also grow (Katharine Schwab, 2021). Whenever a new AI product is developed, companies publicize that their systems are transparent, fair, and are in accordance with the existing laws and regulations as the methods and procedures followed by a big tech company for ensuring AI ethics, not only affect the trust and perception of public, but it also challenges the capabilities of the companies towards business strategies in different regions, and the kind of brains it can attract for their projects. AI Big Tech companies have influence over AI ethics as many influencing ethical-AI researchers have roots in Big Tech or its associated labs.
Center-of-Mass-based Robust Grasp Pose Adaptation Using RGBD Camera and Force/Torque Sensing
Venue: arXiv cs.RO 2022
Year: 2022

Object dropping may occur when the robotic arm grasps objects with uneven mass distribution due to additional moments generated by objects' gravity. To solve this problem, we present a novel work that does not require extra wrist and tactile sensors and large amounts of experiments for learning. First, we obtain the center-of-mass position of the rod object using the widely fixed joint torque sensors on the robot arm and RGBD camera. Further, we give the strategy of grasping to improve grasp stability. Simulation experiments are performed in "Mujoco". Results demonstrate that our work is effective in enhancing grasping robustness.
Sharing and Caring: Creating a Culture of Constructive Criticism in Computational Legal Studies
Venue: arXiv cs.CY 2022
Year: 2022

We introduce seven foundational principles for creating a culture of constructive criticism in computational legal studies. Beginning by challenging the current perception of papers as the primary scholarly output, we call for a more comprehensive interpretation of publications. We then suggest to make these publications computationally reproducible, releasing all of the data and all of the code all of the time, on time, and in the most functioning form possible. Subsequently, we invite constructive criticism in all phases of the publication life cycle. We posit that our proposals will help form our field, and float the idea of marking this maturity by the creation of a modern flagship publication outlet for computational legal studies.