OpenRaiser/Intern-Atlas huggingface dataset:
Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?
Venue: arXiv cs.NE 2016
Year: 2016

Three important properties of a classification machinery are: (i) the system preserves the core information of the input data; (ii) the training examples convey information about unseen data; and (iii) the system is able to treat differently points from different classes. In this work we show that these fundamental properties are satisfied by the architecture of deep neural networks. We formally prove that these networks with random Gaussian weights perform a distance-preserving embedding of the data, with a special treatment for in-class and out-of-class data. Similar points at the input of the network are likely to have a similar output. The theoretical analysis of deep networks here presented exploits tools used in the compressed sensing and dictionary learning literature, thereby making a formal connection between these important topics. The derived results allow drawing conclusions on the metric learning properties of the network and their relation to its structure, as well as providing bounds on the required size of the training set such that the training examples would represent faithfully the unseen data. The results are validated with state-of-the-art trained networks.
Learning Cooperative Games
Venue: arXiv cs.GT 2016
Year: 2016

This paper explores a PAC (probably approximately correct) learning model in cooperative games. Specifically, we are given $m$ random samples of coalitions and their values, taken from some unknown cooperative game; can we predict the values of unseen coalitions? We study the PAC learnability of several well-known classes of cooperative games, such as network flow games, threshold task games, and induced subgraph games. We also establish a novel connection between PAC learnability and core stability: for games that are efficiently learnable, it is possible to find payoff divisions that are likely to be stable using a polynomial number of samples.
Robust Neighbor Discovery in Multi-Hop Multi-Channel Heterogeneous Wireless Networks
Venue: arXiv cs.DC 2016
Year: 2016

An important first step when deploying a wireless ad hoc network is neighbor discovery in which every node attempts to determine the set of nodes it can communicate with in one wireless hop. In the recent years, cognitive radio (CR) technology has gained attention as an attractive approach to alleviate spectrum congestion. A cognitive radio transceiver can operate over a wide range of frequencies, possibly scanning multiple frequency bands. A cognitive radio node can opportunistically utilize unused wireless spectrum without interference from other wireless devices in its vicinity. Due to spatial variations in frequency usage and hardware variations in radio transceivers, different nodes in the network may perceive different subsets of frequencies available to them for communication. This heterogeneity in the available channel sets across the network increases the complexity of solving the neighbor discovery problem in a cognitive radio network. In this work, we design and analyze several randomized algorithms for neighbor discovery in such a (heterogeneous) network under a variety of assumptions (e.g. maximum node degree known or unknown) for both synchronous and asynchronous systems under minimal knowledge. We also show that our randomized algorithms are naturally suited to tolerate unreliable channels and adversarial attacks.
Power Allocation and Measurement Matrix Design for Block CS-Based Distributed MIMO Radars
Venue: arXiv cs.IT 2016
Year: 2016

Multiple-input multiple-output (MIMO) radars offer higher resolution, better target detection, and more accurate target parameter estimation. Due to the sparsity of the targets in space-velocity domain, we can exploit Compressive Sensing (CS) to improve the performance of MIMO radars when the sampling rate is much less than the Nyquist rate. In distributed MIMO radars, block CS methods can be used instead of classical CS ones for more performance improvement, because the received signal in this group of MIMO radars is a block sparse signal in a basis. In this paper, two new methods are proposed to improve the performance of the block CS-based distributed MIMO radars. The first one is a new method for optimal energy allocation to the transmitters, and the other one is a new method for optimal design of the measurement matrix. These methods are based on the minimization of an upper bound of the sensing matrix block-coherence. Simulation results show an increase in the accuracy of multiple targets parameters estimation for both proposed methods.
Physical Layer Security in Massive MIMO
Venue: arXiv cs.IT 2016
Year: 2016

We consider a single-cell downlink massive MIMO communication in the presence of an adversary capable of jamming and eavesdropping simultaneously. We show that massive MIMO communication is naturally resilient to no training-phase jamming attack in which the adversary jams only the data communication and eavesdrops both the data communication and the training. Specifically, we show that the secure degrees of freedom (DoF) attained in the presence of such an attack is identical to the maximum DoF attained under no attack. Further, we evaluate the number of antennas that base station (BS) requires in order to establish information theoretic security without even a need for Wyner encoding. Next, we show that things are completely different once the adversary starts jamming the training phase. Specifically, we consider an attack, called training-phase jamming in which the adversary jams and eavesdrops both the training and the data communication. We show that under such an attack, the maximum secure DoF is equal to zero. Furthermore, the maximum achievable rates of users vanish even in the asymptotic regime in the number of BS antennas. To counter this attack, we develop a defense strategy in which we use a secret key to encrypt the pilot sequence assignments to hide them from the adversary, rather than encrypt the data. We show that, if the cardinality of the set of pilot signals are scaled appropriately, hiding the pilot signal assignments from the adversary enables the users to achieve secure DoF, identical to the maximum achievable DoF under no attack. Finally, we discuss how computational cryptography is a legitimate candidate to hide the pilot signal assignments. Indeed, while information theoretic security is not achieved with cryptography, the computational power necessary for the adversary to achieve a non-zero mutual information leakage rate goes to infinity.
The Minimal and Maximal Sensitivity of the Simplified Weighted Sum Function
Venue: arXiv cs.DM 2016
Year: 2016

