OpenRaiser/Intern-Atlas huggingface dataset:
Random walks and forbidden minors II: A $\text{poly}(d\varepsilon^{-1})$-query tester for minor-closed properties of bounded-degree graphs
Venue: arXiv cs.DM 2019
Year: 2019

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $\mathcal{P}$ (such as planarity). We say that $G$ is $\varepsilon$-far from $\mathcal{P}$ if one has to remove $\varepsilon dn$ edges to make it have $\mathcal{P}$. The problem of property testing $\mathcal{P}$ was introduced in the seminal work of Benjamini-Schramm-Shapira (STOC 2008) that gave a tester with query complexity triply exponential in $\varepsilon^{-1}$. Levi-Ron (TALG 2015) have given the best tester to date, with a quasipolynomial (in $\varepsilon^{-1}$) query complexity. It is an open problem to get property testers whose query complexity is $\text{poly}(d\varepsilon^{-1})$, even for planarity. In this paper, we resolve this open question. For any minor-closed property, we give a tester with query complexity $d\cdot \text{poly}(\varepsilon^{-1})$. The previous line of work on (independent of $n$, two-sided) testers is primarily combinatorial. Our work, on the other hand, employs techniques from spectral graph theory. This paper is a continuation of recent work of the authors (FOCS 2018) analyzing random walk algorithms that find forbidden minors.
Efficient and Safe Exploration in Deterministic Markov Decision Processes with Unknown Transition Models
Venue: arXiv cs.RO 2019
Year: 2019

We propose a safe exploration algorithm for deterministic Markov Decision Processes with unknown transition models. Our algorithm guarantees safety by leveraging Lipschitz-continuity to ensure that no unsafe states are visited during exploration. Unlike many other existing techniques, the provided safety guarantee is deterministic. Our algorithm is optimized to reduce the number of actions needed for exploring the safe space. We demonstrate the performance of our algorithm in comparison with baseline methods in simulation on navigation tasks.
DeepCloud. The Application of a Data-driven, Generative Model in Design
Venue: arXiv cs.LG 2019
Year: 2019

Generative systems have a significant potential to synthesize innovative design alternatives. Still, most of the common systems that have been adopted in design require the designer to explicitly define the specifications of the procedures and in some cases the design space. In contrast, a generative system could potentially learn both aspects through processing a database of existing solutions without the supervision of the designer. To explore this possibility, we review recent advancements of generative models in machine learning and current applications of learning techniques in design. Then, we describe the development of a data-driven generative system titled DeepCloud. It combines an autoencoder architecture for point clouds with a web-based interface and analog input devices to provide an intuitive experience for data-driven generation of design alternatives. We delineate the implementation of two prototypes of DeepCloud, their contributions, and potentials for generative design.
An Efficient Blockchain-based Hierarchical Authentication Mechanism for Energy Trading in V2G Environment
Venue: arXiv cs.NI 2019
Year: 2019

Vehicle-to-grid (V2G) networks have emerged as a new technology in modern electric power transmission networks. It allows bi-directional flow of communication and electricity between electric vehicles (EVs) and the Smart Grid (SG), in order to provide more sophisticated energy trading. However, due to the involvement of a huge amount of trading data and the presence of untrusted entities in the visiting networks, the underlying V2G infrastructure suffers from various security and privacy challenges. Although, several solutions have been proposed in the literature to address these problems, issues like lack of mutual authentication and anonymity, incapability to protect against several attack vectors, generation of huge overhead, and dependency on centralized infrastructures make security and privacy issues even more challenging. To address the above mentioned problems, in this paper, we propose a blockchain oriented hierarchical authentication mechanism for rewarding EVs. The overall process is broadly classified into the following phases: 1) System Initialization, 2) Registration, 3) Hierarchical Mutual Authentication, and 4) Consensus; wherein blockchain's distributed ledger has been employed for transaction execution in distributed V2G environments while Elliptic curve cryptography (ECC) has been used for hierarchical authentication. The designed hierarchical authentication mechanism has been employed to preserve the anonymity of EVs and support mutual authentication between EVs, charging stations (CSs) and the central aggregator (CAG). Additionally, it also supports minimal communicational and computational overheads on resource constrained EVs. Further, formal security verification of the proposed scheme on widely accepted Automated Validation of Internet Security Protocols and Applications (AVISPA) tool validates its safeness against different security attacks.
Adversarial Attacks against Deep Saliency Models
Venue: arXiv cs.CV 2019
Year: 2019

