OpenRaiser/Intern-Atlas huggingface dataset:
Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded 1-Planar Graphs
Venue: arXiv cs.DS 2020
Year: 2020

We propose two fixed-parameter tractable algorithms for the weighted Max-Cut problem on embedded 1-planar graphs parameterized by the crossing number $k$ of the given embedding. A graph is called 1-planar if it can be drawn in the plane with at most one crossing per edge. Our algorithms recursively reduce a 1-planar graph to at most $3^k$ planar graphs, using edge removal and node contraction. Our main algorithm then solves the Max-Cut problem for the planar graphs using the FCE-MaxCut introduced by Liers and Pardella [23]. In the case of non-negative edge weights, we suggest a variant that allows to solve the planar instances with any planar Max-Cut algorithm. We show that a maximum cut in the given 1-planar graph can be derived from the solutions for the planar graphs. Our algorithms compute a maximum cut in an embedded weighted 1-planar graph with $n$ nodes and $k$ edge crossings in time $O(3^k \cdot n^{3/2} \log n)$.
Transfer learning for vision-based tactile sensing
Venue: arXiv cs.RO 2020
Year: 2020

Due to the complexity of modeling the elastic properties of materials, the use of machine learning algorithms is continuously increasing for tactile sensing applications. Recent advances in deep neural networks applied to computer vision make vision-based tactile sensors very appealing for their high-resolution and low cost. A soft optical tactile sensor that is scalable to large surfaces with arbitrary shape is discussed in this paper. A supervised learning algorithm trains a model that is able to reconstruct the normal force distribution on the sensor's surface, purely from the images recorded by an internal camera. In order to reduce the training times and the need for large datasets, a calibration procedure is proposed to transfer the acquired knowledge across multiple sensors while maintaining satisfactory performance.
Equivalence of pushdown automata via first-order grammars
Venue: arXiv cs.LO 2020
Year: 2020

A decidability proof for bisimulation equivalence of first-order grammars is given. It is an alternative proof for a result by Sénizergues (1998, 2005) that subsumes his affirmative solution of the famous decidability question for deterministic pushdown automata. The presented proof is conceptually simpler, and a particular novelty is that it is not given as two semidecision procedures but it provides an explicit algorithm that might be amenable to a complexity analysis.
Deep Learning on Graphs: A Survey
Venue: arXiv cs.LG 2020
Year: 2020

Deep learning has been shown to be successful in a number of domains, ranging from acoustics, images, to natural language processing. However, applying deep learning to the ubiquitous graph data is non-trivial because of the unique characteristics of graphs. Recently, substantial research efforts have been devoted to applying deep learning methods to graphs, resulting in beneficial advances in graph analysis techniques. In this survey, we comprehensively review the different types of deep learning methods on graphs. We divide the existing methods into five categories based on their model architectures and training strategies: graph recurrent neural networks, graph convolutional networks, graph autoencoders, graph reinforcement learning, and graph adversarial methods. We then provide a comprehensive overview of these methods in a systematic manner mainly by following their development history. We also analyze the differences and compositions of different methods. Finally, we briefly outline the applications in which they have been used and discuss potential future research directions.
Learning Controllable Fair Representations
Venue: arXiv cs.LG 2020
Year: 2020

Learning data representations that are transferable and are fair with respect to certain protected attributes is crucial to reducing unfair decisions while preserving the utility of the data. We propose an information-theoretically motivated objective for learning maximally expressive representations subject to fairness constraints. We demonstrate that a range of existing approaches optimize approximations to the Lagrangian dual of our objective. In contrast to these existing approaches, our objective allows the user to control the fairness of the representations by specifying limits on unfairness. Exploiting duality, we introduce a method that optimizes the model parameters as well as the expressiveness-fairness trade-off. Empirical evidence suggests that our proposed method can balance the trade-off between multiple notions of fairness and achieves higher expressiveness at a lower computational cost.
LIGA: A Cryptosystem Based on the Hardness of Rank-Metric List and Interleaved Decoding
Venue: arXiv cs.CR 2020
Year: 2020

