OpenRaiser/Intern-Atlas huggingface dataset:
Private Multi-party Matrix Multiplication and Trust Computations
Venue: arXiv cs.CR 2016
Year: 2016

This paper deals with distributed matrix multiplication. Each player owns only one row of both matrices and wishes to learn about one distinct row of the product matrix, without revealing its input to the other players. We first improve on a weighted average protocol, in order to securely compute a dot-product with a quadratic volume of communications and linear number of rounds. We also propose a protocol with five communication rounds, using a Paillier-like underlying homomorphic public key cryptosystem, which is secure in the semi-honest model or secure with high probability in the malicious adversary model. Using ProVerif, a cryptographic protocol verification tool, we are able to check the security of the protocol and provide a countermeasure for each attack found by the tool. We also give a randomization method to avoid collusion attacks. As an application, we show that this protocol enables a distributed and secure evaluation of trust relationships in a network, for a large class of trust evaluation schemes.
On The Use of Conjugate Teager-Kaiser Energy Operators with Matched Filters
Venue: arXiv cs.IT 2016
Year: 2016

This work presents the proof of concept of using energy operator theory based on the conjugate Teager-Kaiser energy operators in matched filters for signal detection in multipath fading channels. To do so, we consider signals in the space $\mathcal{S}(\mathbb{R})$ a subspace of the Schwartz space $\mathbf{S}^-(\mathbb{R})$ in order to approximate the received signal. These functions obey to some specific properties as shown in this work. It allows to decompose the received signals into subchannels with their own Signal-to-Noise-Ratio.
Unsupervised Feature Learning Based on Deep Models for Environmental Audio Tagging
Venue: arXiv cs.SD 2016
Year: 2016

Environmental audio tagging aims to predict only the presence or absence of certain acoustic events in the interested acoustic scene. In this paper we make contributions to audio tagging in two parts, respectively, acoustic modeling and feature learning. We propose to use a shrinking deep neural network (DNN) framework incorporating unsupervised feature learning to handle the multi-label classification task. For the acoustic modeling, a large set of contextual frames of the chunk are fed into the DNN to perform a multi-label classification for the expected tags, considering that only chunk (or utterance) level rather than frame-level labels are available. Dropout and background noise aware training are also adopted to improve the generalization capability of the DNNs. For the unsupervised feature learning, we propose to use a symmetric or asymmetric deep de-noising auto-encoder (sDAE or aDAE) to generate new data-driven features from the Mel-Filter Banks (MFBs) features. The new features, which are smoothed against background noise and more compact with contextual information, can further improve the performance of the DNN baseline. Compared with the standard Gaussian Mixture Model (GMM) baseline of the DCASE 2016 audio tagging challenge, our proposed method obtains a significant equal error rate (EER) reduction from 0.21 to 0.13 on the development set. The proposed aDAE system can get a relative 6.7% EER reduction compared with the strong DNN baseline on the development set. Finally, the results also show that our approach obtains the state-of-the-art performance with 0.15 EER on the evaluation set of the DCASE 2016 audio tagging task while EER of the first prize of this challenge is 0.17.
On Solutions for the Maximum Revenue Multi-item Auction under Dominant-Strategy and Bayesian Implementations
Venue: arXiv cs.GT 2016
Year: 2016

Very few exact solutions are known for the monopolist's $k$-item $n$-buyer maximum revenue problem with additive valuation in which $k, n >1$ and the buyers $i$ have independent private distributions $F^j_i$ on items $j$. In this paper we derive exact formulas for the maximum revenue when $k=2$ and $F^j_i$ are any IID distributions on support of size 2, for both the dominant-strategy (DIC) and the Bayesian (BIC) implementations. The formulas lead to the simple characterization that, the two implementations have identical maximum revenue if and only if selling-separately is optimal for the distribution. Our results also give the first demonstration, in this setting, of revenue gaps between the two implementations. For instance, if $k=n=2$ and $Pr\{X_F=1\}=Pr\{X_F=2\}=\frac{1}{2}$, then the maximum revenue in the Bayesian implementation exceeds that in the dominant-strategy by exactly $2\%$; the same gap exists for the continuous uniform distribution $X_F$ over $[a, a+1]\cup[2a, 2a+1]$ for all large $a$.
Distributed Games and Strategies
Venue: arXiv cs.LO 2016
Year: 2016