Currently, a plethora of saliency models based on deep neural networks have led great breakthroughs in many complex high-level vision tasks (e.g. scene description, object detection). The robustness of these models, however, has not yet been studied. In this paper, we propose a sparse feature-space adversarial attack method against deep saliency models for the first time. The proposed attack only requires a part of the model information, and is able to generate a sparser and more insidious adversarial perturbation, compared to traditional image-space attacks. These adversarial perturbations are so subtle that a human observer cannot notice their presences, but the model outputs will be revolutionized. This phenomenon raises security threats to deep saliency models in practical applications. We also explore some intriguing properties of the feature-space attack, e.g. 1) the hidden layers with bigger receptive fields generate sparser perturbations, 2) the deeper hidden layers achieve higher attack success rates, and 3) different loss functions and different attacked layers will result in diverse perturbations. Experiments indicate that the proposed method is able to successfully attack different model architectures across various image scenes.
Service Equivalence via Multiparty Session Type Isomorphisms
Venue: arXiv cs.PL 2019
Year: 2019

This paper addresses a problem found within the construction of Service Oriented Architecture: the adaptation of service protocols with respect to functional redundancy and heterogeneity of global communication patterns. We utilise the theory of Multiparty Session Types (MPST). Our approach is based upon the notion of a multiparty session type isomorphism, utilising a novel constructive realisation of service adapter code to establishing equivalence. We achieve this by employing trace semantics over a collection of local types and introducing meta abstractions over the syntax of global types. We develop a corresponding equational theory for MPST isomorphisms. The main motivation for this line of work is to define a type isomorphism that affords the assessment of whether two components/services are substitutables, modulo adaptation code given software components formalised as session types.
FreeST: Context-free Session Types in a Functional Language
Venue: arXiv cs.PL 2019
Year: 2019

FreeST is an experimental concurrent programming language. Based on a core linear functional programming language, it features primitives to fork new threads, and for channel creation and communication. A powerful type system of context-free session types governs the interaction on channels. The compiler builds on a novel algorithm for deciding type equivalence of context-free session types. This abstract provides a gentle introduction to the language and discusses the validation process and runtime system.
A rearrangement distance for fully-labelled trees
Venue: arXiv cs.DS 2019
Year: 2019

The problem of comparing trees representing the evolutionary histories of cancerous tumors has turned out to be crucial, since there is a variety of different methods which typically infer multiple possible trees. A departure from the widely studied setting of classical phylogenetics, where trees are leaf-labelled, tumoral trees are fully labelled, i.e., \emph{every} vertex has a label. In this paper we provide a rearrangement distance measure between two fully-labelled trees. This notion originates from two operations: one which modifies the topology of the tree, the other which permutes the labels of the vertices, hence leaving the topology unaffected. While we show that the distance between two trees in terms of each such operation alone can be decided in polynomial time, the more general notion of distance when both operations are allowed is NP-hard to decide. Despite this result, we show that it is fixed-parameter tractable, and we give a 4-approximation algorithm when one of the trees is binary.
5G for the Factory of the Future: Wireless Communication in an Industrial Environment
Venue: arXiv cs.NI 2019
Year: 2019

In this paper, the application of 5G communication technology in an industrial environment is discussed. It acts as an enabler for the separation of sensors/actors and resources, like memory and computational power. 5G offers characteristics essential for the proposed approach like robustness, ultra-low latency, high data rates and massive number of devices. A demonstrator of a production line was used as an test environment for 5G in a real-world industrial application. A wide variety of heterogeneous sensor systems is used by a mobile robot platform. The collected data is transmitted via a 5G network to various Cloud systems. The product is treated as a cyber-physical system with a RFID tag in conjunction with the product memory system. The dynamic production flow approach is discussed centered around the robot which is used for transportation and inspection of products. This inspection is performed during the transportation and influences the production flow directly. This is desirable in the scope of Industry 4.0 to have an efficient production down to batch size 1.
Software Engineering for Intelligent and Autonomous Systems: Report from the GI Dagstuhl Seminar 18343
Venue: arXiv cs.SE 2019
Year: 2019

Software systems are increasingly used in application domains characterised by uncertain environments, evolving requirements and unexpected failures; sudden system malfunctioning raises serious issues of security, safety, loss of comfort or revenue. During operation, these systems will likely need to deal with several unpredictable situations including variations in system performance, sudden changes in system workload and component failures. These situations can cause deviation from the desired system behaviour and require dynamic adaptation of the system behaviour, parameters or architecture. Through using closed-loop control, typically realized with software, intelligent and autonomous software systems can dynamically adapt themselves, without any or with limited human involvement, by identifying abnormal situations, analysing alternative adaptation options, and finally, self-adapting to a suitable new configuration. This report summarises the research carried out during SEfIAS GI Dagstuhl seminar which provided a forum for strengthening interaction and collaboration for early-career researchers and practitioners from the research communities of SEAMS, ICAC/ICCAC, SASO, Self-Aware Computing and AAMAS.
Rating Reliability and Bias in News Articles: Does AI Assistance Help Everyone?
Venue: arXiv cs.CY 2019
Year: 2019