We propose the new rank-metric code-based cryptosystem LIGA which is based on the hardness of list decoding and interleaved decoding of Gabidulin codes. LIGA is an improved variant of the Faure-Loidreau (FL) system, which was broken in a structural attack by Gaborit, Otmani, and Talé Kalachi (GOT, 2018). We keep the FL encryption and decryption algorithms, but modify the insecure key generation algorithm. Our crucial observation is that the GOT attack is equivalent to decoding an interleaved Gabidulin code. The new key generation algorithm constructs public keys for which all polynomial-time interleaved decoders fail---hence LIGA resists the GOT attack. We also prove that the public-key encryption version of LIGA is IND-CPA secure in the standard model and the KEM version is IND-CCA2 secure in the random oracle model, both under hardness assumptions of formally defined problems related to list decoding and interleaved decoding of Gabidulin codes. We propose and analyze various exponential-time attacks on these problems, calculate their work factors, and compare the resulting parameters to NIST proposals. The strengths of LIGA are short ciphertext sizes and (relatively) small key sizes. Further, LIGA guarantees correct decryption and has no decryption failure rate. It is not based on hiding the structure of a code. Since there are efficient and constant-time algorithms for encoding and decoding Gabidulin codes, timing attacks on the encryption and decryption algorithms can be easily prevented.
The Glauber dynamics for edge-colourings of trees
Venue: arXiv cs.DS 2020
Year: 2020

Let $T$ be a tree on $n$ vertices and with maximum degree $Δ$. We show that for $k\geq Δ+1$ the Glauber dynamics for $k$-edge-colourings of $T$ mixes in polynomial time in $n$. The bound on the number of colours is best possible as the chain is not even ergodic for $k \leq Δ$. Our proof uses a recursive decomposition of the tree into subtrees; we bound the relaxation time of the original tree in terms of the relaxation time of its subtrees using block dynamics and chain comparison techniques. Of independent interest, we also introduce a monotonicity result for Glauber dynamics that simplifies our proof.
Enumeration, structural and dimensional synthesis of robotic hands: theory and implementation
Venue: arXiv cs.RO 2020
Year: 2020

Designing robotic hands for specific tasks could help in the creation of optimized end-effectors for grasping and manipulation. However the systematic design of robotic hands for a simultaneous task of all fingertips presents many challenges. In this work the algorithms and implementation of an overall synthesis process is presented, which could be a first step towards a complete design tool for robotic end-effectors. Type synthesis for a given task and number of fingers, solvability and dimensional synthesis for arbitrary topologies are developed and implemented. The resulting solver is a powerful tool that can aid in the creation of innovative robotic hands with arbitrary number of fingers and palms. Several examples of type synthesis, solvability calculations and dimensional synthesis are presented.
State Leakage and Coordination with Causal State Knowledge at the Encoder
Venue: arXiv cs.IT 2020
Year: 2020

We revisit the problems of state masking and state amplification through the lens of empirical coordination. Specifically, we characterize the rate-equivocation-coordination trade-offs regions of a state-dependent channel in which the encoder has causal and strictly causal state knowledge. We also extend this characterization to the cases of two-sided state information and noisy channel feedback. Our approach is based on the notion of core of the receiver's knowledge, which we introduce to capture what the decoder can infer about all the signals involved in the model. Finally, we exploit the aforementioned results to solve a channel state estimation zero-sum game in which the encoder prevents the decoder to estimate the channel state accurately.
Monotone Precision and Recall Measures for Comparing Executions and Specifications of Dynamic Systems
Venue: arXiv cs.FL 2020
Year: 2020

