OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Decremental Connectivity in Non-Sparse Graphs
Venue: arXiv cs.DS 2021
Year: 2021

We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomized and processes any sequence of edge deletions in $O(m + n \operatorname{polylog} n)$ total time. Interspersed with the deletions, it can answer queries to whether any two given vertices currently belong to the same (2-edge-)connected component in constant time. Our result is based on a general Monte-Carlo randomized reduction from decremental $c$-edge-connectivity to a variant of fully-dynamic $c$-edge-connectivity on a sparse graph. While being Monte-Carlo, our reduction supports a certain final self-check that can be used in Las Vegas algorithms for static problems such as Unique Perfect Matching. For non-sparse graphs with $Ω(n \operatorname{polylog} n)$ edges, our connectivity and $2$-edge-connectivity algorithms handle all deletions in optimal linear total time, using existing algorithms for the respective fully-dynamic problems. This improves upon an $O(m \log (n^2 / m) + n \operatorname{polylog} n)$-time algorithm of Thorup [J.Alg. 1999], which runs in linear time only for graphs with $Ω(n^2)$ edges. Our constant amortized cost for edge deletions in decremental connectivity in non-sparse graphs should be contrasted with an $Ω(\log n/\log\log n)$ worst-case time lower bound in the decremental setting [Alstrup, Thore Husfeldt, FOCS'98] as well as an $Ω(\log n)$ amortized time lower-bound in the fully-dynamic setting [Patrascu and Demaine STOC'04].
Quality-Aware Deep Reinforcement Learning for Streaming in Infrastructure-Assisted Connected Vehicles
Venue: arXiv cs.NI 2021
Year: 2021

This paper proposes a deep reinforcement learning-based video streaming scheme for mobility-aware vehicular networks, e.g., vehicles on the highway. We consider infrastructure-assisted and mmWave-based scenarios in which the macro base station (MBS) cannot directly provide the streaming service to vehicles due to the short range of mmWave beams so that small mmWave base stations (mBSs) along the road deliver the desired videos to users. For a smoother streaming service, the MBS proactively pushes video chunks to mBSs. This is done to support vehicles that are currently covered and/or will be by each mBS. We formulate the dynamic video delivery scheme that adaptively determines 1) which content, 2) what quality and 3) how many chunks to be proactively delivered from the MBS to mBSs using Markov decision process (MDP). Since it is difficult for the MBS to track all the channel conditions and the network states have extensive dimensions, we adopt the deep deterministic policy gradient (DDPG) algorithm for the DRL-based video delivery scheme. This paper finally shows that the DRL agent learns a streaming policy that pursues high average quality while limiting packet drops, avoiding playback stalls, reducing quality fluctuations and saving backhaul usage.
Novel Concepts for Organic Transistors: Physics, Device Design, and Applications
Venue: arXiv cs.ET 2021
Year: 2021

Beyond conventional organic thin-film transistors, this thesis explores possible paths for the fourth wave of organic electronics. In this context, mixed ionic-electronic conductors and organic electro-chemical transistors (OECTs) are identified as highly promising approaches for electronic bio-interfaces enabling ultra-sensitive detection of biological signals. Furthermore, these systems show fundamental properties of biological synapses, namely the synaptic plasticity, which renders the possibility to build brain-inspired, neuromorphic networks enabling highly efficient computing. In particular, the combination of OECTs acting as sensor units and self-learning neural networks at once enables the development of intelligent tags for medical applications. Overall, this thesis adds substantially new insight into the field of organic electronics and draws a vision towards further research and applications. The advancements in the field of vertical organic transistors open new perspectives for the implementation of organic transistors in high-resolution AMOLED displays or radio-frequency identification tags. Furthermore, the exploration of OECTs for neuromorphic computing will create a whole new research field across the disciplines of physics, material, and computer science.
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments
Venue: arXiv cs.DM 2021
Year: 2021

Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the $p$-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of Khot's 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). In this work, we develop a new theory of hypercontractivity on high dimensional expanders (HDX), an important class of expanding complexes that has recently seen similarly impressive applications in both coding theory and approximate sampling. Our results lead to a new understanding of the structure of Boolean functions on HDX, including a tight analog of the KKL Theorem and a new characterization of non-expanding sets. Unlike previous settings satisfying hypercontractivity, HDX can be asymmetric, sparse, and very far from products, which makes the application of traditional proof techniques challenging. We handle these barriers with the introduction of two new tools of independent interest: a new explicit combinatorial Fourier basis for HDX that behaves well under restriction, and a new local-to-global method for analyzing higher moments. Interestingly, unlike analogous second moment methods that apply equally across all types of expanding complexes, our tools rely inherently on simplicial structure. This suggests a new distinction among high dimensional expanders based upon their behavior beyond the second moment.
SummaC: Re-Visiting NLI-based Models for Inconsistency Detection in Summarization
Venue: arXiv cs.CL 2021
Year: 2021

