OpenRaiser/Intern-Atlas huggingface dataset:
Fair cost allocation for ridesharing services - modeling, mathematical programming and an algorithm to find the nucleolus
Venue: arXiv cs.GT 2019
Year: 2019

This paper addresses one of the most challenging issues in designing an efficient and sustainable ridesharing service: ridesharing market design. We formulate it as a fair cost allocation problem through the lens of the cooperative game theory. A special property of the cooperative ridesharing game is that its characteristic function values are calculated by solving an optimization problem. Several concepts of fairness are investigated and special attention is paid to a solution concept named nucleolus, which aims to minimize the maximum dissatisfaction in the system. Due to its computational intractability, we break the problem into a master-subproblem structure and two subproblems are developed to generate constraints for the master problem. We propose a coalition generation procedure to find the nucleolus and approximate nucleolus of the game. Experimental results showed that when the game has a non-empty core, in the approximate nucleolus scheme the coalitions are computed only when it is necessary and the approximate procedure produces the actual nucleolus. And when the game has an empty core, the approximate nucleolus is close to the actual one. Regardless of the emptiness of the game, our algorithm needs to generate only a small fraction (1.6%) of the total coalition constraints to compute the approximate nucleolus. The proposed model and results nicely fit systems operated by autonomous vehicles.
Mutual Information for the Stochastic Block Model by the Adaptive Interpolation Method
Venue: arXiv cs.IT 2019
Year: 2019

We rigorously derive a single-letter variational expression for the mutual information of the asymmetric two-groups stochastic block model in the dense graph regime. Existing proofs in the literature are indirect, as they involve mapping the model to a rank-one matrix estimation problem whose mutual information is then determined by a combination of methods (e.g., interpolation, cavity, algorithmic, spatial coupling). In this contribution we provide a self-contained direct method using only the recently introduced adaptive interpolation method.
Subspace Methods That Are Resistant to a Limited Number of Features Corrupted by an Adversary
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we consider batch supervised learning where an adversary is allowed to corrupt instances with arbitrarily large noise. The adversary is allowed to corrupt any $l$ features in each instance and the adversary can change their values in any way. This noise is introduced on test instances and the algorithm receives no label feedback for these instances. We provide several subspace voting techniques that can be used to transform existing algorithms and prove data-dependent performance bounds in this setting. The key insight to our results is that we set our parameters so that a significant fraction of the voting hypotheses do not contain corrupt features and, for many real world problems, these uncorrupt hypotheses are sufficient to achieve high accuracy. We empirically validate our approach on several datasets including three new datasets that deal with side channel electromagnetic information.
DeepBall: Deep Neural-Network Ball Detector
Venue: arXiv cs.CV 2019
Year: 2019

The paper describes a deep network based object detector specialized for ball detection in long shot videos. Due to its fully convolutional design, the method operates on images of any size and produces \emph{ball confidence map} encoding the position of detected ball. The network uses hypercolumn concept, where feature maps from different hierarchy levels of the deep convolutional network are combined and jointly fed to the convolutional classification layer. This allows boosting the detection accuracy as larger visual context around the object of interest is taken into account. The method achieves state-of-the-art results when tested on publicly available ISSIA-CNR Soccer Dataset.
Large-scale mammography CAD with Deformable Conv-Nets
Venue: arXiv cs.CV 2019
Year: 2019

State-of-the-art deep learning methods for image processing are evolving into increasingly complex meta-architectures with a growing number of modules. Among them, region-based fully convolutional networks (R-FCN) and deformable convolutional nets (DCN) can improve CAD for mammography: R-FCN optimizes for speed and low consumption of memory, which is crucial for processing the high resolutions of to 50 micrometers used by radiologists. Deformable convolution and pooling can model a wide range of mammographic findings of different morphology and scales, thanks to their versatility. In this study, we present a neural net architecture based on R-FCN / DCN, that we have adapted from the natural image domain to suit mammograms -- particularly their larger image size -- without compromising resolution. We trained the network on a large, recently released dataset (Optimam) including 6,500 cancerous mammograms. By combining our modern architecture with such a rich dataset, we achieved an area under the ROC curve of 0.879 for breast-wise detection in the DREAMS challenge (130,000 withheld images), which surpassed all other submissions in the competitive phase.
Construction of QC-LDPC Codes with Low Error Floor by Efficient Systematic Search and Elimination of Trapping Sets
Venue: arXiv cs.IT 2019
Year: 2019