The behavioural comparison of systems is an important concern of software engineering research. For example, the areas of specification discovery and specification mining are concerned with measuring the consistency between a collection of execution traces and a program specification. This problem is also tackled in process mining with the help of measures that describe the quality of a process specification automatically discovered from execution logs. Though various measures have been proposed, it was recently demonstrated that they neither fulfil essential properties, such as monotonicity, nor can they handle infinite behaviour. In this paper, we address this research problem by introducing a new framework for the definition of behavioural quotients. We proof that corresponding quotients guarantee desired properties that existing measures have failed to support. We demonstrate the application of the quotients for capturing precision and recall measures between a collection of recorded executions and a system specification. We use a prototypical implementation of these measures to contrast their monotonic assessment with measures that have been defined in prior research.
Learning Direct Optimization for Scene Understanding
Venue: arXiv cs.CV 2020
Year: 2020

We develop a Learning Direct Optimization (LiDO) method for the refinement of a latent variable model that describes input image x. Our goal is to explain a single image x with an interpretable 3D computer graphics model having scene graph latent variables z (such as object appearance, camera position). Given a current estimate of z we can render a prediction of the image g(z), which can be compared to the image x. The standard way to proceed is then to measure the error E(x, g(z)) between the two, and use an optimizer to minimize the error. However, it is unknown which error measure E would be most effective for simultaneously addressing issues such as misaligned objects, occlusions, textures, etc. In contrast, the LiDO approach trains a Prediction Network to predict an update directly to correct z, rather than minimizing the error with respect to z. Experiments show that our LiDO method converges rapidly as it does not need to perform a search on the error landscape, produces better solutions than error-based competitors, and is able to handle the mismatch between the data and the fitted scene model. We apply LiDO to a realistic synthetic dataset, and show that the method also transfers to work well with real images.
Sequential Attention GAN for Interactive Image Editing
Venue: arXiv cs.CV 2020
Year: 2020

Most existing text-to-image synthesis tasks are static single-turn generation, based on pre-defined textual descriptions of images. To explore more practical and interactive real-life applications, we introduce a new task - Interactive Image Editing, where users can guide an agent to edit images via multi-turn textual commands on-the-fly. In each session, the agent takes a natural language description from the user as the input and modifies the image generated in the previous turn to a new design, following the user description. The main challenges in this sequential and interactive image generation task are two-fold: 1) contextual consistency between a generated image and the provided textual description; 2) step-by-step region-level modification to maintain visual consistency across the generated image sequence in each session. To address these challenges, we propose a novel Sequential Attention Generative Adversarial Net-work (SeqAttnGAN), which applies a neural state tracker to encode the previous image and the textual description in each turn of the sequence, and uses a GAN framework to generate a modified version of the image that is consistent with the preceding images and coherent with the description. To achieve better region-specific refinement, we also introduce a sequential attention mechanism into the model. To benchmark on the new task, we introduce two new datasets, Zap-Seq and DeepFashion-Seq, which contain multi-turn sessions with image-description sequences in the fashion domain. Experiments on both datasets show that the proposed SeqAttnGANmodel outperforms state-of-the-art approaches on the interactive image editing task across all evaluation metrics including visual quality, image sequence coherence, and text-image consistency.
Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics
Venue: arXiv cs.DS 2020
Year: 2020

We consider the classic Facility Location, $k$-Median, and $k$-Means problems in metric spaces of doubling dimension $d$. We give nearly linear-time approximation schemes for each problem. The complexity of our algorithms is $2^{(\log(1/\eps)/\eps)^{O(d^2)}} n \log^4 n + 2^{O(d)} n \log^9 n$, making a significant improvement over the state-of-the-art algorithms which run in time $n^{(d/\eps)^{O(d)}}$. Moreover, we show how to extend the techniques used to get the first efficient approximation schemes for the problems of prize-collecting $k$-Medians and $k$-Means, and efficient bicriteria approximation schemes for $k$-Medians with outliers, $k$-Means with outliers and $k$-Center.
Splitting Epistemic Logic Programs
Venue: arXiv cs.AI 2020
Year: 2020