A summary of work on distributed games and strategies done within the first three years of the ERC project ECSYM is presented.
On the Chen Conjecture regarding the complexity of QCSPs
Venue: arXiv cs.LO 2016
Year: 2016

Let A be an idempotent algebra on a finite domain. We combine results of Chen 2008 and Zhuk 2015 to argue that if Inv(A) satisfies the polynomially generated powers property (PGP), then QCSP(Inv(A)) is in NP. We then use the result of Zhuk to prove a converse, that if Inv(A) satisfies the exponentially generated powers property (EGP), then QCSP(Inv(A)) is co-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive a full dichotomy for the QCSP, justifying the moral correctness of what we term the Chen Conjecture.
Truthfulness with Value-Maximizing Bidders
Venue: arXiv cs.GT 2016
Year: 2016

In markets such as digital advertising auctions, bidders want to maximize value rather than payoff. This is different to the utility functions typically assumed in auction theory and leads to different strategies and outcomes. We refer to bidders who maximize value as value bidders. While simple single-object auction formats are truthful, standard multi-object auction formats allow for manipulation. It is straightforward to show that there cannot be a truthful and revenue-maximizing deterministic auction mechanism with value bidders and general valuations. Approximation has been used as a means to achieve truthfulness, and we study which approximation ratios we can get from truthful approximation mechanisms. We show that the approximation ratio that can be achieved with a deterministic and truthful approximation mechanism with $n$ bidders and $m$ items cannot be higher than 1/n for general valuations. For randomized approximation mechanisms there is a framework with a ratio of O(sqrt(m)). We provide better ratios for environments with restricted valuations.
Large Scale SfM with the Distributed Camera Model
Venue: arXiv cs.CV 2016
Year: 2016

We introduce the distributed camera model, a novel model for Structure-from-Motion (SfM). This model describes image observations in terms of light rays with ray origins and directions rather than pixels. As such, the proposed model is capable of describing a single camera or multiple cameras simultaneously as the collection of all light rays observed. We show how the distributed camera model is a generalization of the standard camera model and describe a general formulation and solution to the absolute camera pose problem that works for standard or distributed cameras. The proposed method computes a solution that is up to 8 times more efficient and robust to rotation singularities in comparison with gDLS. Finally, this method is used in an novel large-scale incremental SfM pipeline where distributed cameras are accurately and robustly merged together. This pipeline is a direct generalization of traditional incremental SfM; however, instead of incrementally adding one camera at a time to grow the reconstruction the reconstruction is grown by adding a distributed camera. Our pipeline produces highly accurate reconstructions efficiently by avoiding the need for many bundle adjustment iterations and is capable of computing a 3D model of Rome from over 15,000 images in just 22 minutes.
Large-scale Analysis of Chess Games with Chess Engines: A Preliminary Report
Venue: arXiv cs.AI 2016
Year: 2016

The strength of chess engines together with the availability of numerous chess games have attracted the attention of chess players, data scientists, and researchers during the last decades. State-of-the-art engines now provide an authoritative judgement that can be used in many applications like cheating detection, intrinsic ratings computation, skill assessment, or the study of human decision-making. A key issue for the research community is to gather a large dataset of chess games together with the judgement of chess engines. Unfortunately the analysis of each move takes lots of times. In this paper, we report our effort to analyse almost 5 millions chess games with a computing grid. During summer 2015, we processed 270 millions unique played positions using the Stockfish engine with a quite high depth (20). We populated a database of 1+ tera-octets of chess evaluations, representing an estimated time of 50 years of computation on a single machine. Our effort is a first step towards the replication of research results, the supply of open data and procedures for exploring new directions, and the investigation of software engineering/scalability issues when computing billions of moves.
Android Permission Model
Venue: arXiv cs.CR 2016
Year: 2016

