OpenRaiser/Intern-Atlas huggingface dataset:
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
Venue: arXiv cs.LG 2016
Year: 2016

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial. More formally, in the problem of parity learning, an unknown string $x \in \{0,1\}^n$ was chosen uniformly at random. A learner tries to learn $x$ from a stream of samples $(a_1, b_1), (a_2, b_2) \ldots$, where each~$a_t$ is uniformly distributed over $\{0,1\}^n$ and $b_t$ is the inner product of $a_t$ and $x$, modulo~2. We show that any algorithm for parity learning, that uses less than $\frac{n^2}{25}$ bits of memory, requires an exponential number of samples. Previously, there was no non-trivial lower bound on the number of samples needed, for any learning problem, even if the allowed memory size is $O(n)$ (where $n$ is the space needed to store one sample). We also give an application of our result in the field of bounded-storage cryptography. We show an encryption scheme that requires a private key of length $n$, as well as time complexity of $n$ per encryption/decription of each bit, and is provenly and unconditionally secure as long as the attacker uses less than $\frac{n^2}{25}$ memory bits and the scheme is used at most an exponential number of times. Previous works on bounded-storage cryptography assumed that the memory size used by the attacker is at most linear in the time needed for encryption/decription.
Composable Industrial Internet Applications for Tiered Architectures
Venue: arXiv cs.CY 2016
Year: 2016

A single vendor cannot provide complete IIoT end-to-end solutions because cooperation is required from multiple parties. Interoperability is a key architectural quality. Composability of capabilities, information and configuration is the prerequisite for interoperability, supported by a data storage infrastructure and defined set of interfaces to build applications. Secure collection, transport and storage of data and algorithms are expectations for collaborative participation in any IIoT solution. Participants require control of their data ownership and confidentiality. We propose an Internet of Things, Services and People (IoTSP) application development and management framework which includes components for data storage, algorithm design and packaging, and computation execution. Applications use clusters of platform services, organized in tiers, and local access to data to reduce complexity and enhance reliable data exchange. Since communication is less reliable across tiers, data is synchronized between storage replicas when communication is available. The platform services provide a common ecosystem to exchange data uniting data storage, applications, and components that process the data. Configuration and orchestration of the tiers are managed using shared tools and facilities. The platform promotes the data storage components to be peers of the applications where each data owner is in control of when and how much information is shared with a service provider. The service components and applications are securely integrated using local event and data exchange communication channels. This tiered architecture reduces the cyber attack surface and enables individual tiers to operate autonomously, while addressing interoperability concerns. We present our framework using predictive maintenance as an example, and evaluate compatibility of our vision with an emerging set of standards.
Low rank tensor recovery via iterative hard thresholding
Venue: arXiv cs.IT 2016
Year: 2016

We study extensions of compressive sensing and low rank matrix recovery (matrix completion) to the recovery of low rank tensors of higher order from a small number of linear measurements. While the theoretical understanding of low rank matrix recovery is already well-developed, only few contributions on the low rank tensor recovery problem are available so far. In this paper, we introduce versions of the iterative hard thresholding algorithm for several tensor decompositions, namely the higher order singular value decomposition (HOSVD), the tensor train format (TT), and the general hierarchical Tucker decomposition (HT). We provide a partial convergence result for these algorithms which is based on a variant of the restricted isometry property of the measurement operator adapted to the tensor decomposition at hand that induces a corresponding notion of tensor rank. We show that subgaussian measurement ensembles satisfy the tensor restricted isometry property with high probability under a certain almost optimal bound on the number of measurements which depends on the corresponding tensor format. These bounds are extended to partial Fourier maps combined with random sign flips of the tensor entries. Finally, we illustrate the performance of iterative hard thresholding methods for tensor recovery via numerical experiments where we consider recovery from Gaussian random measurements, tensor completion (recovery of missing entries), and Fourier measurements for third order tensors.
Proportional Approval Method using Squared loads, Approval removal and Coin-flip approval transformation (PAMSAC) - a new system of proportional representation using approval voting
Venue: arXiv cs.GT 2016
Year: 2016

Several multi-winner systems that use approval voting have been developed but they each suffer from various problems. Six of these methods are discussed in this paper. They are Satisfaction Approval Voting, Minimax Approval Voting, Proportional Approval Voting, Monroe's Fully Proportional Representation, Chamberlin-Courant's Rule, and Ebert's method. They all fail at least one of Proportional Representation (PR), strong PR, monotonicity or positive support. However, the new method described in this paper - Proportional Approval Method using Squared loads, Approval removal and Coin-flip approval transformation (PAMSAC) - passes them all. PAMSAC uses the squared loads of Ebert's method, but removes non-beneficial approvals to restore monotonicity. It also uses the Coin-Flip Approval Transformation (CFAT), where voters are "split" into two for each candidate they approve, and where one half of this split voter approves and the other half does not approve each candidate approved on the ballot. This restores positive support, and also makes the method equivalent to the D'Hondt party-list method for party voting. PAMSAC reduces to simple approval voting in the single-winner case. A score voting version is described that also reduces to simple score voting in the single-winner case.
2D SEM images turn into 3D object models
Venue: arXiv cs.CV 2016
Year: 2016