Epistemic logic programs constitute an extension of the stable models semantics to deal with new constructs called subjective literals. Informally speaking, a subjective literal allows checking whether some regular literal is true in all stable models or in some stable model. As it can be imagined, the associated semantics has proved to be non-trivial, as the truth of the subjective literal may interfere with the set of stable models it is supposed to query. As a consequence, no clear agreement has been reached and different semantic proposals have been made in the literature. Unfortunately, comparison among these proposals has been limited to a study of their effect on individual examples, rather than identifying general properties to be checked. In this paper, we propose an extension of the well-known splitting property for logic programs to the epistemic case. To this aim, we formally define when an arbitrary semantics satisfies the epistemic splitting property and examine some of the consequences that can be derived from that, including its relation to conformant planning and to epistemic constraints. Interestingly, we prove (through counterexamples) that most of the existing proposals fail to fulfill the epistemic splitting property, except the original semantics proposed by Gelfond in 1991.
Dissociable neural representations of adversarially perturbed images in convolutional neural networks and the human brain
Venue: arXiv cs.CV 2020
Year: 2020

Despite the remarkable similarities between convolutional neural networks (CNN) and the human brain, CNNs still fall behind humans in many visual tasks, indicating that there still exist considerable differences between the two systems. Here, we leverage adversarial noise (AN) and adversarial interference (AI) images to quantify the consistency between neural representations and perceptual outcomes in the two systems. Humans can successfully recognize AI images as corresponding categories but perceive AN images as meaningless noise. In contrast, CNNs can correctly recognize AN images but mistakenly classify AI images into wrong categories with surprisingly high confidence. We use functional magnetic resonance imaging to measure brain activity evoked by regular and adversarial images in the human brain, and compare it to the activity of artificial neurons in a prototypical CNN-AlexNet. In the human brain, we find that the representational similarity between regular and adversarial images largely echoes their perceptual similarity in all early visual areas. In AlexNet, however, the neural representations of adversarial images are inconsistent with network outputs in all intermediate processing layers, providing no neural foundations for perceptual similarity. Furthermore, we show that voxel-encoding models trained on regular images can successfully generalize to the neural responses to AI images but not AN images. These remarkable differences between the human brain and AlexNet in the representation-perception relation suggest that future CNNs should emulate both behavior and the internal neural presentations of the human brain.
QuickSel: Quick Selectivity Learning with Mixture Models
Venue: arXiv cs.DB 2020
Year: 2020

Estimating the selectivity of a query is a key step in almost any cost-based query optimizer. Most of today's databases rely on histograms or samples that are periodically refreshed by re-scanning the data as the underlying data changes. Since frequent scans are costly, these statistics are often stale and lead to poor selectivity estimates. As an alternative to scans, query-driven histograms have been proposed, which refine the histograms based on the actual selectivities of the observed queries. Unfortunately, these approaches are either too costly to use in practice---i.e., require an exponential number of buckets---or quickly lose their advantage as they observe more queries. In this paper, we propose a selectivity learning framework, called QuickSel, which falls into the query-driven paradigm but does not use histograms. Instead, it builds an internal model of the underlying data, which can be refined significantly faster (e.g., only 1.9 milliseconds for 300 queries). This fast refinement allows QuickSel to continuously learn from each query and yield increasingly more accurate selectivity estimates over time. Unlike query-driven histograms, QuickSel relies on a mixture model and a new optimization algorithm for training its model. Our extensive experiments on two real-world datasets confirm that, given the same target accuracy, QuickSel is 34.0x-179.4x faster than state-of-the-art query-driven histograms, including ISOMER and STHoles. Further, given the same space budget, QuickSel is 26.8%-91.8% more accurate than periodically-updated histograms and samples, respectively.
Generative Adversarial User Model for Reinforcement Learning Based Recommendation System
Venue: arXiv cs.LG 2020
Year: 2020