We propose a systematic design of protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with low error floor. We first characterize the trapping sets of such codes and demonstrate that the QC structure of the code eliminates some of the trapping set structures that can exist in a code with the same degree distribution and girth but lacking the QC structure. Using this characterization, our design aims at eliminating a targeted collection of trapping sets. Considering the parent/child relationship between the trapping sets in the collection, we search for and eliminate those trapping sets that are in the collection but are not a child of any other trapping set in the collection. An efficient layered algorithm is designed for the search of these targeted trapping sets. Compared to the existing codes in the literature, the designed codes are superior in the sense that they are free of the same collection of trapping sets with a smaller block length, or a larger collection of trapping sets with the same block length. In addition, the efficiency of the search algorithm makes it possible to design codes with larger degrees which are free of trapping sets within larger ranges compared to the state-of-the-art.
In oder Aus
Venue: arXiv cs.DS 2019
Year: 2019

Bloom filters are data structures used to determine set membership of elements, with applications from string matching to networking and security problems. These structures are favored because of their reduced memory consumption and fast wallclock and asymptotic time bounds. Generally, Bloom filters maintain constant membership query time, making them very fast in their niche. However, they are limited in their lack of a removal operation, as well as by their probabilistic nature. In this paper, we discuss various iterations of and alternatives to the generic Bloom filter that have been researched and implemented to overcome their inherent limitations. Bloom filters, especially when used in conjunction with other data structures, are still powerful and efficient data structures; we further discuss their use in industy and research to optimize resource utilization.
Concurrent Distributed Serving with Mobile Servers
Venue: arXiv cs.DC 2019
Year: 2019

This paper introduces a new resource allocation problem in distributed computing called distributed serving with mobile servers (DSMS). In DSMS, there are $k$ identical mobile servers residing at the processors of a network. At arbitrary points of time, any subset of processors can invoke one or more requests. To serve a request, one of the servers must move to the processor that invoked the request. Resource allocation is performed in a distributed manner since only the processor that invoked the request initially knows about it. All processors cooperate by passing messages to achieve correct resource allocation. They do this with the goal to minimize the communication cost. Routing servers in large-scale distributed systems requires a scalable location service. We introduce the distributed protocol GNN that solves the DSMS problem on overlay trees. We prove that GNN is starvation-free and correctly integrates locating the servers and synchronizing the concurrent access to servers despite asynchrony, even when the requests are invoked over time. Further, we analyze GNN for "one-shot" executions, i.e., all requests are invoked simultaneously. We prove that when running GNN on top of a special family of tree topologies---known as hierarchically well-separated trees (HSTs)---we obtain a randomized distributed protocol with an expected competitive ratio of $O(\log n)$ on general network topologies with $n$ processors. From a technical point of view, our main result is that GNN optimally solves the DSMS problem on HSTs for one-shot executions, even if communication is asynchronous. Further, we present a lower bound of $Ω(\max\{k, \log n/\log\log n\})$ on the competitive ratio for DSMS. The lower bound even holds when communication is synchronous and requests are invoked sequentially.
Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
Venue: arXiv cs.CC 2019
Year: 2019

In the past decade, sparse principal component analysis has emerged as an archetypal problem for illustrating statistical-computational tradeoffs. This trend has largely been driven by a line of research aiming to characterize the average-case complexity of sparse PCA through reductions from the planted clique (PC) conjecture - which conjectures that there is no polynomial-time algorithm to detect a planted clique of size $K = o(N^{1/2})$ in $\mathcal{G}(N, \frac{1}{2})$. All previous reductions to sparse PCA either fail to show tight computational lower bounds matching existing algorithms or show lower bounds for formulations of sparse PCA other than its canonical generative model, the spiked covariance model. Also, these lower bounds all quickly degrade with the exponent in the PC conjecture. Specifically, when only given the PC conjecture up to $K = o(N^α)$ where $α< 1/2$, there is no sparsity level $k$ at which these lower bounds remain tight. If $α\le 1/3$ these reductions fail to even show the existence of a statistical-computational tradeoff at any sparsity $k$. We give a reduction from PC that yields the first full characterization of the computational barrier in the spiked covariance model, providing tight lower bounds at all sparsities $k$. We also show the surprising result that weaker forms of the PC conjecture up to clique size $K = o(N^α)$ for any given $α\in (0, 1/2]$ imply tight computational lower bounds for sparse PCA at sparsities $k = o(n^{α/3})$. This shows that even a mild improvement in the signal strength needed by the best known polynomial-time sparse PCA algorithms would imply that the hardness threshold for PC is subpolynomial. This is the first instance of a suboptimal hardness assumption implying optimal lower bounds for another problem in unsupervised learning.
Optimal Decentralized Dynamic Policies for Video Streaming over Wireless Channels
Venue: arXiv cs.NI 2019
Year: 2019