Sensitivity is an important complexity measure of Boolean functions. In this paper we present properties of the minimal and maximal sensitivity of the simplified weighted sum function. A simple close formula of the minimal sensitivity of the simplified weighted sum function is obtained. A phenomenon is exhibited that the minimal sensitivity of the weighted sum function is indeed an indicator of large primes, that is, for large prime number p, the minimal sensitivity of the weighted sum function is always equal to one.
Activity Dynamics in Collaboration Networks
Venue: arXiv cs.SI 2016
Year: 2016

Many online collaboration networks struggle to gain user activity and become self-sustaining due to the ramp-up problem or dwindling activity within the system. Prominent examples include online encyclopedias such as (Semantic) MediaWikis, Question and Answering portals such as StackOverflow, and many others. Only a small fraction of these systems manage to reach self-sustaining activity, a level of activity that prevents the system from reverting to a non-active state. In this paper, we model and analyze activity dynamics in synthetic and empirical collaboration networks. Our approach is based on two opposing and well-studied principles: (i) without incentives, users tend to lose interest to contribute and thus, systems become inactive, and (ii) people are susceptible to actions taken by their peers (social or peer influence). With the activity dynamics model that we introduce in this paper we can represent typical situations of such collaboration networks. For example, activity in a collaborative network, without external impulses or investments, will vanish over time, eventually rendering the system inactive. However, by appropriately manipulating the activity dynamics and/or the underlying collaboration networks, we can jump-start a previously inactive system and advance it towards an active state. To be able to do so, we first describe our model and its underlying mechanisms. We then provide illustrative examples of empirical datasets and characterize the barrier that has to be breached by a system before it can become self-sustaining in terms of critical mass and activity dynamics. Additionally, we expand on this empirical illustration and introduce a new metric p---the Activity Momentum---to assess the activity robustness of collaboration networks.
Secrecy Analysis on Network Coding in Bidirectional Multibeam Satellite Communications
Venue: arXiv cs.IT 2016
Year: 2016

Network coding is an efficient means to improve the spectrum efficiency of satellite communications. However, its resilience to eavesdropping attacks is not well understood. This paper studies the confidentiality issue in a bidirectional satellite network consisting of two mobile users who want to exchange message via a multibeam satellite using the XOR network coding protocol. We aim to maximize the sum secrecy rate by designing the optimal beamforming vector along with optimizing the return and forward link time allocation. The problem is non-convex, and we find its optimal solution using semidefinite programming together with a 1-D search. For comparison, we also solve the sum secrecy rate maximization problem for a conventional reference scheme without using network coding. Simulation results using realistic system parameters demonstrate that the bidirectional scheme using network coding provides considerably higher secrecy rate compared to that of the conventional scheme.
Learning image representations tied to ego-motion
Venue: arXiv cs.CV 2016
Year: 2016

Understanding how images of objects and scenes behave in response to specific ego-motions is a crucial aspect of proper visual development, yet existing visual learning methods are conspicuously disconnected from the physical source of their images. We propose to exploit proprioceptive motor signals to provide unsupervised regularization in convolutional neural networks to learn visual representations from egocentric video. Specifically, we enforce that our learned features exhibit equivariance i.e. they respond predictably to transformations associated with distinct ego-motions. With three datasets, we show that our unsupervised feature learning approach significantly outperforms previous approaches on visual recognition and next-best-view prediction tasks. In the most challenging test, we show that features learned from video captured on an autonomous driving platform improve large-scale scene recognition in static images from a disjoint domain.
Time4: Time for SDN
Venue: arXiv cs.NI 2016
Year: 2016