In the summarization domain, a key requirement for summaries is to be factually consistent with the input document. Previous work has found that natural language inference (NLI) models do not perform competitively when applied to inconsistency detection. In this work, we revisit the use of NLI for inconsistency detection, finding that past work suffered from a mismatch in input granularity between NLI datasets (sentence-level), and inconsistency detection (document level). We provide a highly effective and light-weight method called SummaCConv that enables NLI models to be successfully used for this task by segmenting documents into sentence units and aggregating scores between pairs of sentences. On our newly introduced benchmark called SummaC (Summary Consistency) consisting of six large inconsistency detection datasets, SummaCConv obtains state-of-the-art results with a balanced accuracy of 74.4%, a 5% point improvement compared to prior work. We make the models and datasets available: https://github.com/tingofurro/summac
A Survey on Metaverse: the State-of-the-art, Technologies, Applications, and Challenges
Venue: arXiv cs.CY 2021
Year: 2021

Metaverse is a new type of Internet application and social form that integrates a variety of new technologies. It has the characteristics of multi-technology, sociality, and hyper spatiotemporality. This paper introduces the development status of Metaverse, from the five perspectives of network infrastructure, management technology, basic common technology, virtual reality object connection, and virtual reality convergence, it introduces the technical framework of Metaverse. This paper also introduces the nature of Metaverse's social and hyper spatiotemporality, and discusses the first application areas of Metaverse and some of the problems and challenges it may face.
Authentication of optical physical unclonable functions based on single-pixel detection
Venue: arXiv cs.CR 2021
Year: 2021

Physical unclonable function (PUF) has been proposed as a promising and trustworthy solution to a variety of cryptographic applications. Here we propose a non-imaging based authentication scheme for optical PUFs materialized by random scattering media, in which the characteristic fingerprints of optical PUFs are extracted from stochastical fluctuations of the scattered light intensity with respect to laser challenges which are detected by a single-pixel detector. The randomness, uniqueness, unpredictability, and robustness of the extracted fingerprints are validated to be qualified for real authentication applications. By increasing the key length and improving the signal to noise ratio, the false accept rate of a fake PUF can be dramatically lowered to the order of 10^-28. In comparison to the conventional laser-speckle-imaging based authentication with unique identity information obtained from textures of laser speckle patterns, this non-imaging scheme can be implemented at small speckle size bellowing the Nyquist--Shannon sampling criterion of the commonly used CCD or CMOS cameras, offering benefits in system miniaturization and immunity against reverse engineering attacks simultaneously.
EDF-Like Scheduling for Self-Suspending Real-Time Tasks
Venue: arXiv cs.OS 2021
Year: 2021