The problem addressed is that of optimally controlling, in a decentralized fashion, the download of mobile video, which is expected to comprise 75 % of total mobile data traffic by 2020. The server can dynamically choose which packets to download to clients, from among several packets which encode their videos at different resolutions, as well as the power levels of their transmissions. This allows it to control packet delivery probabilities, and thereby, for example, avert imminent video outages at clients. It must however respect the access point's constraints on bandwidth and average transmission power. The goal is to maximize video "Quality of Experience" (QoE), which depends on several factors such as (i) outage duration when the video playback buffer is empty, (ii) number of outage periods, (iii) how many frames downloaded are of lower resolution, (iv) temporal variations in resolution, etc. It is shown that there exists an optimal decentralized solution where the AP announces the price of energy, and each client distributedly and dynamically maximizes its own QoE subject to the cost of energy. A distributed iterative algorithm to solve for optimal decentralized policy is also presented. Further, for the client-level QoE optimization, the optimal choice of video-resolution and power-level of packet transmissions has a simple monotonicity and threshold structure vis-a-vis video playback buffer level. When the number of orthogonal channels is less than the number of clients, there is an index policy for prioritizing packet transmissions. When the AP has to simply choose which clients' packets to transmit, the index policy is asymptotically optimal as the number of channels is scaled up with clients.
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions
Venue: arXiv cs.DM 2019
Year: 2019

The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(\frac{n}{\log n})$ players can bias the outcome of any Boolean function $\{0,1\}^n \to \{0,1\}$ with respect to the uniform measure. We extend their result to arbitrary product measures on $\{0,1\}^n$, by combining their argument with a completely different argument that handles very biased coordinates. We view this result as a step towards proving a conjecture of Friedgut, which states that Boolean functions on the continuous cube $[0,1]^n$ (or, equivalently, on $\{1,\dots,n\}^n$) can be biased using coalitions of $o(n)$ players. This is the first step taken in this direction since Friedgut proposed the conjecture in 2004. Russell, Saks and Zuckerman extended the result of Kahn, Kalai and Linial to multi-round protocols, showing that when the number of rounds is $o(\log^* n)$, a coalition of $o(n)$ players can bias the outcome with respect to the uniform measure. We extend this result as well to arbitrary product measures on $\{0,1\}^n$. The argument of Russell et al. relies on the fact that a coalition of $o(n)$ players can boost the expectation of any Boolean function from $ε$ to $1-ε$ with respect to the uniform measure. This fails for general product distributions, as the example of the AND function with respect to $μ_{1-1/n}$ shows. Instead, we use a novel boosting argument alongside a generalization of our first result to arbitrary finite ranges.
Seed Selection and Social Coupon Allocation for Redemption Maximization in Online Social Networks
Venue: arXiv cs.SI 2019
Year: 2019

Online social networks have become the medium for efficient viral marketing exploiting social influence in information diffusion. However, the emerging application Social Coupon (SC) incorporating social referral into coupons cannot be efficiently solved by previous researches which do not take into account the effect of SC allocation. The number of allocated SCs restricts the number of influenced friends for each user. In the paper, we investigate not only the seed selection problem but also the effect of SC allocation for optimizing the redemption rate which represents the efficiency of SC allocation. Accordingly, we formulate a problem named Seed Selection and SC allocation for Redemption Maximization (S3CRM) and prove the hardness of S3CRM. We design an effective algorithm with a performance guarantee, called Seed Selection and Social Coupon allocation algorithm. For S3CRM, we introduce the notion of marginal redemption to evaluate the efficiency of investment in seeds and SCs. Moreover, for a balanced investment, we develop a new graph structure called guaranteed path, to explore the opportunity to optimize the redemption rate. Finally, we perform a comprehensive evaluation on our proposed algorithm with various baselines. The results validate our ideas and show the effectiveness of the proposed algorithm over baselines.
Dynamic Matrix Decomposition for Action Recognition
Venue: arXiv cs.CV 2019
Year: 2019