With the rise of Software Defined Networks (SDN), there is growing interest in dynamic and centralized traffic engineering, where decisions about forwarding paths are taken dynamically from a network-wide perspective. Frequent path reconfiguration can significantly improve the network performance, but should be handled with care, so as to minimize disruptions that may occur during network updates. In this paper we introduce Time4, an approach that uses accurate time to coordinate network updates. Time4 is a powerful tool in softwarized environments, that can be used for various network update scenarios. Specifically, we characterize a set of update scenarios called flow swaps, for which Time4 is the optimal update approach, yielding less packet loss than existing update approaches. We define the lossless flow allocation problem, and formally show that in environments with frequent path allocation, scenarios that require simultaneous changes at multiple network devices are inevitable. We present the design, implementation, and evaluation of a Time4-enabled OpenFlow prototype. The prototype is publicly available as open source. Our work includes an extension to the OpenFlow protocol that has been adopted by the Open Networking Foundation (ONF), and is now included in OpenFlow 1.5. Our experimental results show the significant advantages of Time4 compared to other network update approaches, and demonstrate an SDN use case that is infeasible without Time4.
Brain Tumor Segmentation with Deep Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we present a fully automatic brain tumor segmentation method based on Deep Neural Networks (DNNs). The proposed networks are tailored to glioblastomas (both low and high grade) pictured in MR images. By their very nature, these tumors can appear anywhere in the brain and have almost any kind of shape, size, and contrast. These reasons motivate our exploration of a machine learning solution that exploits a flexible, high capacity DNN while being extremely efficient. Here, we give a description of different model choices that we've found to be necessary for obtaining competitive performance. We explore in particular different architectures based on Convolutional Neural Networks (CNN), i.e. DNNs specifically adapted to image data. We present a novel CNN architecture which differs from those traditionally used in computer vision. Our CNN exploits both local features as well as more global contextual features simultaneously. Also, different from most traditional uses of CNNs, our networks use a final layer that is a convolutional implementation of a fully connected layer which allows a 40 fold speed up. We also describe a 2-phase training procedure that allows us to tackle difficulties related to the imbalance of tumor labels. Finally, we explore a cascade architecture in which the output of a basic CNN is treated as an additional source of information for a subsequent CNN. Results reported on the 2013 BRATS test dataset reveal that our architecture improves over the currently published state-of-the-art while being over 30 times faster.
Stars and Celebrities: A Network Creation Game
Venue: arXiv cs.GT 2016
Year: 2016

Celebrity games, a new model of network creation games is introduced. The specific features of this model are that players have different celebrity weights and that a critical distance is taken into consideration. The aim of any player is to be close (at distance less than critical) to the others, mainly to those with high celebrity weights. The cost of each player depends on the cost of establishing direct links to other players and on the sum of the weights of those players at a distance greater than the critical distance. We show that celebrity games always have pure Nash equilibria and we characterize the family of subgames having connected Nash equilibria, the so called star celebrity games. We provide exact bounds for the PoA of celebrity games. The PoA can be tightened when restricted to particular classes of Nash equilibria graphs, in particular for trees.
Norm Monitoring under Partial Action Observability
Venue: arXiv cs.MA 2016
Year: 2016

In the context of using norms for controlling multi-agent systems, a vitally important question that has not yet been addressed in the literature is the development of mechanisms for monitoring norm compliance under partial action observability. This paper proposes the reconstruction of unobserved actions to tackle this problem. In particular, we formalise the problem of reconstructing unobserved actions, and propose an information model and algorithms for monitoring norms under partial action observability using two different processes for reconstructing unobserved actions. Our evaluation shows that reconstructing unobserved actions increases significantly the number of norm violations and fulfilments detected.
Partitioned Multiprocessor Fixed-Priority Scheduling of Sporadic Real-Time Tasks
Venue: arXiv cs.DS 2016
Year: 2016

Partitioned multiprocessor scheduling has been widely accepted in academia and industry to statically assign and partition real-time tasks onto identical multiprocessor systems. This paper studies fixed-priority partitioned multiprocessor scheduling for sporadic real-time systems, in which deadline-monotonic scheduling is applied on each processor. Prior to this paper, the best known results are by Fisher, Baruah, and Baker with speedup factors $4-\frac{2}{M}$ and $3-\frac{1}{M}$ for arbitrary-deadline and constrained-deadline sporadic real-time task systems, respectively, where $M$ is the number of processors. We show that a greedy mapping strategy has a speedup factor $3-\frac{1}{M}$ when considering task systems with arbitrary deadlines. Such a factor holds for polynomial-time schedulability tests and exponential-time (exact) schedulability tests. Moreover, we also improve the speedup factor to $2.84306$ when considering constrained-deadline task systems. We also provide tight examples when the fitting strategy in the mapping stage is arbitrary and $M$ is sufficiently large. For both constrained- and arbitrary-deadline task systems, the analytical result surprisingly shows that using exact tests does not gain theoretical benefits (with respect to speedup factors) for an arbitrary fitting strategy.
Packet Efficient Implementation of the Omega Failure Detector
Venue: arXiv cs.DC 2016
Year: 2016

