OpenRaiser/Intern-Atlas huggingface dataset:
Incorporating Weisfeiler-Leman into algorithms for group isomorphism
Venue: arXiv cs.CC 2019
Year: 2019

In this paper we combine many of the standard and more recent algebraic techniques for testing isomorphism of finite groups (GpI) with combinatorial techniques that have typically been applied to Graph Isomorphism. In particular, we show how to combine several state-of-the-art GpI algorithms for specific group classes into an algorithm for general GpI, namely: composition series isomorphism (Rosenbaum-Wagner, Theoret. Comp. Sci., 2015; Luks, 2015), recursively-refineable filters (Wilson, J. Group Theory, 2013), and low-genus GpI (Brooksbank-Maglione-Wilson, J. Algebra, 2017). Recursively-refineable filters -- a generalization of subgroup series -- form the skeleton of this framework, and we refine our filter by building a hypergraph encoding low-genus quotients, to which we then apply a hypergraph variant of the k-dimensional Weisfeiler-Leman technique. Our technique is flexible enough to readily incorporate additional hypergraph invariants or additional characteristic subgroups.
Descriptive evaluation of students using fuzzy approximate reasoning
Venue: arXiv cs.AI 2019
Year: 2019

In recent years, descriptive evaluation has been introduced as a new model for educational evaluation of Iranian students. The current descriptive evaluation method is based on four-valued logic. Assessing all students with only four values is led to a lack of relative justice and the creation of unrealistic equality. Also, the complexity of the evaluation process in the current method increases teacher errors likelihood. As a suitable solution, in this paper, a fuzzy descriptive evaluation system has been proposed. The proposed method is based on fuzzy logic, which is an infinite-valued logic and it can perform approximate reasoning on natural language propositions. By the proposed fuzzy system, student assessment is performed over the school year with infinite values instead of four values. But to eliminate the diversity of assigned values to students, at the end of the school year, the calculated values for each student will be rounded to the nearest value of the four standard values of the current descriptive evaluation system. It can be implemented easily in an appropriate smartphone app, which makes it much easier for the teachers to evaluate the evaluation process. In this paper, the evaluation process of the elementary third-grade mathematics course in Iran during the period from the beginning of the MEHR (The Seventh month of Iran) to the end of BAHMAN (The Eleventh Month of Iran) is examined by the proposed system. To evaluate the validity of this system, the proposed method has been simulated in MATLAB software.
A Comprehensive Analysis on Adversarial Robustness of Spiking Neural Networks
Venue: arXiv cs.NE 2019
Year: 2019

In this era of machine learning models, their functionality is being threatened by adversarial attacks. In the face of this struggle for making artificial neural networks robust, finding a model, resilient to these attacks, is very important. In this work, we present, for the first time, a comprehensive analysis of the behavior of more bio-plausible networks, namely Spiking Neural Network (SNN) under state-of-the-art adversarial tests. We perform a comparative study of the accuracy degradation between conventional VGG-9 Artificial Neural Network (ANN) and equivalent spiking network with CIFAR-10 dataset in both whitebox and blackbox setting for different types of single-step and multi-step FGSM (Fast Gradient Sign Method) attacks. We demonstrate that SNNs tend to show more resiliency compared to ANN under black-box attack scenario. Additionally, we find that SNN robustness is largely dependent on the corresponding training mechanism. We observe that SNNs trained by spike-based backpropagation are more adversarially robust than the ones obtained by ANN-to-SNN conversion rules in several whitebox and blackbox scenarios. Finally, we also propose a simple, yet, effective framework for crafting adversarial attacks from SNNs. Our results suggest that attacks crafted from SNNs following our proposed method are much stronger than those crafted from ANNs.
Learning Unsupervised Multi-View Stereopsis via Robust Photometric Consistency
Venue: arXiv cs.CV 2019
Year: 2019

We present a learning based approach for multi-view stereopsis (MVS). While current deep MVS methods achieve impressive results, they crucially rely on ground-truth 3D training data, and acquisition of such precise 3D geometry for supervision is a major hurdle. Our framework instead leverages photometric consistency between multiple views as supervisory signal for learning depth prediction in a wide baseline MVS setup. However, naively applying photo consistency constraints is undesirable due to occlusion and lighting changes across views. To overcome this, we propose a robust loss formulation that: a) enforces first order consistency and b) for each point, selectively enforces consistency with some views, thus implicitly handling occlusions. We demonstrate our ability to learn MVS without 3D supervision using a real dataset, and show that each component of our proposed robust loss results in a significant improvement. We qualitatively observe that our reconstructions are often more complete than the acquired ground truth, further showing the merits of this approach. Lastly, our learned model generalizes to novel settings, and our approach allows adaptation of existing CNNs to datasets without ground-truth 3D by unsupervised finetuning. Project webpage: https://tejaskhot.github.io/unsup_mvs
Displaying Things in Common to Encourage Friendship Formation: A Large Randomized Field Experiment
Venue: arXiv cs.SI 2019
Year: 2019