The recent evolution on the smart phone technology has made its application market huge and less secure. Every single day large number of apps introduced in the android market (mostly on google play store) without any particular inspections which creates a lot of security issues and they remain unresolved. There are a lot of recent and increasing security issues which are mostly caused by the android apps. Mainly, the access of user data through the apps relied on the users given permission to apps.So, it is always a big question that how different apps on the android smart phones bypass the android permission model to have root access and how user data compromised or stolen by its apps. It is not startling that the Google Play Store has massive number of malicious apps that may gain users attention to fall victim for one, but some time it might be even worse than we thought. In this paper, we will look at the security issues (i.e. rooting phone, malware bypassing and secondary storage) and how easy to get access to users phone by using its app. Furthermore, I will discuss the android update mechanism and its functionalities as well as vulnerability to possible third party bypassing and root access. Moreover, a key feature and source of the all possible access route to android applications I will discuss an android permission model. Finally, I will first time present concept of the feature based development model implementing a feature based permission selections as a solution to android application system and describe the purposed Feature based permission model in detail how it is the solution for current security issues caused by intentional (evil coded) or unintentional (poorly coded) coding using android permission models.
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
Venue: arXiv cs.CC 2016
Year: 2016

In recent years, we have seen several approaches to the graph isomorphism problem based on "generic" mathematical programming or algebraic (Gröbner basis) techniques. For most of these, lower bounds have been established. In fact, it has been shown that the pairs of nonisomorphic CFI-graphs (introduced by Cai, Fürer, and Immerman in 1992 as hard examples for the combinatorial Weisfeiler-Leman algorithm) cannot be distinguished by these mathematical algorithms. A notable exception were the algebraic algorithms over the field GF(2), for which no lower bound was known. Another, in some way even stronger, approach to graph isomorphism testing is based on solving systems of linear Diophantine equations (that is, linear equations over the integers), which is known to be possible in polynomial time. So far, no lower bounds for this approach were known. Lower bounds for the algebraic algorithms can best be proved in the framework of proof complexity, where they can be phrased as lower bounds for algebraic proof systems such as Nullstellensatz or the (more powerful) polynomial calculus. We give new hard examples for these systems: families of pairs of non-isomorphic graphs that are hard to distinguish by polynomial calculus proofs simultaneously over all prime fields, including GF(2), as well as examples that are hard to distinguish by the systems-of-linear-Diophantine-equations approach. In a previous paper, we observed that the CFI-graphs are closely related to what we call "group CSPs": constraint satisfaction problems where the constraints are membership tests in some coset of a subgroup of a cartesian power of a base group (Z_2 in the case of the classical CFI-graphs). Our new examples are also based on group CSPs (for Abelian groups), but here we extend the CSPs by a few non-group constraints to obtain even harder instances for graph isomorphism.
Random-Key Cuckoo Search for the Travelling Salesman Problem
Venue: arXiv cs.NE 2016
Year: 2016

Combinatorial optimization problems are typically NP-hard, and thus very challenging to solve. In this paper, we present the random key cuckoo search (RKCS) algorithm for solving the famous Travelling Salesman Problem (TSP). We used a simplified random-key encoding scheme to pass from a continuous space (real numbers) to a combinatorial space. We also consider the displacement of a solution in both spaces using Levy flights. The performance of the proposed RKCS is tested against a set of benchmarks of symmetric TSP from the well-known TSPLIB library. The results of the tests show that RKCS is superior to some other metaheuristic algorithms.
Unequal Error Protection in Coded Slotted ALOHA
Venue: arXiv cs.IT 2016
Year: 2016