Designing a technique for the automatic analysis of different actions in videos in order to detect the presence of interested activities is of high significance nowadays. In this paper, we explore a robust and dynamic appearance technique for the purpose of identifying different action activities. We also exploit a low-rank and structured sparse matrix decomposition (LSMD) method to better model these activities.. Our method is effective in encoding localized spatio-temporal features which enables the analysis of local motion taking place in the video. Our proposed model use adjacent frame differences as the input to the method thereby forcing it to capture the changes occurring in the video. The performance of our model is tested on a benchmark dataset in terms of detection accuracy. Results achieved with our model showed the promising capability of our model in detecting action activities.
'Zhores' -- Petaflops supercomputer for data-driven modeling, machine learning and artificial intelligence installed in Skolkovo Institute of Science and Technology
Venue: arXiv cs.DC 2019
Year: 2019

The Petaflops supercomputer "Zhores" recently launched in the "Center for Computational and Data-Intensive Science and Engineering" (CDISE) of Skolkovo Institute of Science and Technology (Skoltech) opens up new exciting opportunities for scientific discoveries in the institute especially in the areas of data-driven modeling, machine learning and artificial intelligence. This supercomputer utilizes the latest generation of Intel and NVidia processors to provide resources for the most compute intensive tasks of the Skoltech scientists working in digital pharma, predictive analytics, photonics, material science, image processing, plasma physics and many more. Currently it places 6th in the Russian and CIS TOP-50 (2018) supercomputer list. In this article we summarize the cluster properties and discuss the measured performance and usage modes of this scientific instrument in Skoltech.
Misbinding Attacks on Secure Device Pairing and Bootstrapping
Venue: arXiv cs.CR 2019
Year: 2019

In identity misbinding attacks against authenticated key-exchange protocols, a legitimate but compromised participant manipulates the honest parties so that the victim becomes unknowingly associated with a third party. These attacks are well known, and resistance to misbinding is considered a critical requirement for security protocols on the Internet. In the context of device pairing, on the other hand, the attack has received little attention outside the trusted-computing community. This paper points out that most device pairing protocols are vulnerable to misbinding. Device pairing protocols are characterized by lack of a-priory information, such as identifiers and cryptographic roots of trust, about the other endpoint. Therefore, the devices in pairing protocols need to be identified by the user's physical access to them. As case studies for demonstrating the misbinding vulnerability, we use Bluetooth and a protocol that registers new IoT devices to authentication servers on wireless networks. We have implemented the attacks. We also show how the attacks can be found in formal models of the protocols with carefully formulated correspondence assertions. The formal analysis yields a new type of double misbinding attack. While pairing protocols have been extensively modelled and analyzed, misbinding seems to be an aspect that has not previously received sufficient attention. Finally, we discuss potential ways to mitigate the threat and its significance to security of pairing protocols.
Active Probabilistic Inference on Matrices for Pre-Conditioning in Stochastic Optimization
Venue: arXiv cs.LG 2019
Year: 2019

Pre-conditioning is a well-known concept that can significantly improve the convergence of optimization algorithms. For noise-free problems, where good pre-conditioners are not known a priori, iterative linear algebra methods offer one way to efficiently construct them. For the stochastic optimization problems that dominate contemporary machine learning, however, this approach is not readily available. We propose an iterative algorithm inspired by classic iterative linear solvers that uses a probabilistic model to actively infer a pre-conditioner in situations where Hessian-projections can only be constructed with strong Gaussian noise. The algorithm is empirically demonstrated to efficiently construct effective pre-conditioners for stochastic gradient descent and its variants. Experiments on problems of comparably low dimensionality show improved convergence. In very high-dimensional problems, such as those encountered in deep learning, the pre-conditioner effectively becomes an automatic learning-rate adaptation scheme, which we also empirically show to work well.
Fast, Small, and Simple Document Listing on Repetitive Text Collections
Venue: arXiv cs.DS 2019
Year: 2019

Document listing on string collections is the task of finding all documents where a pattern appears. It is regarded as the most fundamental document retrieval problem, and is useful in various applications. Many of the fastest-growing string collections are composed of very similar documents, such as versioned code and document collections, genome repositories, etc. Plain pattern-matching indexes designed for repetitive text collections achieve orders-of-magnitude reductions in space. Instead, there are not many analogous indexes for document retrieval. In this paper we present a simple document listing index for repetitive string collections of total length $n$ that lists the $ndoc$ distinct documents where a pattern of length $m$ appears in time $\mathcal{O}(m+ndoc \cdot \log n)$. We exploit the repetitiveness of the document array (i.e., the suffix array coarsened to document identifiers) to grammar-compress it while precomputing the answers to nonterminals, and store them in grammar-compressed form as well. Our experimental results show that our index sharply outperforms existing alternatives in the space/time tradeoff map.