There are great interests as well as many challenges in applying reinforcement learning (RL) to recommendation systems. In this setting, an online user is the environment; neither the reward function nor the environment dynamics are clearly defined, making the application of RL challenging. In this paper, we propose a novel model-based reinforcement learning framework for recommendation systems, where we develop a generative adversarial network to imitate user behavior dynamics and learn her reward function. Using this user model as the simulation environment, we develop a novel Cascading DQN algorithm to obtain a combinatorial recommendation policy which can handle a large number of candidate items efficiently. In our experiments with real data, we show this generative adversarial user model can better explain user behavior than alternatives, and the RL policy based on this model can lead to a better long-term reward for the user and higher click rate for the system.
An efficient cloud scheduler design supporting preemptible instances
Venue: arXiv cs.DC 2020
Year: 2020

Maximizing resource utilization by performing an efficient resource provisioning is a key factor for any cloud provider: commercial actors can maximize their revenues, whereas scientific and non-commercial providers can maximize their infrastructure utilization. Traditionally, batch systems have allowed data centers to fill their resources as much as possible by using backfilling and similar techniques. However, in an IaaS cloud, where virtual machines are supposed to live indefinitely, or at least as long as the user is able to pay for them, these policies are not easily implementable. In this work we present a new scheduling algorithm for IaaS providers that is able to support preemptible instances, that can be stopped by higher priority requests without introducing large modifications in the current cloud schedulers. This scheduler enables the implementation of new cloud usage and payment models that allow more efficient usage of the resources and potential new revenue sources for commercial providers. We also study the correctness and the performace overhead of the proposed scheduler agains existing solutions.
A Tight Runtime Analysis for the $(μ+ λ)$ EA
Venue: arXiv cs.NE 2020
Year: 2020

Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of evolutionary algorithms which use non-trivial populations remains challenging and only few rigorous results exist. Already for the most basic problem, the determination of the asymptotic runtime of the $(μ+λ)$ evolutionary algorithm on the simple OneMax benchmark function, only the special cases $μ=1$ and $λ=1$ have been solved. In this work, we analyze this long-standing problem and show the asymptotically tight result that the runtime $T$, the number of iterations until the optimum is found, satisfies \[E[T] = Θ\bigg(\frac{n\log n}λ+\frac{n}{λ/ μ} + \frac{n\log^+\log^+ λ/ μ}{\log^+ λ/ μ}\bigg),\] where $\log^+ x := \max\{1, \log x\}$ for all $x > 0$. The same methods allow to improve the previous-best $O(\frac{n \log n}λ + n \log λ)$ runtime guarantee for the $(λ+λ)$~EA with fair parent selection to a tight $Θ(\frac{n \log n}λ + n)$ runtime result.
Online Trading as a Secretary Problem
Venue: arXiv cs.GT 2020
Year: 2020

We consider the online problem in which an intermediary trades identical items with a sequence of n buyers and n sellers, each of unit demand. We assume that the values of the traders are selected by an adversary and the sequence is randomly permuted. We give competitive algorithms for two objectives: welfare and gain-from-trade.
Smooth, Time-invariant Regulation of Nonholonomic Systems via Energy Pumping-and-Damping
Venue: arXiv cs.SY 2020
Year: 2020

In this paper we propose an energy pumping-and-damping technique to regulate nonholonomic systems described by kinematic models. The controller design follows the widely popular interconnection and damping assignment passivity-based methodology, with the free matrices partially structured. Two asymptotic regulation objectives are considered: drive to zero the state or drive the systems total energy to a desired constant value. In both cases, the control laws are smooth, time-invariant, state-feedbacks. For the nonholonomic integrator we give an almost global solution for both problems, with the objectives ensured for all system initial conditions starting outside a set that has zero Lebesgue measure and is nowhere dense. For the general case of higher-order nonholonomic systems in chained form, a local stability result is given. Simulation results comparing the performance of the proposed controller with other existing designs are also provided.