The scanning electron microscopy (SEM) is probably one the most fascinating examination approach that has been used since more than two decades to detailed inspection of micro scale objects. Most of the scanning electron microscopes could only produce 2D images that could not assist operational analysis of microscopic surface properties. Computer vision algorithms combined with very advanced geometry and mathematical approaches turn any SEM into a full 3D measurement device. This work focuses on a methodical literature review for automatic 3D surface reconstruction of scanning electron microscope images.
Scheduling MapReduce Jobs under Multi-Round Precedences
Venue: arXiv cs.DS 2016
Year: 2016

We consider non-preemptive scheduling of MapReduce jobs with multiple tasks in the practical scenario where each job requires several map-reduce rounds. We seek to minimize the average weighted completion time and consider scheduling on identical and unrelated parallel processors. For identical processors, we present LP-based O(1)-approximation algorithms. For unrelated processors, the approximation ratio naturally depends on the maximum number of rounds of any job. Since the number of rounds per job in typical MapReduce algorithms is a small constant, our scheduling algorithms achieve a small approximation ratio in practice. For the single-round case, we substantially improve on previously best known approximation guarantees for both identical and unrelated processors. Moreover, we conduct an experimental analysis and compare the performance of our algorithms against a fast heuristic and a lower bound on the optimal solution, thus demonstrating their promising practical performance.
A Full-Bandwidth Audio Codec With Low Complexity And Very Low Delay
Venue: arXiv cs.MM 2016
Year: 2016

We propose an audio codec that addresses the low-delay requirements of some applications such as network music performance. The codec is based on the modified discrete cosine transform (MDCT) with very short frames and uses gain-shape quantization to preserve the spectral envelope. The short frame sizes required for low delay typically hinder the performance of transform codecs. However, at 96 kbit/s and with only 4 ms algorithmic delay, the proposed codec out-performs the ULD codec operating at the same rate. The total complexity of the codec is small, at only 17 WMOPS for real-time operation at 48 kHz.
Global Synchronization Protection for Bandwidth Sharing TCP Flows in High-Speed Links
Venue: arXiv cs.NI 2016
Year: 2016

In a congested network link, synchronization effects between bandwidth-sharing TCP flows cause wide queue length oscillations, which may translate into poor link utilization if insufficiently buffered. We introduce global synchronization protection (GSP), a simple extension to the ordinary operation of a tail-drop queue that safely suppresses the flow synchronization. Our minimalistic solution is well suited for scaling with leading-edge link rates: it adds only few extra operations in the fast path and does not require accelerated memory access compared to the line rate. GSP makes it easier to provide advanced control of TCP congestion in high-speed links and in low-power packet processing hardware. Using experiments with a Linux prototype of GSP, we show that, despite its exclusive focus on removing global synchronization, the new scheme performs as well as far more complex active queue management (AQM) schemes like CoDel and PIE.
Cross-Language Domain Adaptation for Classifying Crisis-Related Short Messages
Venue: arXiv cs.CL 2016
Year: 2016

Rapid crisis response requires real-time analysis of messages. After a disaster happens, volunteers attempt to classify tweets to determine needs, e.g., supplies, infrastructure damage, etc. Given labeled data, supervised machine learning can help classify these messages. Scarcity of labeled data causes poor performance in machine training. Can we reuse old tweets to train classifiers? How can we choose labeled tweets for training? Specifically, we study the usefulness of labeled data of past events. Do labeled tweets in different language help? We observe the performance of our classifiers trained using different combinations of training sets obtained from past disasters. We perform extensive experimentation on real crisis datasets and show that the past labels are useful when both source and target events are of the same type (e.g. both earthquakes). For similar languages (e.g., Italian and Spanish), cross-language domain adaptation was useful, however, when for different languages (e.g., Italian and English), the performance decreased.
Unifying Requirements and Code: an Example
Venue: arXiv cs.SE 2016
Year: 2016

Requirements and code, in conventional software engineering wisdom, belong to entirely different worlds. Is it possible to unify these two worlds? A unified framework could help make software easier to change and reuse. To explore the feasibility of such an approach, the case study reported here takes a classic example from the requirements engineering literature and describes it using a programming language framework to express both domain and machine properties. The paper describes the solution, discusses its benefits and limitations, and assesses its scalability.
Multihead Multitrack Detection with Reduced-State Sequence Estimation
Venue: arXiv cs.IT 2016
Year: 2016