We analyze the performance of coded slotted ALOHA systems for a scenario where users have different error protection requirements and correspondingly can be divided into user classes. The main goal is to design the system so that the requirements for each class are satisfied. To that end, we derive analytical error floor approximations of the packet loss rate for each class in the finite frame length regime, as well as the density evolution in the asymptotic case. Based on this analysis, we propose a heuristic approach for the optimization of the degree distributions to provide the required unequal error protection. In addition, we analyze the decoding delay for users in different classes and show that better protected users experience a smaller average decoding delay.
Towards Stochastically Optimizing Data Computing Flows
Venue: arXiv cs.DC 2016
Year: 2016

With rapid growth in the amount of unstructured data produced by memory-intensive applications, large scale data analytics has recently attracted increasing interest. Processing, managing and analyzing this huge amount of data poses several challenges in cloud and data center computing domain. Especially, conventional frameworks for distributed data analytics are based on the assumption of homogeneity and non-stochastic distribution of different data-processing nodes. The paper argues the fundamental limiting factors for scaling big data computation. It is shown that as the number of series and parallel computing servers increase, the tail (mean and variance) of the job execution time increase. We will first propose a model to predict the response time of highly distributed processing tasks and then propose a new practical computational algorithm to optimize the response time.
Management of Renewable Energy for A Shared Facility Controller in Smart Grid
Venue: arXiv cs.SY 2016
Year: 2016

This paper proposes an energy management scheme to maximize the use of solar energy in the smart grid. In this context, a shared facility controller (SFC) with a number of solar photovoltaic (PV) panels in a smart community is considered that has the capability to schedule the generated energy for consumption and trade to other entities. Particularly, a mechanism is designed for the SFC to decide on the energy surplus, if there is any, that it can use to charge its battery and sell to the households and the grid based on the offered prices. In this regard, a hierarchical energy management scheme is proposed with a view to reduce the total operational cost to the SFC. The concept of a virtual cost (VC) is introduced that aids the SFC to estimate its future operational cost based on some available current information. The energy management is conducted for three different cases and the optimal cost to the SFC is determined for each case via the theory of maxima and minima. A real-time algorithm is proposed to reach the optimal cost for all cases and some numerical examples are provided to demonstrate the beneficial properties of the proposed scheme.
DCAR: A Discriminative and Compact Audio Representation to Improve Event Detection
Venue: arXiv cs.SD 2016
Year: 2016

This paper presents a novel two-phase method for audio representation, Discriminative and Compact Audio Representation (DCAR), and evaluates its performance at detecting events in consumer-produced videos. In the first phase of DCAR, each audio track is modeled using a Gaussian mixture model (GMM) that includes several components to capture the variability within that track. The second phase takes into account both global structure and local structure. In this phase, the components are rendered more discriminative and compact by formulating an optimization problem on Grassmannian manifolds, which we found represents the structure of audio effectively. Our experiments used the YLI-MED dataset (an open TRECVID-style video corpus based on YFCC100M), which includes ten events. The results show that the proposed DCAR representation consistently outperforms state-of-the-art audio representations. DCAR's advantage over i-vector, mv-vector, and GMM representations is significant for both easier and harder discrimination tasks. We discuss how these performance differences across easy and hard cases follow from how each type of model leverages (or doesn't leverage) the intrinsic structure of the data. Furthermore, DCAR shows a particularly notable accuracy advantage on events where humans have more difficulty classifying the videos, i.e., events with lower mean annotator confidence.
Password Generators: Old Ideas and New
Venue: arXiv cs.CR 2016
Year: 2016

This paper considers password generators, i.e. systems designed to generate site-specific passwords on demand. Such systems are an alternative to password managers. Over the last 15 years a range of password generator systems have been described. This paper proposes the first general model for such systems, and critically examines options for instantiating this model; options considered include all those previously proposed as part of existing schemes as well as certain novel possibilities. The model enables a more objective and high-level assessment of the design of such systems; it has also been used to sketch a possible new scheme, AutoPass, intended to incorporate the best features of the prior art whilst also addressing many of the most serious shortcomings of existing systems through the inclusion of novel features.
A Networked Swarm Model for UAV Deployment in the Assessment of Forest Environments
Venue: arXiv cs.RO 2016
Year: 2016