In real-time systems, schedulability tests are utilized to provide timing guarantees. However, for self-suspending task sets, current suspension-aware schedulability tests are limited to Task-Level Fixed-Priority~(TFP) scheduling or Earliest-Deadline-First~(EDF) with constrained-deadline task systems. In this work we provide a unifying schedulability test for the uniprocessor version of Global EDF-Like (GEL) schedulers and arbitrary-deadline task sets. A large body of existing scheduling algorithms can be considered as EDF-Like, such as EDF, First-In-First-Out~(FIFO), Earliest-Quasi-Deadline-First~(EQDF) and Suspension-Aware EDF~(SAEDF). Therefore, the unifying schedulability test is applicable to those algorithms. Moreover, the schedulability test can be applied to TFP scheduling as well. Our analysis is the first suspension-aware schedulability test applicable to arbitrary-deadline sporadic real-time task systems under Job-Level Fixed-Priority (JFP) scheduling, such as EDF. Moreover, it is the first unifying suspension-aware schedulability test framework that covers a wide range of scheduling algorithms. Through numerical simulations, we show that the schedulability test outperforms the state of the art for EDF under constrained-deadline scenarios. Moreover, we demonstrate the performance of different configurations under EQDF and SAEDF.
Hybrid Super Intelligence and Polymetric Analysis
Venue: arXiv cs.AI 2021
Year: 2021

The problem of possible applications Polymetric Analysis for the resolution problems of artificial Intelligence is discussed. As example the hybrid super intelligence system by N. Moiseev type was selected. The bond between polymetric analysis and hybrid super intelligence system was shown. In operational sense polymetric analysis is more general system. Therefore main principles of Moiseev concept may be unify with the help of polymetric analysis. Main peculiarities of this unification are analyzed.
Unsupervised Online Learning for Robotic Interestingness with Visual Memory
Venue: arXiv cs.RO 2021
Year: 2021

Autonomous robots frequently need to detect "interesting" scenes to decide on further exploration, or to decide which data to share for cooperation. These scenarios often require fast deployment with little or no training data. Prior work considers "interestingness" based on data from the same distribution. Instead, we propose to develop a method that automatically adapts online to the environment to report interesting scenes quickly. To address this problem, we develop a novel translation-invariant visual memory and design a three-stage architecture for long-term, short-term, and online learning, which enables the system to learn human-like experience, environmental knowledge, and online adaption, respectively. With this system, we achieve an average of 20% higher accuracy than the state-of-the-art unsupervised methods in a subterranean tunnel environment. We show comparable performance to supervised methods for robot exploration scenarios showing the efficacy of our approach. We expect that the presented method will play an important role in the robotic interestingness recognition exploration tasks.
Visual Goal-Directed Meta-Learning with Contextual Planning Networks
Venue: arXiv cs.RO 2021
Year: 2021

The goal of meta-learning is to generalize to new tasks and goals as quickly as possible. Ideally, we would like approaches that generalize to new goals and tasks on the first attempt. Toward that end, we introduce contextual planning networks (CPN). Tasks are represented as goal images and used to condition the approach. We evaluate CPN along with several other approaches adapted for zero-shot goal-directed meta-learning. We evaluate these approaches across 24 distinct manipulation tasks using Metaworld benchmark tasks. We found that CPN outperformed several approaches and baselines on one task and was competitive with existing approaches on others. We demonstrate the approach on a physical platform on Jenga tasks using a Kinova Jaco robotic arm.
Quality and Cost Trade-offs in Passage Re-ranking Task
Venue: arXiv cs.IR 2021
Year: 2021

Deep learning models named transformers achieved state-of-the-art results in a vast majority of NLP tasks at the cost of increased computational complexity and high memory consumption. Using the transformer model in real-time inference becomes a major challenge when implemented in production, because it requires expensive computational resources. The more executions of a transformer are needed the lower the overall throughput is, and switching to the smaller encoders leads to the decrease of accuracy. Our paper is devoted to the problem of how to choose the right architecture for the ranking step of the information retrieval pipeline, so that the number of required calls of transformer encoder is minimal with the maximum achievable quality of ranking. We investigated several late-interaction models such as Colbert and Poly-encoder architectures along with their modifications. Also, we took care of the memory footprint of the search index and tried to apply the learning-to-hash method to binarize the output vectors from the transformer encoders. The results of the evaluation are provided using TREC 2019-2021 and MS Marco dev datasets.
Explainable predictions of different machine learning algorithms used to predict Early Stage diabetes
Venue: arXiv cs.LG 2021
Year: 2021