To achieve ultra-high storage capacity, the data tracks are squeezed more and more on the magnetic recording disks, causing severe intertrack interference (ITI). The multihead multitrack (MHMT) detector is proposed to better combat ITI. Such a detector, however, has prohibitive implementation complexity. In this paper we propose to use the reduced-state sequence estimation (RSSE) algorithm to significantly reduce the complexity, and render MHMT practical. We first consider a commonly used symmetric two-head two-track (2H2T) channel model. The effective distance between two input symbols is redefined. It provides a better distance measure and naturally leads to an unbalanced set partition tree. Different trellis configurations are obtained based on the desired performance/complexity tradeoff. Simulation results show that the reduced MHMT detector can achieve near maximum-likelihood (ML) performance with a small fraction of the original number of trellis states. Error event analysis is given to explain the behavior of RSSE algorithm on 2H2T channel. Search results of dominant RSSE error events for different channel targets are presented. We also study an asymmetric 2H2T system. The simulation results and error event analysis show that RSSE is applicable to the asymmetric channel.
Fault and Byzantine Tolerant Self-stabilizing Mobile Robots Gathering - Feasibility Study -
Venue: arXiv cs.RO 2016
Year: 2016

Gathering is a fundamental coordination problem in cooperative mobile robotics. In short, given a set of robots with arbitrary initial locations and no initial agreement on a global coordinate system, gathering requires that all robots, following their algorithm, reach the exact same but not predetermined location. Gathering is particularly challenging in networks where robots are oblivious (i.e., stateless) and direct communication is replaced by observations on their respective locations. Interestingly any algorithm that solves gathering with oblivious robots is inherently self-stabilizing if no specific assumption is made on the initial distribution of the robots. In this paper, we significantly extend the studies of de-terministic gathering feasibility under different assumptions This manuscript considerably extends preliminary results presented as an extended abstract at the DISC 2006 conference [7]. The current version is under review at Distributed Computing Journal since February 2012 (in a previous form) and since 2014 in the current form. The most important results have been also presented in MAC 2010 organized in Ottawa from August 15th to 17th 2010 related to synchrony and faults (crash and Byzantine). Unlike prior work, we consider a larger set of scheduling strategies, such as bounded schedulers. In addition, we extend our study to the feasibility of probabilistic self-stabilizing gathering in both fault-free and fault-prone environments.
Energy-Efficient Resource Allocation Optimization for Multimedia Heterogeneous Cloud Radio Access Networks
Venue: arXiv cs.NI 2016
Year: 2016

The heterogeneous cloud radio access network (H-CRAN) is a promising paradigm which incorporates the cloud computing into heterogeneous networks (HetNets), thereby taking full advantage of cloud radio access networks (C-RANs) and HetNets. Characterizing the cooperative beamforming with fronthaul capacity and queue stability constraints is critical for multimedia applications to improving energy efficiency (EE) in H-CRANs. An energy-efficient optimization objective function with individual fronthaul capacity and inter-tier interference constraints is presented in this paper for queue-aware multimedia H-CRANs. To solve this non-convex objective function, a stochastic optimization problem is reformulated by introducing the general Lyapunov optimization framework. Under the Lyapunov framework, this optimization problem is equivalent to an optimal network-wide cooperative beamformer design algorithm with instantaneous power, average power and inter-tier interference constraints, which can be regarded as the weighted sum EE maximization problem and solved by a generalized weighted minimum mean square error approach. The mathematical analysis and simulation results demonstrate that a tradeoff between EE and queuing delay can be achieved, and this tradeoff strictly depends on the fronthaul constraint.
Differentiated latency in data center networks with erasure coded files through traffic engineering
Venue: arXiv cs.DC 2016
Year: 2016

This paper proposes an algorithm to minimize weighted service latency for different classes of tenants (or service classes) in a data center network where erasure-coded files are stored on distributed disks/racks and access requests are scattered across the network. Due to limited bandwidth available at both top-of-the-rack and aggregation switches and tenants in different service classes need differentiated services, network bandwidth must be apportioned among different intra- and inter-rack data flows for different service classes in line with their traffic statistics. We formulate this problem as weighted queuing and employ a class of probabilistic request scheduling policies to derive a closed-form upper-bound of service latency for erasure-coded storage with arbitrary file access patterns and service time distributions. The result enables us to propose a joint weighted latency (over different service classes) optimization over three entangled "control knobs": the bandwidth allocation at top-of-the-rack and aggregation switches for different service classes, dynamic scheduling of file requests, and the placement of encoded file chunks (i.e., data locality). The joint optimization is shown to be a mixed-integer problem. We develop an iterative algorithm which decouples and solves the joint optimization as 3 sub-problems, which are either convex or solvable via bipartite matching in polynomial time. The proposed algorithm is prototyped in an open-source, distributed file system, {\em Tahoe}, and evaluated on a cloud testbed with 16 separate physical hosts in an Openstack cluster using 48-port Cisco Catalyst switches. Experiments validate our theoretical latency analysis and show significant latency reduction for diverse file access patterns. The results provide valuable insights on designing low-latency data center networks with erasure coded storage.
Key Economic and Environmental Perspectives on Sustainability in the ICT Sector
Venue: arXiv cs.CY 2016
Year: 2016