With the spread of false and misleading information in current news, many algorithmic tools have been introduced with the aim of assessing bias and reliability in written content. However, there has been little work exploring how effective these tools are at changing human perceptions of content. To this end, we conduct a study with 654 participants to understand if algorithmic assistance improves the accuracy of reliability and bias perceptions, and whether there is a difference in the effectiveness of the AI assistance for different types of news consumers. We find that AI assistance with feature-based explanations improves the accuracy of news perceptions. However, some consumers are helped more than others. Specifically, we find that participants who read and share news often on social media are worse at recognizing bias and reliability issues in news articles than those who do not, while frequent news readers and those familiar with politics perform much better. We discuss these differences and their implication to offer insights for future research.
Augmented Utilitarianism for AGI Safety
Venue: arXiv cs.AI 2019
Year: 2019

In the light of ongoing progresses of research on artificial intelligent systems exhibiting a steadily increasing problem-solving ability, the identification of practicable solutions to the value alignment problem in AGI Safety is becoming a matter of urgency. In this context, one preeminent challenge that has been addressed by multiple researchers is the adequate formulation of utility functions or equivalents reliably capturing human ethical conceptions. However, the specification of suitable utility functions harbors the risk of "perverse instantiation" for which no final consensus on responsible proactive countermeasures has been achieved so far. Amidst this background, we propose a novel socio-technological ethical framework denoted Augmented Utilitarianism which directly alleviates the perverse instantiation problem. We elaborate on how augmented by AI and more generally science and technology, it might allow a society to craft and update ethical utility functions while jointly undergoing a dynamical ethical enhancement. Further, we elucidate the need to consider embodied simulations in the design of utility functions for AGIs aligned with human values. Finally, we discuss future prospects regarding the usage of the presented scientifically grounded ethical framework and mention possible challenges.
An Architecture to Support the Invocation of Personal Services in Web Interactions
Venue: arXiv cs.CR 2019
Year: 2019

This paper proposes an architecture to enable Web service providers to interact with personal services. Personal services are vanilla HTTP services that are invoked from a browser, upon a request made by a service Provider, to deliver some service on the client side, i.e., on an execution environment defined by the browser's user. Personal services can be used both to handle content manipulation and presentation or to deliver request-response interactions with different goals (e.g. user authentication). Unlike plugins, that are described to service providers on each and every HTTP request, personal services are explicitly searched by service providers using a novel agent, a Broker, that works in close cooperation with each browser. We have implemented this architecture and implemented an HTTP proxy to cope with it. For demonstration purposes we show how we can use personal services for personal authentication with an electronic identification (eID) card
Learning Algorithms via Neural Logic Networks
Venue: arXiv cs.LG 2019
Year: 2019

We propose a novel learning paradigm for Deep Neural Networks (DNN) by using Boolean logic algebra. We first present the basic differentiable operators of a Boolean system such as conjunction, disjunction and exclusive-OR and show how these elementary operators can be combined in a simple and meaningful way to form Neural Logic Networks (NLNs). We examine the effectiveness of the proposed NLN framework in learning Boolean functions and discrete-algorithmic tasks. We demonstrate that, in contrast to the implicit learning in MLP approach, the proposed neural logic networks can learn the logical functions explicitly that can be verified and interpreted by human. In particular, we propose a new framework for learning the inductive logic programming (ILP) problems by exploiting the explicit representational power of NLN. We show the proposed neural ILP solver is capable of feats such as predicate invention and recursion and can outperform the current state of the art neural ILP solvers using a variety of benchmark tasks such as decimal addition and multiplication, and sorting on ordered list.
Analyzing Learned Molecular Representations for Property Prediction
Venue: arXiv cs.LG 2019
Year: 2019