Machine Learning and Artificial Intelligence can be widely used to diagnose chronic diseases so that necessary precautionary treatment can be done in critical time. Diabetes Mellitus which is one of the major diseases can be easily diagnosed by several Machine Learning algorithms. Early stage diagnosis is crucial to prevent dangerous consequences. In this paper we have made a comparative analysis of several machine learning algorithms viz. Random Forest, Decision Tree, Artificial Neural Networks, K Nearest Neighbor, Support Vector Machine, and XGBoost along with feature attribution using SHAP to identify the most important feature in predicting the diabetes on a dataset collected from Sylhet Hospital. As per the experimental results obtained, the Random Forest algorithm has outperformed all the other algorithms with an accuracy of 99 percent on this particular dataset.
A Review of Adversarial Attack and Defense for Classification Methods
Venue: arXiv cs.CR 2021
Year: 2021

Despite the efficiency and scalability of machine learning systems, recent studies have demonstrated that many classification methods, especially deep neural networks (DNNs), are vulnerable to adversarial examples; i.e., examples that are carefully crafted to fool a well-trained classification model while being indistinguishable from natural data to human. This makes it potentially unsafe to apply DNNs or related methods in security-critical areas. Since this issue was first identified by Biggio et al. (2013) and Szegedy et al.(2014), much work has been done in this field, including the development of attack methods to generate adversarial examples and the construction of defense techniques to guard against such examples. This paper aims to introduce this topic and its latest developments to the statistical community, primarily focusing on the generation and guarding of adversarial examples. Computing codes (in python and R) used in the numerical experiments are publicly available for readers to explore the surveyed methods. It is the hope of the authors that this paper will encourage more statisticians to work on this important and exciting field of generating and defending against adversarial examples.
Formalization of Transform Methods in Higher-order Logic: A Survey
Venue: arXiv cs.LO 2021
Year: 2021

Most of the engineering and physical systems are generally characterized by differential and difference equations based on their continuous-time and discrete-time dynamics, respectively. Moreover, these dynamical models are analyzed using transform methods to prove various properties of these systems, such as, transfer function, frequency response and stability, and to find out solutions of the differential/difference equations. The conventional techniques for performing the transform methods based analysis have been unable to provide an accurate analysis of these systems. Therefore, higher-order-logic theorem proving, a formal method, has been used for accurately analyzing systems based on transform methods. In this paper, we survey developments for transform methods based analysis in various higher-order-logic theorem provers and overview the corresponding real world case studies from the avionics, medicine and transportation domains that have been analyzed based on these developments.
An Asynchronous Multi-Beam MAC Protocol for Multi-Hop Wireless Networks
Venue: arXiv cs.NI 2021
Year: 2021

A node equipped with a multi-beam antenna can achieve a throughput of up to m times as compared to a single-beam antenna, by simultaneously communicating on its m non-interfering beams. However, the existing multi-beam medium access control (MAC) schemes can achieve concurrent data communication only when the transmitter nodes are locally synchronized. Asynchronous packet arrival at a multi-beam receiver node would increase the node deafness and MAC layer capture problems, and thereby limit the data throughput. This paper presents an asynchronous multi-beam MAC protocol for multi-hop wireless networks, which makes the following enhancements to the existing multi-beam MAC schemes (i) A windowing mechanism to achieve concurrent communication when the packet arrival is asynchronous, (ii) A smart packet processing mechanism which reduces the node deafness, hidden terminals and MAC-layer capture problems, and (iii) A channel access mechanism which decreases resource wastage and node starvation. Our proposed protocol also works in heterogeneous networks that deploy the nodes equipped with single-beam as well as multi-beam antennas. Simulation results demonstrate a superior performance of our proposed protocol.
Enhanced countering adversarial attacks via input denoising and feature restoring
Venue: arXiv cs.CV 2021
Year: 2021