Friendship formation is important to online social network sites and to society, but can suffer from informational friction. In this study, we demonstrate that social networks may effectively use an IT-facilitated intervention -- displaying things in common (TIC) between users (mutual hometown, interest, education, work, city) -- to encourage friendship formation. Displaying TIC updates an individual's belief about the shared similarity with another and reduces information friction that may be hard to overcome in offline communication. In collaboration with an online social network, we conduct a randomized field experiment that randomly varies the prominence of different things in common when a user is browsing a non-friend's profile. The dyad-level exogenous variation, orthogonal to any (un)observed structural factors in viewer-profile's network, allows us to cleanly isolate the role of preferences for TIC in driving network formation and homophily. We find that displaying TICs to viewers can significantly increase their probability of sending a friend requests and forming friendships, and is especially effective for pairs of people who have little in common. We also find that displaying TIC can improve friendship formation for a wide range of viewers with different demographics and is more effective when the TICs are more surprising to the viewer.
P3DFFT: a framework for parallel computations of Fourier transforms in three dimensions
Venue: arXiv cs.DC 2019
Year: 2019

Fourier and related transforms is a family of algorithms widely employed in diverse areas of computational science, notoriously difficult to scale on high-performance parallel computers with large number of processing elements (cores). This paper introduces a popular software package called P3DFFT implementing Fast Fourier Transforms (FFT) in three dimensions (3D) in a highly efficient and scalable way. It overcomes a well-known scalability bottleneck of 3D FFT implementations by using two-dimensional domain decomposition. Designed for portable performance, P3DFFT achieves excellent timings for a number of systems and problem sizes. On Cray XT5 system P3DFFT attains 45% efficiency in weak scaling from 128 to 65,536 computational cores. Library features include Fourier and Chebyshev transforms, Fortran and C interfaces, in- and out-of-place transforms, uneven data grids, single and double precision. P3DFFT is available as open source at http://code.google.com/p/p3dfft/. This paper discusses P3DFFT implementation and performance in a way that helps guide the user in making optimal choices for parameters of their runs.
LightTrack: A Generic Framework for Online Top-Down Human Pose Tracking
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we propose a novel effective light-weight framework, called LightTrack, for online human pose tracking. The proposed framework is designed to be generic for top-down pose tracking and is faster than existing online and offline methods. Single-person Pose Tracking (SPT) and Visual Object Tracking (VOT) are incorporated into one unified functioning entity, easily implemented by a replaceable single-person pose estimation module. Our framework unifies single-person pose tracking with multi-person identity association and sheds first light upon bridging keypoint tracking with object tracking. We also propose a Siamese Graph Convolution Network (SGCN) for human pose matching as a Re-ID module in our pose tracking system. In contrary to other Re-ID modules, we use a graphical representation of human joints for matching. The skeleton-based representation effectively captures human pose similarity and is computationally inexpensive. It is robust to sudden camera shift that introduces human drifting. To the best of our knowledge, this is the first paper to propose an online human pose tracking framework in a top-down fashion. The proposed framework is general enough to fit other pose estimators and candidate matching mechanisms. Our method outperforms other online methods while maintaining a much higher frame rate, and is very competitive with our offline state-of-the-art. We make the code publicly available at: https://github.com/Guanghan/lighttrack.
On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences
Venue: arXiv cs.GT 2019
Year: 2019

We study the three-dimensional stable matching problem with cyclic preferences. This model involves three types of agents, with an equal number of agents of each type. The types form a cyclic order such that each agent has a complete preference list over the agents of the next type. We consider the open problem of the existence of three-dimensional matchings in which no triple of agents prefer each other to their partners. Such matchings are said to be weakly stable. We show that contrary to published conjectures, weakly stable three-dimensional matchings need not exist. Furthermore, we show that it is NP-complete to determine whether a weakly stable three-dimensional matchings exists. We achieve this by reducing from the variant of the problem where preference lists are allowed to be incomplete. Our results can be generalized to the $k$-dimensional stable matching problem with cyclic preferences for $k \geq 3$.
Feature Selection and Feature Extraction in Pattern Analysis: A Literature Review
Venue: arXiv cs.LG 2019
Year: 2019