Telecommunication networks have become as critical to the 21st century development as were railways, roads and canals, to the 19th Century developments and is now seen as enabler to a more sustained business, environment and society as a whole. Still fascinating has been and is the exponential rate of growth in this industry. This is one sector where the next revolution is always just around the corner whether known or unknown. The telecoms industry is categorized by high rates of innovation in a rapidly changing technological environment. This in turn is associated with an immense range of sustainability concerns and challenges for the Telecoms service providers, the service users and the whole industry and its far reaching influence on other industries. This paper discusses three key aspects of such challenges namely; the question of sustainable power/energy supply for the industry when the change is resulting in increasing energy and operational cost, the exploitation of technologies advancement for sustainability and their business and environmental benefits.
Audio Recording Device Identification Based on Deep Learning
Venue: arXiv cs.SD 2016
Year: 2016

In this paper we present a research on identification of audio recording devices from background noise, thus providing a method for forensics. The audio signal is the sum of speech signal and noise signal. Usually, people pay more attention to speech signal, because it carries the information to deliver. So a great amount of researches have been dedicated to getting higher Signal-Noise-Ratio (SNR). There are many speech enhancement algorithms to improve the quality of the speech, which can be seen as reducing the noise. However, noises can be regarded as the intrinsic fingerprint traces of an audio recording device. These digital traces can be characterized and identified by new machine learning techniques. Therefore, in our research, we use the noise as the intrinsic features. As for the identification, multiple classifiers of deep learning methods are used and compared. The identification result shows that the method of getting feature vector from the noise of each device and identifying them with deep learning techniques is viable, and well-preformed.
An improved analysis of the ER-SpUD dictionary learning algorithm
Venue: arXiv cs.LG 2016
Year: 2016

In "dictionary learning" we observe $Y = AX + E$ for some $Y\in\mathbb{R}^{n\times p}$, $A \in\mathbb{R}^{m\times n}$, and $X\in\mathbb{R}^{m\times p}$. The matrix $Y$ is observed, and $A, X, E$ are unknown. Here $E$ is "noise" of small norm, and $X$ is column-wise sparse. The matrix $A$ is referred to as a {\em dictionary}, and its columns as {\em atoms}. Then, given some small number $p$ of samples, i.e.\ columns of $Y$, the goal is to learn the dictionary $A$ up to small error, as well as $X$. The motivation is that in many applications data is expected to sparse when represented by atoms in the "right" dictionary $A$ (e.g.\ images in the Haar wavelet basis), and the goal is to learn $A$ from the data to then use it for other applications. Recently, [SWW12] proposed the dictionary learning algorithm ER-SpUD with provable guarantees when $E = 0$ and $m = n$. They showed if $X$ has independent entries with an expected $s$ non-zeroes per column for $1 \lesssim s \lesssim \sqrt{n}$, and with non-zero entries being subgaussian, then for $p\gtrsim n^2\log^2 n$ with high probability ER-SpUD outputs matrices $A', X'$ which equal $A, X$ up to permuting and scaling columns (resp.\ rows) of $A$ (resp.\ $X$). They conjectured $p\gtrsim n\log n$ suffices, which they showed was information theoretically necessary for {\em any} algorithm to succeed when $s \simeq 1$. Significant progress was later obtained in [LV15]. We show that for a slight variant of ER-SpUD, $p\gtrsim n\log(n/δ)$ samples suffice for successful recovery with probability $1-δ$. We also show that for the unmodified ER-SpUD, $p\gtrsim n^{1.99}$ samples are required even to learn $A, X$ with polynomially small success probability. This resolves the main conjecture of [SWW12], and contradicts the main result of [LV15], which claimed that $p\gtrsim n\log^4 n$ guarantees success whp.
Restricted deterministic Watson-Crick automata
Venue: arXiv cs.FL 2016
Year: 2016

In this paper, we introduce a new model of deterministic Watson-Crick automaton namely restricted deterministic Watson- Crick automaton which is a deterministic Watson-Crick automaton where the complementarity string in the lower strand is restricted to a language L. We examine the computational power of the restricted model with respect to L being in different language classes such as regular, unary regular, finite, context free and context sensitive. We also show that computational power of restricted deterministic Watson- Crick automata with L in regular languages is same as that of deterministic Watson-Crick automata and that the set of all languages accepted by restricted deterministic Watson-Crick automata with L in unary regular languages is a proper subset of context free languages.