Despite the fact that deep neural networks (DNNs) have achieved prominent performance in various applications, it is well known that DNNs are vulnerable to adversarial examples/samples (AEs) with imperceptible perturbations in clean/original samples. To overcome the weakness of the existing defense methods against adversarial attacks, which damages the information on the original samples, leading to the decrease of the target classifier accuracy, this paper presents an enhanced countering adversarial attack method IDFR (via Input Denoising and Feature Restoring). The proposed IDFR is made up of an enhanced input denoiser (ID) and a hidden lossy feature restorer (FR) based on the convex hull optimization. Extensive experiments conducted on benchmark datasets show that the proposed IDFR outperforms the various state-of-the-art defense methods, and is highly effective for protecting target models against various adversarial black-box or white-box attacks. \footnote{Souce code is released at: \href{https://github.com/ID-FR/IDFR}{https://github.com/ID-FR/IDFR}}
An Improved Analysis of Greedy for Online Steiner Forest
Venue: arXiv cs.DS 2021
Year: 2021

This paper considers the classic Online Steiner Forest problem where one is given a (weighted) graph $G$ and an arbitrary set of $k$ terminal pairs $\{\{s_1,t_1\},\ldots ,\{s_k,t_k\}\}$ that are required to be connected. The goal is to maintain a minimum-weight sub-graph that satisfies all the connectivity requirements as the pairs are revealed one by one. It has been known for a long time that no algorithm (even randomized) can be better than $Ω(\log(k))$-competitive for this problem. Interestingly, a simple greedy algorithm is already very efficient for this problem. This algorithm can be informally described as follows: Upon arrival of a new pair $\{s_i,t_i\}$, connect $s_i$ and $t_i$ with the shortest path in the current metric, contract the metric along the chosen path and wait for the next pair. Although simple and intuitive, greedy proved itself challenging to analyze and its competitive ratio is a long-standing open problem in the area of online algorithms. The last progress on this question is due to an elegant analysis by Awerbuch, Azar, and Bartal [SODA~1996], who showed that greedy is $O(\log^2(k))$-competitive. Our main result is to show that greedy is in fact $O(\log(k)\log\log(k))$-competitive on a wide class of instances. In particular, this wide class of instances contains all the instances that were exhibited in the literature until now.
A Voting-Based Blockchain Interoperability Oracle
Venue: arXiv cs.CR 2021
Year: 2021

Today's blockchain landscape is severely fragmented as more and more heterogeneous blockchain platforms have been developed in recent years. These blockchain platforms are not able to interact with each other or with the outside world since only little emphasis is placed on the interoperability between them. Already proposed solutions for blockchain interoperability such as naive relay or oracle solutions are usually not broadly applicable since they are either too expensive to operate or very resource-intensive. For that reason, we propose a blockchain interoperability oracle that follows a voting-based approach based on threshold signatures. The oracle nodes generate a distributed private key to execute an off-chain aggregation mechanism to collectively respond to requests. Compared to state-of-the-art relay schemes, our approach does not incur any ongoing costs and since the on-chain component only needs to verify a single signature, we can achieve remarkable cost savings compared to conventional oracle solutions.
Non-NP-Hardness of Translationally-Invariant Spin-Model Problems
Venue: arXiv cs.CC 2021
Year: 2021

Finding the ground state energy of the Heisenberg Hamiltonian is an important problem in the field of condensed matter physics. In some configurations, such as the antiferromagnetic translationally-invariant case on the 2D square lattice, its exact ground state energy is still unknown. We show that finding the ground state energy of the Heisenberg model cannot be an NP-Hard problem unless P=NP. We prove this result using a reduction to a sparse set and certain theorems from computational complexity theory. The result hints at the potential tractability of the problem and encourages further research towards a positive complexity result. In addition, we prove similar results for many similarly structured Hamiltonian problems, including certain forms of the Ising, t-J, and Fermi-Hubbard models.