Autonomous Unmanned Aerial Vehicles (UAVs) have gained popularity due to their many potential application fields. Alongside sophisticated sensors, UAVs can be equipped with communication adaptors aimed for inter-UAV communication. Inter-communication of UAVs to form a UAV swarm raises questions on how to manage its communication structure and mobility. In this paper, we consider therefore the problem of establishing an efficient swarm movement model and a network topology between a collection of UAVs, which are specifically deployed for the scenario of high-quality forest-mapping. The forest environment with its highly heterogeneous distribution of trees and obstacles represents an extreme challenge for a UAV swarm. It requires the swarm to constantly avoid possible collisions with trees, to change autonomously the trajectory, which can lead to disconnection to the swarm, and to reconnect to the swarm after passing the obstacle, while continue collecting environmental data that needs to be fused and assessed efficiently. In this paper, we propose a novel solution to the formation flight problem for UAV swarms. The proposed method provides an adaptive and reliable network structure, which maintains swarm connectivity and communicability. These characteristics are needed to achieve a detailed and accurate description of the environment from the data acquired by the UAV swarm. The main characteristics of our approach are high scalability regarding the number of UAVs in the swarm and the adaptive network topology within the swarm.
The IDE as a Scriptable Information System (extended version)
Venue: arXiv cs.SE 2016
Year: 2016

Software engineering is extremely information-intensive. Every day developers work with source code, version repositories, issue trackers, documentation, web-based and other information resources. However, three key aspects of information work lack good support: (i) combining information from different sources; (ii) flexibly presenting collected information to enable easier comprehension; and (iii) automatically acting on collected information, for example to perform a refactoring. Poor support for these activities makes many common development tasks time-consuming and error-prone. We propose an approach that directly addresses these three issues by integrating a flexible query mechanism into the development environment. Our approach enables diverse ways to process and visualize information and can be extended via scripts. We demonstrate how an implementation of the approach can be used to rapidly write queries that meet a wide range of information needs.
Challenges in Decomposing Encodings of Verification Problems
Venue: arXiv cs.LO 2016
Year: 2016

Modern program verifiers use logic-based encodings of the verification problem that are discharged by a back end reasoning engine. However, instances of such encodings for large programs can quickly overwhelm these back end solvers. Hence, we need techniques to make the solving process scale to large systems, such as partitioning (divide-and-conquer) and abstraction. In recent work, we showed how decomposing the formula encoding of a termination analysis can significantly increase efficiency. The analysis generates a sequence of logical formulas with existentially quantified predicates that are solved by a synthesis-based program analysis engine. However, decomposition introduces abstractions in addition to those required for finding the unknown predicates in the formula, and can hence deteriorate precision. We discuss the challenges associated with such decompositions and their interdependencies with the solving process.
On Distance-$d$ Independent Set and other problems in graphs with few minimal separators
Venue: arXiv cs.DS 2016
Year: 2016

Fomin and Villanger (STACS 2010) proved that Maximum Independent Set, Feedback Vertex Set, and more generally the problem of finding a maximum induced subgraph of treewith at most a constant $t$, can be solved in polynomial time on graph classes with polynomially many minimal separators. We extend these results in two directions. Let $\Gpoly$ be the class of graphs with at most $\poly(n)$ minimal separators, for some polynomial $\poly$. We show that the odd powers of a graph $G$ have at most as many minimal separators as $G$. Consequently, \textsc{Distance-$d$ Independent Set}, which consists in finding maximum set of vertices at pairwise distance at least $d$, is polynomial on $\Gpoly$, for any even $d$. The problem is NP-hard on chordal graphs for any odd $d \geq 3$. We also provide polynomial algorithms for Connected Vertex Cover and Connected Feedback Vertex Set on subclasses of $\Gpoly$ including chordal and circular-arc graphs, and we discuss variants of independent domination problems.