OpenRaiser/Intern-Atlas huggingface dataset:
Wireless Expanders
Venue: arXiv cs.DS 2018
Year: 2018

This paper introduces an extended notion of expansion suitable for radio networks. A graph $G=(V,E)$ is called an $(α_w, β_w)$-{wireless expander} if for every subset $S \subseteq V$ s.t. $|S|\leq α_w \cdot |V|$, there exists a subset $S'\subseteq S$ s.t. there are at least $β_w \cdot |S|$ vertices in $V\backslash S$ adjacent in $G$ to exactly one vertex in $S'$. The main question we ask is the following: to what extent are ordinary expanders also good {wireless} expanders? We answer this question in a nearly tight manner. On the positive side, we show that any $(α, β)$-expander with maximum degree $Δ$ and $β\geq 1/Δ$ is also a $(α_w, β_w)$ wireless expander for $β_w = Ω(β/ \log (2 \cdot \min\{Δ/ β, Δ\cdot β\}))$. Thus the wireless expansion is smaller than the ordinary expansion by at most a factor logarithmic in $\min\{Δ/ β, Δ\cdot β\}$, which depends on the graph \emph{average degree} rather than maximum degree; e.g., for low arboricity graphs, the wireless expansion matches the ordinary expansion up to a constant. We complement this positive result by presenting an explicit construction of a "bad" $(α, β)$-expander for which the wireless expansion is $β_w = O(β/ \log (2 \cdot \min\{Δ/ β, Δ\cdot β\})$. We also analyze the theoretical properties of wireless expanders and their connection to unique neighbor expanders, and demonstrate their applicability: Our results yield improved bounds for the {spokesmen election problem} that was introduced in the seminal paper of Chlamtac and Weinstein (1991) to devise efficient broadcasting for multihop radio networks. Our negative result yields a significantly simpler proof than that from the seminal paper of Kushilevitz and Mansour (1998) for a lower bound on the broadcast time in radio networks.
Distributed Symmetry-Breaking Algorithms for Congested Cliques
Venue: arXiv cs.DC 2018
Year: 2018

The {Congested Clique} is a distributed-computing model for single-hop networks with restricted bandwidth that has been very intensively studied recently. It models a network by an $n$-vertex graph in which any pair of vertices can communicate one with another by transmitting $O(\log n )$ bits in each round. Various problems have been studied in this setting, but for some of them the best-known results are those for general networks. In this paper we devise significantly improved algorithms for various symmetry-breaking problems, such as forests-decompositions, vertex-colorings, and maximal independent set. We analyze the running time of our algorithms as a function of the arboricity $a$ of a clique subgraph that is given as input. Our algorithms are especially efficient in Trees, planar graphs, graphs with constant genus, and many other graphs that have bounded arboricity, but unbounded size. We obtain $O(a)$-forest-decomposition algorithm with $O(\log a)$ time that improves the previously-known $O(\log n)$ time, $O(a^{2 + ε})$-coloring in $O(\log^* n)$ time that improves upon an $O(\log n)$-time algorithm, $O(a)$-coloring in $O(a^ε)$-time that improves upon several previous algorithms, and a maximal independent set algorithm with $O(\sqrt a)$ time that improves at least quadratically upon the state-of-the-art for small and moderate values of $a$. Those results are achieved using several techniques. First, we produce a forest decomposition with a helpful structure called {$H$-partition} within $O(\log a)$ rounds. In general graphs this structure requires $Θ(\log n)$ time, but in Congested Cliques we are able to compute it faster. We employ this structure in conjunction with partitioning techniques that allow us to solve various symmetry-breaking problems efficiently.
Steering Social Activity: A Stochastic Optimal Control Point Of View
Venue: arXiv cs.SI 2018
Year: 2018

User engagement in online social networking depends critically on the level of social activity in the corresponding platform--the number of online actions, such as posts, shares or replies, taken by their users. Can we design data-driven algorithms to increase social activity? At a user level, such algorithms may increase activity by helping users decide when to take an action to be more likely to be noticed by their peers. At a network level, they may increase activity by incentivizing a few influential users to take more actions, which in turn will trigger additional actions by other users. In this paper, we model social activity using the framework of marked temporal point processes, derive an alternate representation of these processes using stochastic differential equations (SDEs) with jumps and, exploiting this alternate representation, develop two efficient online algorithms with provable guarantees to steer social activity both at a user and at a network level. In doing so, we establish a previously unexplored connection between optimal control of jump SDEs and doubly stochastic marked temporal point processes, which is of independent interest. Finally, we experiment both with synthetic and real data gathered from Twitter and show that our algorithms consistently steer social activity more effectively than the state of the art.
Achievability Bounds for T-Fold Irregular Repetition Slotted ALOHA Scheme in the Gaussian MAC
Venue: arXiv cs.IT 2018
Year: 2018

We address the problem of uncoordinated massive random-access in the Gaussian multiple access channel (MAC). The performance of low-complexity T-fold irregular repetition slotted ALOHA (IRSA) scheme is investigated and achievability bounds are derived. The main difference of this scheme in comparison to IRSA is as follows: any collisions of order up to T can be resolved with some probability of error introduced by noise. In order to optimize the parameters of the scheme we combine the density evolution method (DE) proposed by G. Liva and a finite length random coding bound for the Gaussian MAC proposed by Y. Polyanskiy. As energy efficiency is of critical importance for massive machine-type communication (mMTC), then our main goal is to minimize the energy-per-bit required to achieve the target packet loss ratio (PLR). We consider two scenarios: (a) the number of active users is fixed; (b) the number of active users is a Poisson random variable.
Fault Detection Effectiveness of Source Test Case Generation Strategies for Metamorphic Testing
Venue: arXiv cs.SE 2018
Year: 2018

Metamorphic testing is a well known approach to tackle the oracle problem in software testing. This technique requires the use of source test cases that serve as seeds for the generation of follow-up test cases. Systematic design of test cases is crucial for the test quality. Thus, source test case generation strategy can make a big impact on the fault detection effectiveness of metamorphic testing. Most of the previous studies on metamorphic testing have used either random test data or existing test cases as source test cases. There has been limited research done on systematic source test case generation for metamorphic testing. This paper provides a comprehensive evaluation on the impact of source test case generation techniques on the fault finding effectiveness of metamorphic testing. We evaluated the effectiveness of line coverage, branch coverage, weak mutation and random test generation strategies for source test case generation. The experiments are conducted with 77 methods from 4 open source code repositories. Our results show that by systematically creating source test cases, we can significantly increase the fault finding effectiveness of metamorphic testing. Further, in this paper we introduce a simple metamorphic testing tool called "METtester" that we use to conduct metamorphic testing on these methods.
On the scaling of polynomial features for representation matching
Venue: arXiv cs.CL 2018
Year: 2018

In many neural models, new features as polynomial functions of existing ones are used to augment representations. Using the natural language inference task as an example, we investigate the use of scaled polynomials of degree 2 and above as matching features. We find that scaling degree 2 features has the highest impact on performance, reducing classification error by 5% in the best models.
Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time
Venue: arXiv cs.DS 2018
Year: 2018

In the weighted flow-time problem on a single machine, we are given a set of n jobs, where each job has a processing requirement p_j, release date r_j and weight w_j. The goal is to find a preemptive schedule which minimizes the sum of weighted flow-time of jobs, where the flow-time of a job is the difference between its completion time and its released date. We give the first pseudo-polynomial time constant approximation algorithm for this problem. The running time of our algorithm is polynomial in n, the number of jobs, and P, which is the ratio of the largest to the smallest processing requirement of a job. Our algorithm relies on a novel reduction of this problem to a generalization of the multi-cut problem on trees, which we call the Demand Multi-Cut problem. Even though we do not give a constant factor approximation algorithm for the Demand Multi-Cut problem on trees, we show that the specific instances of Demand Multi-Cut obtained by reduction from weighted flow-time problem instances have more structure in them, and we are able to employ techniques based on dynamic programming. Our dynamic programming algorithm relies on showing that there are near optimal solutions which have nice smoothness properties, and we exploit these properties to reduce the size of DP table.
Communication Using Eigenvalues of Higher Multiplicity of the Nonlinear Fourier Transform
Venue: arXiv cs.IT 2018
Year: 2018

A generalized Nonlinear Fourier Transform (GNFT), which includes eigenvalues of higher multiplicity, is considered for information transmission over fiber optic channels. Numerical algorithms are developed to compute the direct and inverse GNFTs. For closely-spaced eigenvalues, examples suggest that the GNFT is more robust than the NFT to the practical impairments of truncation, discretization, attenuation and noise. Communication using a soliton with one double eigenvalue is numerically demonstrated, and its information rates are compared to solitons with one and two simple eigenvalues.
Multiclass Weighted Loss for Instance Segmentation of Cluttered Cells
Venue: arXiv cs.CV 2018
Year: 2018

We propose a new multiclass weighted loss function for instance segmentation of cluttered cells. We are primarily motivated by the need of developmental biologists to quantify and model the behavior of blood T-cells which might help us in understanding their regulation mechanisms and ultimately help researchers in their quest for developing an effective immuno-therapy cancer treatment. Segmenting individual touching cells in cluttered regions is challenging as the feature distribution on shared borders and cell foreground are similar thus difficulting discriminating pixels into proper classes. We present two novel weight maps applied to the weighted cross entropy loss function which take into account both class imbalance and cell geometry. Binary ground truth training data is augmented so the learning model can handle not only foreground and background but also a third touching class. This framework allows training using U-Net. Experiments with our formulations have shown superior results when compared to other similar schemes, outperforming binary class models with significant improvement of boundary adequacy and instance detection. We validate our results on manually annotated microscope images of T-cells.
Car-to-Cloud Communication Traffic Analysis Based on the Common Vehicle Information Model
Venue: arXiv cs.NI 2018
Year: 2018

Although connectivity services have been introduced already today in many of the most recent car models, the potential of vehicles serving as highly mobile sensor platform in the Internet of Things (IoT) has not been sufficiently exploited yet. The European AutoMat project has therefore defined an open Common Vehicle Information Model (CVIM) in combination with a cross-industry, cloud-based big data marketplace. Thereby, vehicle sensor data can be leveraged for the design of entirely new services even beyond traffic-related applications (such as localized weather forecasts). This paper focuses on the prediction of the achievable data rate making use of an analytical model based on empirical measurements. For an in-depth analysis, the CVIM has been integrated in a vehicle traffic simulator to produce CVIM-complaint data streams as a result of the individual behavior of each vehicle (speed, brake activity, steering activity, etc.). In a next step, a simulation of vehicle traffic in a realistically modeled, large-area street network has been used in combination with a cellular Long Term Evolution (LTE) network to determine the cumulated amount of data produced within each network cell. As a result, a new car-to-cloud communication traffic model has been derived, which quantifies the data rate of aggregated car-to-cloud data producible by vehicles depending on the current traffic situations (free flow and traffic jam). The results provide a reference for network planning and resource scheduling for car-to-cloud type services in the context of smart cities.
Sensor-topology based simplicial complex reconstruction
Venue: arXiv cs.GR 2018
Year: 2018

We propose a new method for the reconstruction of simplicial complexes (combining points, edges and triangles) from 3D point clouds from Mobile Laser Scanning (MLS). Our main goal is to produce a reconstruction of a scene that is adapted to the local geometry of objects. Our method uses the inherent topology of the MLS sensor to define a spatial adjacency relationship between points. We then investigate each possible connexion between adjacent points and filter them by searching collinear structures in the scene, or structures perpendicular to the laser beams. Next, we create triangles for each triplet of self-connected edges. Last, we improve this method with a regularization based on the co-planarity of triangles and collinearity of remaining edges. We compare our results to a naive simplicial complexes reconstruction based on edge length.
Toward Open Data Blockchain Analytics: A Bitcoin Perspective
Venue: arXiv cs.CR 2018
Year: 2018

Bitcoin is the first implementation of what has become known as a 'public permissionless' blockchain. Guaranteeing security and protocol conformity through its elegant combination of cryptographic assurances and game theoretic economic incentives, it permits censorship resistant public read-write access to its append-only blockchain database without the need for any mediating central authority. Not until its advent has such a trusted, transparent, comprehensive and granular data set of digital economic behaviours been available for public network analysis. In this article, by translating the cumbersome binary data structure of the Bitcoin blockchain into a high fidelity graph model, we demonstrate through various analyses the often overlooked social and econometric benefits of employing such a novel open data architecture. Specifically we show (a) how repeated patterns of transaction behaviours can be revealed to link user activity across the blockchain; (b) how newly mined bitcoin can be associated to demonstrate individual accumulations of wealth; (c) through application of the naive quantity theory of money that Bitcoin's disinflationary properties can be revealed and measured; and (d) how the user community can develop coordinated defences against repeated denial of service attacks on the network. All of the aforementioned being exemplary benefits that would be lost with the closed data models of the 'private permissioned' distributed ledger architectures that are dominating enterprise level development due to existing blockchain issues of governance, scalability and confidentiality.
A Novel Image Encryption Scheme Based on Different Block Sizes for Grayscale and Color Images
Venue: arXiv cs.CR 2018
Year: 2018

In this paper, two image encryption schemes are proposed for grayscale and color images. The two encryption schemes are based on dividing each image into blocks of different sizes. In the first scheme, the two dimension ($2$D) input image is divided into various blocks of size $N \times N$. Each block is transformed into a one dimensional ($1$D) array by using the Zigzag pattern. Then, the exclusive or (XOR) logical operation is used to encrypt each block with the analogous secret key. In the second scheme, after the transformation process, the first block of each image is encrypted by the corresponding secret key. Then, before the next block is encrypted, it is XORed with the first encrypted block to become the next input to the encrypting routine and so on. This feedback mechanism depends on the cipher block chaining (CBC) mode of operation which considers the heart of some ciphers because it is highly nonlinear. In the case of color images, the color component is separated into blocks with the same size and different secret keys. The used secret key sequences are generated from elliptic curves (EC) over a \textit{binary} finite field $\mathbb{F}_{2^{m}}$. Finally, the experimental results are carried out and security analysis of the ciphered images are demonstrated that the two proposed schemes had a better performance in terms of security, sensitivity and robustness.
Batch Normalization and the impact of batch structure on the behavior of deep convolution networks
Venue: arXiv cs.CV 2018
Year: 2018

Batch normalization was introduced in 2015 to speed up training of deep convolution networks by normalizing the activations across the current batch to have zero mean and unity variance. The results presented here show an interesting aspect of batch normalization, where controlling the shape of the training batches can influence what the network will learn. If training batches are structured as balanced batches (one image per class), and inference is also carried out on balanced test batches, using the batch's own means and variances, then the conditional results will improve considerably. The network uses the strong information about easy images in a balanced batch, and propagates it through the shared means and variances to help decide the identity of harder images on the same batch. Balancing the test batches requires the labels of the test images, which are not available in practice, however further investigation can be done using batch structures that are less strict and might not require the test image labels. The conditional results show the error rate almost reduced to zero for nontrivial datasets with small number of classes such as the CIFAR10.
Randomized sliding window algorithms for regular languages
Venue: arXiv cs.FL 2018
Year: 2018

A sliding window algorithm receives a stream of symbols and has to output at each time instant a certain value which only depends on the last $n$ symbols. If the algorithm is randomized, then at each time instant it produces an incorrect output with probability at most $ε$, which is a constant error bound. This work proposes a more relaxed definition of correctness which is parameterized by the error bound $ε$ and the failure ratio $ϕ$: A randomized sliding window algorithm is required to err with probability at most $ε$ at a portion of $1-ϕ$ of all time instants of an input stream. This work continues the investigation of sliding window algorithms for regular languages. In previous works a trichotomy theorem was shown for deterministic algorithms: the optimal space complexity is either constant, logarithmic or linear in the window size. The main results of this paper concerns three natural settings (randomized algorithms with failure ratio zero and randomized/deterministic algorithms with bounded failure ratio) and provide natural language theoretic characterizations of the space complexity classes.
Fast flow-based algorithm for creating density-equalizing map projections
Venue: arXiv cs.CG 2018
Year: 2018

Cartograms are maps that rescale geographic regions (e.g., countries, districts) such that their areas are proportional to quantitative demographic data (e.g., population size, gross domestic product). Unlike conventional bar or pie charts, cartograms can represent correctly which regions share common borders, resulting in insightful visualizations that can be the basis for further spatial statistical analysis. Computer programs can assist data scientists in preparing cartograms, but developing an algorithm that can quickly transform every coordinate on the map (including points that are not exactly on a border) while generating recognizable images has remained a challenge. Methods that translate the cartographic deformations into physics-inspired equations of motion have become popular, but solving these equations with sufficient accuracy can still take several minutes on current hardware. Here we introduce a flow-based algorithm whose equations of motion are numerically easier to solve compared with previous methods. The equations allow straightforward parallelization so that the calculation takes only a few seconds even for complex and detailed input. Despite the speedup, the proposed algorithm still keeps the advantages of previous techniques: with comparable quantitative measures of shape distortion, it accurately scales all areas, correctly fits the regions together and generates a map projection for every point. We demonstrate the use of our algorithm with applications to the 2016 US election results, the gross domestic products of Indian states and Chinese provinces, and the spatial distribution of deaths in the London borough of Kensington and Chelsea between 2011 and 2014.
Spanning Tree Congestion and Computation of Generalized Győri-Lovász Partition
Venue: arXiv cs.DS 2018
Year: 2018

We study a natural problem in graph sparsification, the Spanning Tree Congestion (\STC) problem. Informally, the \STC problem seeks a spanning tree with no tree-edge \emph{routing} too many of the original edges. The root of this problem dates back to at least 30 years ago, motivated by applications in network design, parallel computing and circuit design. Variants of the problem have also seen algorithmic applications as a preprocessing step of several important graph algorithms. For any general connected graph with $n$ vertices and $m$ edges, we show that its STC is at most $\mathcal{O}(\sqrt{mn})$, which is asymptotically optimal since we also demonstrate graphs with STC at least $Ω(\sqrt{mn})$. We present a polynomial-time algorithm which computes a spanning tree with congestion $\mathcal{O}(\sqrt{mn}\cdot \log n)$. We also present another algorithm for computing a spanning tree with congestion $\mathcal{O}(\sqrt{mn})$; this algorithm runs in sub-exponential time when $m = ω(n \log^2 n)$. For achieving the above results, an important intermediate theorem is \emph{generalized Győri-Lovász theorem}, for which Chen et al. gave a non-constructive proof. We give the first elementary and constructive proof by providing a local search algorithm with running time $\mathcal{O}^*\left( 4^n \right)$, which is a key ingredient of the above-mentioned sub-exponential time algorithm. We discuss a few consequences of the theorem concerning graph partitioning, which might be of independent interest. We also show that for any graph which satisfies certain \emph{expanding properties}, its STC is at most $\mathcal{O}(n)$, and a corresponding spanning tree can be computed in polynomial time. We then use this to show that a random graph has STC $Θ(n)$ with high probability.