Advancements in neural machinery have led to a wide range of algorithmic solutions for molecular property prediction. Two classes of models in particular have yielded promising results: neural networks applied to computed molecular fingerprints or expert-crafted descriptors, and graph convolutional neural networks that construct a learned molecular representation by operating on the graph structure of the molecule. However, recent literature has yet to clearly determine which of these two methods is superior when generalizing to new chemical space. Furthermore, prior research has rarely examined these new models in industry research settings in comparison to existing employed models. In this paper, we benchmark models extensively on 19 public and 16 proprietary industrial datasets spanning a wide variety of chemical endpoints. In addition, we introduce a graph convolutional model that consistently matches or outperforms models using fixed molecular descriptors as well as previous graph neural architectures on both public and proprietary datasets. Our empirical findings indicate that while approaches based on these representations have yet to reach the level of experimental reproducibility, our proposed model nevertheless offers significant improvements over models currently used in industrial workflows.
MOTIVE: Micropayments for trusted vehicular services
Venue: arXiv cs.DC 2019
Year: 2019

Increasingly, connected cars are becoming a decentralized data platform. With greater autonomy, they have growing needs for computation and perceiving the world around them through sensors. While todays generation of vehicles carry all the necessary sensor data and computation on board, we envision a future where vehicles can cooperate to increase their perception of the world beyond their immediate view, resulting in greater safety, coordination and more comfortable experience for their human occupants. In order for vehicles to obtain data, compute and other services from other vehicles or road side infrastructure, it is important to be able to make micro payments for those services and for the services to run seamlessly despite the challenges posed by mobility and ephemeral interactions with a dynamic set of neighboring devices. We present MOTIVE, a trusted and decentralized framework that allows vehicles to make peer to peer micropayments for data, compute and other services obtained from other vehicles or road side infrastructure within radio range. The framework utilizes distributed ledger technologies including smart contracts to enable autonomous operation and trusted interactions between vehicles and nearby entities.
Lab Hackathons to Overcome Laboratory Equipment Shortages in Africa: Opportunities and Challenges
Venue: arXiv cs.CY 2019
Year: 2019

Equipment shortages in Africa undermine Science, Technology, Engineering and Mathematics (STEM) Education. We have pioneered the LabHackathon (LabHack): a novel initiative that adapts the conventional hackathon and draws on insights from the Open Hardware movement and Responsible Research and Innovation (RRI). LabHacks are fun, educational events that challenge student participants to build frugal and reproducible pieces of laboratory equipment. Completed designs are then made available to others. LabHacks can therefore facilitate the open and sustainable design of laboratory equipment, in situ, in Africa. In this case study we describe the LabHackathon model, discuss its application in a pilot event held in Zimbabwe and outline the opportunities and challenges it presents.
Method of Counteraction in Social Engineering on Information Activity Objectives
Venue: arXiv cs.CR 2019
Year: 2019

The article presents a study using attacks such as a fake access point and a phishing page. The previous publications on social engineering have been reviewed, statistics of break-ups are analyzed and directions and mechanism of realization of attacks having elements of social engineering are analyzed. The data from the research in three different places were collected and analyzed and the content statistics were provided. For comparison, three categories of higher education institutions were chosen: technical, humanitarian and mixed profiles. Since the research was conducted in educational institutions during the week, most students in the experiment and graduate students took part in the experiment. For each educational institution, a registration form template was created that mimicked the design of the main pages. Examples of hardware and software implementation of a typical stand for attack, data collection and analysis are given. In order to construct a test stand, widely available components were chosen to show how easy it is to carry out attacks of this kind without significant initial costs and special skills. The article provides statistics on the number of connections, permission to use the address of the e-mail and password, as well as permission to automatically transfer service data to the browser (cookies). The statistics are processed using specially written algorithms. The proposed approaches to solving the problem of socio-technical attacks can be used and implemented for operation on any objects of information activity. As a result of the experiments, it is clear that the awareness of users of even technical specialties is not enough, so one needs to pay particular attention to the development of methods for raising awareness of users and reducing the number of potential attacks on objects of information activity.
Pharos: improving navigation instructions on smartwatches by including global landmarks
Venue: arXiv cs.HC 2019
Year: 2019

Landmark-based navigation systems have proven benefits relative to traditional turn-by-turn systems that use street names and distances. However, one obstacle to the implementation of landmark-based navigation systems is the complex challenge of selecting salient local landmarks at each decision point for each user. In this paper, we present Pharos, a novel system that extends turn-by-turn navigation instructions using a single global landmark (e.g. the Eiffel Tower, the Burj Khalifa, municipal TV towers) rather than multiple, hard-to-select local landmarks. We first show that our approach is feasible in a large number of cities around the world through the use of computer vision to select global landmarks. We then present the results of a study demonstrating that by including global landmarks in navigation instructions, users navigate more confidently and build a more accurate mental map of the navigated area than using turn-by-turn instructions.