We assume that a message may be delivered by packets through multiple hops and investigate the feasibility and efficiency of an implementation of the Omega Failure Detector under such an assumption.To motivate the study, we prove that the existence and sustainability of a leader is exponentially more probable in a multi-hop Omega implementation than in a single-hop one.An implementation is: \emph{message efficient} if all but finitely many messages are sent by a single process; \emph{packet efficient} if the number of packets used to transmit a message in all but finitely many messages is linear w.r.t the number of processes, packets of different messages may potentially use different channels, thus the number of used channels is not limited; \emph{super packet efficient} if the number of channels used by packets to transmit all but finitely many messages is linear.We present the following results for deterministic algorithms. If reliability and timeliness of one message does not correlate with another, i.e., there are no channel reliability properties, then a packet efficient implementation of Omega is impossible. If eventuallytimely and fair-lossy channels are considered, we establish necessary and sufficient conditions for the existence of a message and packet efficient implementation of Omega. We also prove that the eventuality of timeliness of channels makes a super packet efficientimplementation of Omega impossible. On the constructive side, we present and prove correct a deterministic packet efficient implementation of Omega that matches the necessary conditions we established.
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
Venue: arXiv cs.IT 2016
Year: 2016

We consider the fundamental problem of solving quadratic systems of equations in $n$ variables, where $y_i = |\langle \boldsymbol{a}_i, \boldsymbol{x} \rangle|^2$, $i = 1, \ldots, m$ and $\boldsymbol{x} \in \mathbb{R}^n$ is unknown. We propose a novel method, which starting with an initial guess computed by means of a spectral method, proceeds by minimizing a nonconvex functional as in the Wirtinger flow approach. There are several key distinguishing features, most notably, a distinct objective functional and novel update rules, which operate in an adaptive fashion and drop terms bearing too much influence on the search direction. These careful selection rules provide a tighter initial guess, better descent directions, and thus enhanced practical performance. On the theoretical side, we prove that for certain unstructured models of quadratic systems, our algorithms return the correct solution in linear time, i.e. in time proportional to reading the data $\{\boldsymbol{a}_i\}$ and $\{y_i\}$ as soon as the ratio $m/n$ between the number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems in which we only have $y_i \approx |\langle \boldsymbol{a}_i, \boldsymbol{x} \rangle|^2$ and prove that our algorithms achieve a statistical accuracy, which is nearly un-improvable. We complement our theoretical study with numerical examples showing that solving random quadratic systems is both computationally and statistically not much harder than solving linear systems of the same size---hence the title of this paper. For instance, we demonstrate empirically that the computational cost of our algorithm is about four times that of solving a least-squares problem of the same size.
The Distortion Rate Function of Cyclostationary Gaussian Processes
Venue: arXiv cs.IT 2016
Year: 2016

A general expression for the distortion rate function (DRF) of cyclostationary Gaussian processes in terms of their spectral properties is derived. This expression can be seen as the result of orthogonalization over the different components in the polyphase decomposition of the process. We use this expression to derive, in a closed form, the DRF of several cyclostationary processes arising in practice. We first consider the DRF of a combined sampling and source coding problem. It is known that the optimal coding strategy for this problem involves source coding applied to a signal with the same structure as one resulting from pulse amplitude modulation (PAM). Since a PAM-modulated signal is cyclostationary, our DRF expression can be used to solve for the minimal distortion in the combined sampling and source coding problem. We also analyze in more detail the DRF of a source with the same structure as a PAM-modulated signal, and show that it is obtained by reverse waterfilling over an expression that depends on the energy of the pulse and the baseband process modulated to obtain the PAM signal. This result is then used to study the information content of a PAM-modulated signal as a function of its symbol time relative to the bandwidth of the underlying baseband process. In addition, we also study the DRF of sources with an amplitude-modulation structure, and show that the DRF of a narrow-band Gaussian stationary process modulated by either a deterministic or a random phase sine-wave equals the DRF of the baseband process.
Pitfalls in Designing Zero-Effort Deauthentication: Opportunistic Human Observation Attacks
Venue: arXiv cs.CR 2016
Year: 2016

Deauthentication is an important component of any authentication system. The widespread use of computing devices in daily life has underscored the need for zero-effort deauthentication schemes. However, the quest for eliminating user effort may lead to hidden security flaws in the authentication schemes. As a case in point, we investigate a prominent zero-effort deauthentication scheme, called ZEBRA, which provides an interesting and a useful solution to a difficult problem as demonstrated in the original paper. We identify a subtle incorrect assumption in its adversary model that leads to a fundamental design flaw. We exploit this to break the scheme with a class of attacks that are much easier for a human to perform in a realistic adversary model, compared to the naïve attacks studied in the ZEBRA paper. For example, one of our main attacks, where the human attacker has to opportunistically mimic only the victim's keyboard typing activity at a nearby terminal, is significantly more successful compared to the naïve attack that requires mimicking keyboard and mouse activities as well as keyboard-mouse movements. Further, by understanding the design flaws in ZEBRA as cases of tainted input, we show that we can draw on well-understood design principles to improve ZEBRA's security.