Pattern analysis often requires a pre-processing stage for extracting or selecting features in order to help the classification, prediction, or clustering stage discriminate or represent the data in a better way. The reason for this requirement is that the raw data are complex and difficult to process without extracting or selecting appropriate features beforehand. This paper reviews theory and motivation of different common methods of feature selection and extraction and introduces some of their applications. Some numerical implementations are also shown for these methods. Finally, the methods in feature selection and extraction are compared.
Adaptive neural network based dynamic surface control for uncertain dual arm robots
Venue: arXiv cs.RO 2019
Year: 2019

The paper discusses an adaptive strategy to effectively control nonlinear manipulation motions of a dual arm robot (DAR) under system uncertainties including parameter variations, actuator nonlinearities and external disturbances. It is proposed that the control scheme is first derived from the dynamic surface control (DSC) method, which allows the robot's end-effectors to robustly track the desired trajectories. Moreover, since exactly determining the DAR system's dynamics is impractical due to the system uncertainties, the uncertain system parameters are then proposed to be adaptively estimated by the use of the radial basis function network (RBFN). The adaptation mechanism is derived from the Lyapunov theory, which theoretically guarantees stability of the closed-loop control system. The effectiveness of the proposed RBFN-DSC approach is demonstrated by implementing the algorithm in a synthetic environment with realistic parameters, where the obtained results are highly promising.
A new direction to promote the implementation of artificial intelligence in natural clinical settings
Venue: arXiv cs.AI 2019
Year: 2019

Artificial intelligence (AI) researchers claim that they have made great `achievements' in clinical realms. However, clinicians point out the so-called `achievements' have no ability to implement into natural clinical settings. The root cause for this huge gap is that many essential features of natural clinical tasks are overlooked by AI system developers without medical background. In this paper, we propose that the clinical benchmark suite is a novel and promising direction to capture the essential features of the real-world clinical tasks, hence qualifies itself for guiding the development of AI systems, promoting the implementation of AI in real-world clinical practice.
Configuration-Space Flipper Planning for Rescue Robots
Venue: arXiv cs.RO 2019
Year: 2019

For rescue robots, flipper endows the robot with additional ability to pass through various terrain. Autonomous motion becomes more important. In recent work autonomy is done by either planning with several special states or based on collected data. We are considering if it is possible to find a way to build continues states without collecting old trail data. In this paper, we first model the possible states as a global planning path with parameter configuration of the scene. Then, we follows the path to achieve the autonomous run. We plot the morphology of each path points to show the correctness of the path and implement a simple path following on real robot to demonstrate the performance of our algorithm.
Brief Announcement: Does Preprocessing Help under Congestion?
Venue: arXiv cs.DC 2019
Year: 2019

This paper investigates the power of preprocessing in the CONGEST model. Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to study the application of distributed algorithms in Software-Defined Networks (SDNs). In this paper, we show that a large class of lower bounds in the CONGEST model still hold in the SUPPORTED model, highlighting the robustness of these bounds. This also raises the question how much does preprocessing help in the CONGEST model.
An Entropy Power Inequality for Discrete Random Variables
Venue: arXiv cs.IT 2019
Year: 2019

Let $\mathsf{N}_{\rm d}\left[X\right]=\frac{1}{2π{\rm e}}{\rm e}^{2\mathsf{H}\left[X\right]}$ denote the entropy power of the discrete random variable $X$ where $\mathsf{H}\left[X\right]$ denotes the discrete entropy of $X$. In this paper, we show that for two independent discrete random variables $X$ and $Y$, the entropy power inequality $\mathsf{N}_{\rm d}\left[X\right]+\mathsf{N}_{\rm d}\left[Y\right]\leq 2 \mathsf{N}_{\rm d}\left[X+Y\right]$ holds and it can be tight. The basic idea behind the proof is to perturb the discrete random variables using suitably designed continuous random variables. Then, the continuous entropy power inequality is applied to the sum of the perturbed random variables and the resulting lower bound is optimized.
Proof-of-Prestige: A Useful Work Reward System for Unverifiable Tasks
Venue: arXiv cs.CR 2019
Year: 2019

As cryptographic tokens and altcoins are increasingly being built to serve as utility tokens, the notion of useful work consensus protocols, as opposed to number-crunching PoW consensus, is becoming ever more important. In such contexts, users get rewards from the network after they have carried out some specific task useful for the network. While in some cases the proof of some utility or service can be proved, the majority of tasks are impossible to verify. In order to deal with such cases, we design Proof-of-Prestige (PoP) - a reward system that can run on top of Proof-of-Stake blockchains. PoP introduces prestige which is a volatile resource and, in contrast to coins, regenerates over time. Prestige can be gained by performing useful work, spent when benefiting from services and directly translates to users minting power. PoP is resistant against Sybil and Collude attacks and can be used to reward workers for completing unverifiable tasks, while keeping the system free for the end-users. We use two exemplar use-cases to showcase the usefulness of PoP and we build a simulator to assess the cryptoeconomic behaviour of the system in terms of prestige transfer between nodes.
Algorithms for Grey-Weighted Distance Computations
Venue: arXiv cs.CV 2019
Year: 2019

With the increasing size of datasets and demand for real time response for interactive applications, improving runtime for algorithms with excessive computational requirements has become increasingly important. Many different algorithms combining efficient priority queues with various helper structures have been proposed for computing grey-weighted distance transforms. Here we compare the performance of popular competitive algorithms in different scenarios to form practical guidelines easy to adopt. The label-setting category of algorithms is shown to be the best choice for all scenarios. The hierarchical heap with a pointer array to keep track of nodes on the heap is shown to be the best choice as priority queue. However, if memory is a critical issue, then the best choice is the Dial priority queue for integer valued costs and the Untidy priority queue for real valued costs.
Numerical Modelling of Crack Initiation, Propagation and Branching under Dynamic Loading
Venue: arXiv cs.CE 2019
Year: 2019

In this paper crack initiation, propagation and branching phenomena are simulated using the Pseudo-Spring Smooth Particle Hydrodynamics (SPH) in two and three-dimensional domains. The pseudo-spring analogy is used to model material damage. Here, the interaction of particles is limited to its initial immediate neighbours. The particles are connected via springs. These springs do not provide any extra stiffness in the system but only define the level of interaction between the connecting pairs. It is assumed that a crack has passed through a spring connecting a particle pair if the damage indicator of that spring becomes more than a predefined value. The crack branching of a pre-notched plate under dynamic loading and the effect of loading amplitude are studied here. The computed crack speeds, crack paths and surfaces are compared with experimental and numerical results available in the literature and are found to be in good agreement. The effect of notch location for a plate with a circular hole is studied here. The ability of the framework to model arbitrary crack paths and surfaces are demonstrated via three-dimensional simulations of chalk under torsion, Kalthoff-Winkler experiment and Taylor bullet impact.
Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model
Venue: arXiv cs.DS 2019
Year: 2019

In a recent work (ECCC, TR18-171, 2018), we introduced models of testing graph properties in which, in addition to answers to the usual graph-queries, the tester obtains {\em random vertices drawn according to an arbitrary distribution $D$}. Such a tester is required to distinguish between graphs that have the property and graphs that are far from having the property, {\em where the distance between graphs is defined based on the unknown vertex distribution $D$}. These ("vertex-distribution free" (VDF)) models generalize the standard models in which $D$ is postulated to be uniform on the vertex-set, and they were studies both in the dense graph model and in the bounded-degree graph model. The focus of the aforementioned work was on testers, called {\sf strong}, whose query complexity depends only on the proximity parameter $ε$. Unfortunately, in the standard bounded-degree graph model, some natural properties such as Bipartiteness do not have strong testers, and others (like cycle-freeness) do not have strong testers of one-sided error (whereas one-sided error was shown inherent to the VDF model). Hence, it was suggested to study general (i.e., non-strong) testers of "sub-linear" complexity. In this work, we pursue the foregoing suggestion, but do so in a model that augments the model presented in the aforementioned work. Specifically, we provide the tester with an evaluation oracle to the unknown distribution $D$, in addition to samples of $D$ and oracle access to the tested graph. Our main results are testers for Bipartitness and cycle-freeness, in this augmented model, having complexity that is almost-linear in the square root of the "effective support size" of $D$.
Load Balancing with preemptive and non-preemptive task scheduling in Cloud Computing
Venue: arXiv cs.NI 2019
Year: 2019

In Cloud computing environment the resources are managed dynamically based on the need and demand for resources for a particular task. With a lot of challenges to be addressed our concern is Load balancing where load balancing is done for optimal usage of resources and reduces the cost associated with it as we use pay-as-you-go policy. The task scheduling is done by the cloud service provider using preemption and non-preemption based on the requirements in a virtualized scenario which has been focused here. In this paper, various task scheduling algorithms are studied to present the dynamic allocation of resources under each category and the ways each of this scheduling algorithm adapts to handle the load and have high-performance computing
Managing a Queue to a Soft Delay Target
Venue: arXiv cs.NI 2019
Year: 2019

This memo proposes to transplant the core idea of Curvy RED, the softened delay target, into AQMs that are better designed to deal with dynamics, such as PIE or PI2, but that suffer from the weakness of a fixed delay target.
From Sicilian mafia to Chinese "scam villages"
Venue: arXiv cs.CR 2019
Year: 2019

Inspired by Gambetta's theory on the origins of the mafia in Sicily, we report a geo-concentrating phenomenon of scams in China, and propose a novel economic explanation. Our analysis has some policy implications.