OpenRaiser/Intern-Atlas huggingface dataset:
Quantum Advantage on Information Leakage for Equality
Venue: arXiv cs.CC 2016
Year: 2016

We prove a lower bound on the information leakage of any classical protocol computing the equality function in the simultaneous message passing (SMP) model. Our bound is valid in the finite length regime and is strong enough to demonstrate a quantum advantage in terms of information leakage for practical quantum protocols. We prove our bound by obtaining an improved finite size version of the communication bound due to Babai and Kimmel, relating randomized communication to deterministic communication in the SMP model. We then relate information leakage to randomized communication through a series of reductions. We first provide alternative characterizations for information leakage, allowing us to link it to average length communication while allowing for shared randomness (pairwise, with the referee). A Markov inequality links this with bounded length communication, and a Newman type argument allows us to go from shared to private randomness. The only reduction in which we incur more than a logarithmic additive factor is in the Markov inequality; in particular, our compression method is essentially tight for the SMP model with average length communication.
Pilot Decontamination via PDP Alignment
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we look into the issue of intra-cell uplink (UL) pilot orthogonalization and schemes for mitigating the inter-cell pilot contamination with a realistic massive multi-input multi-output (MIMO) orthogonal frequency-division multiplexing (OFDM) system model. First, we show how to align the power-delay profiles (PDP) of different users served by one BS so that the pilots sent within one common OFDM symbol are orthogonal. From the derived aligning rule, we see much more users can be sounded in the same OFDM symbol as their channels are sparse in time. Second, in the case of massive MIMO, we show how PDP alignment can help to alleviate the pilot contamination due to inter-cell interference. We demonstrate that, by utilizing the fact that different paths in time are associated with different angles of arrival (AoA), the pilot contamination can be significantly reduced through aligning the PDPs of the users served by different BSs appropriately. Computer simulations further convince us PDP aligning can serve as the new baseline design philosophy for the UL pilots in massive MIMO.
Machine Learned Resume-Job Matching Solution
Venue: arXiv cs.CL 2016
Year: 2016

Job search through online matching engines nowadays are very prominent and beneficial to both job seekers and employers. But the solutions of traditional engines without understanding the semantic meanings of different resumes have not kept pace with the incredible changes in machine learning techniques and computing capability. These solutions are usually driven by manual rules and predefined weights of keywords which lead to an inefficient and frustrating search experience. To this end, we present a machine learned solution with rich features and deep learning methods. Our solution includes three configurable modules that can be plugged with little restrictions. Namely, unsupervised feature extraction, base classifiers training and ensemble method learning. In our solution, rather than using manual rules, machine learned methods to automatically detect the semantic similarity of positions are proposed. Then four competitive "shallow" estimators and "deep" estimators are selected. Finally, ensemble methods to bag these estimators and aggregate their individual predictions to form a final prediction are verified. Experimental results of over 47 thousand resumes show that our solution can significantly improve the predication precision current position, salary, educational background and company scale.
Low-complexity feedback-channel-free distributed video coding using Local Rank Transform
Venue: arXiv cs.MM 2016
Year: 2016

In this paper, we propose a new feedback-channel-free Distributed Video Coding (DVC) algorithm using Local Rank Transform (LRT). The encoder computes LRT by considering selected neighborhood pixels of Wyner-Ziv frame. The ranks from the modified LRT are merged, and their positions are entropy coded and sent to the decoder. In addition, means of each block of Wyner-Ziv frame are also transmitted to assist motion estimation. Using these measurements, the decoder generates side information (SI) by implementing motion estimation and compensation in LRT domain. An iterative algorithm is executed on SI using LRT to reconstruct the Wyner-Ziv frame. Experimental results show that the coding efficiency of our codec is close to the efficiency of pixel domain distributed video coders based on Low-Density Parity Check and Accumulate (LDPCA) or turbo codes, with less encoder complexity.
Analysis and Design of Adaptive OCDMA Passive Optical Networks
Venue: arXiv cs.IT 2016
Year: 2016

OCDMA systems can support multiple classes of service by differentiating code parameters, power level and diversity order. In this paper, we analyze BER performance of a multi-class 1D/2D OCDMA system and propose a new approximation method that can be used to generate accurate estimation of system BER using a simple mathematical form. The proposed approximation provides insight into proper system level analysis, system level design and sensitivity of system performance to the factors such as code parameters, power level and diversity order. Considering code design, code cardinality and system performance constraints, two design problems are defined and their optimal solutions are provided. We then propose an adaptive OCDMA-PON that adaptively shares unused resources of inactive users among active ones to improve upstream system performance. Using the approximated BER expression and defined design problems, two adaptive code allocation algorithms for the adaptive OCDMA-PON are presented and their performances are evaluated by simulation. Simulation results show that the adaptive code allocation algorithms can increase average transmission rate or decrease average optical power consumption of ONUs for dynamic traffic patterns. According to the simulation results, for an adaptive OCDMA-PON with BER value of 1e-7 and user activity probability of 0.5, transmission rate (optical power consumption) can be increased (decreased) by a factor of 2.25 (0.27) compared to fixed code assignment.
Spectrum-Convertible BVWXC Placement in OFDM-based Elastic Optical Networks
Venue: arXiv cs.IT 2016
Year: 2016

Spectrum conversion can improve the performance of OFDM-based Elastic Optical Networks (EONs) by relaxing the continuity constraint and consequently reducing connection request blocking probability during Routing and Spectrum Assignment (RSA) process. We propose three different architectures for including spectrum conversion capability in Bandwidth-Variable Wavelength Cross-Connects (BVWXCs). To compare the capability of the introduced architectures, we develop an analytical method for computing average connection request blocking probability in a spectrum-convertible OFDM-based EON in which all, part or none of the BVWXCs can convert the spectrum. An algorithm for distributing a limited number of Spectrum-Convertible Bandwidth-Variable Wavelength Cross-Connects (SCBVWXCs) in an OFDM-based EON is also proposed. Finally, we use simulation results to evaluate the accuracy of the proposed method for calculating connection request blocking probability and the capability of the introduced algorithm for SCBVWXC placement.
Discovering, quantifying, and displaying attacks
Venue: arXiv cs.CR 2016
Year: 2016

In the design of software and cyber-physical systems, security is often perceived as a qualitative need, but can only be attained quantitatively. Especially when distributed components are involved, it is hard to predict and confront all possible attacks. A main challenge in the development of complex systems is therefore to discover attacks, quantify them to comprehend their likelihood, and communicate them to non-experts for facilitating the decision process. To address this three-sided challenge we propose a protection analysis over the Quality Calculus that (i) computes all the sets of data required by an attacker to reach a given location in a system, (ii) determines the cheapest set of such attacks for a given notion of cost, and (iii) derives an attack tree that displays the attacks graphically. The protection analysis is first developed in a qualitative setting, and then extended to quantitative settings following an approach applicable to a great many contexts. The quantitative formulation is implemented as an optimisation problem encoded into Satisfiability Modulo Theories, allowing us to deal with complex cost structures. The usefulness of the framework is demonstrated on a national-scale authentication system, studied through a Java implementation of the framework.
Machine Learning in Falls Prediction; A cognition-based predictor of falls for the acute neurological in-patient population
Venue: arXiv cs.CY 2016
Year: 2016

Background Information: Falls are associated with high direct and indirect costs, and significant morbidity and mortality for patients. Pathological falls are usually a result of a compromised motor system, and/or cognition. Very little research has been conducted on predicting falls based on this premise. Aims: To demonstrate that cognitive and motor tests can be used to create a robust predictive tool for falls. Methods: Three tests of attention and executive function (Stroop, Trail Making, and Semantic Fluency), a measure of physical function (Walk-12), a series of questions (concerning recent falls, surgery and physical function) and demographic information were collected from a cohort of 323 patients at a tertiary neurological center. The principal outcome was a fall during the in-patient stay (n = 54). Data-driven, predictive modelling was employed to identify the statistical modelling strategies which are most accurate in predicting falls, and which yield the most parsimonious models of clinical relevance. Results: The Trail test was identified as the best predictor of falls. Moreover, addition of any others variables, to the results of the Trail test did not improve the prediction (Wilcoxon signed-rank p < .001). The best statistical strategy for predicting falls was the random forest (Wilcoxon signed-rank p < .001), based solely on results of the Trail test. Tuning of the model results in the following optimized values: 68% (+- 7.7) sensitivity, 90% (+- 2.3) specificity, with a positive predictive value of 60%, when the relevant data is available. Conclusion: Predictive modelling has identified a simple yet powerful machine learning prediction strategy based on a single clinical test, the Trail test. Predictive evaluation shows this strategy to be robust, suggesting predictive modelling and machine learning as the standard for future predictive tools.
Non-Fragility and Partial Controllability of Multi-Agent Systems
Venue: arXiv cs.SY 2016
Year: 2016

Controllability of multi-agent systems is determined by the interconnection topologies. In practice, losing agents can change the topologies of multi-agent systems, which may affect the controllability. This paper studies non-fragility of controllability influenced by losing agents. In virtue of the concept of cutsets, necessary and sufficient conditions are established from a graphic perspective, for strong non-fragility and weak non-fragility of controllability, respectively. For multi-agent systems which contain important agents, partial controllability is proposed in terms of the concept of controllable node groups, and necessary and sufficient criteria are established for partial controllability. Moreover, partial controllability preserving problem is proposed. Utilizing the concept of compressed graphs, this problem is transformed into finding the the minimal $\mathbf{\langle s,t\rangle}$ vertex cutsets of the interconnection graph, which has a polynomial-time complexity algorithm for the solution. Several constructive examples illuminate the theoretical results.
Approximate Policy Iteration for Budgeted Semantic Video Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

This paper formulates and presents a solution to the new problem of budgeted semantic video segmentation. Given a video, the goal is to accurately assign a semantic class label to every pixel in the video within a specified time budget. Typical approaches to such labeling problems, such as Conditional Random Fields (CRFs), focus on maximizing accuracy but do not provide a principled method for satisfying a time budget. For video data, the time required by CRF and related methods is often dominated by the time to compute low-level descriptors of supervoxels across the video. Our key contribution is the new budgeted inference framework for CRF models that intelligently selects the most useful subsets of descriptors to run on subsets of supervoxels within the time budget. The objective is to maintain an accuracy as close as possible to the CRF model with no time bound, while remaining within the time budget. Our second contribution is the algorithm for learning a policy for the sparse selection of supervoxels and their descriptors for budgeted CRF inference. This learning algorithm is derived by casting our problem in the framework of Markov Decision Processes, and then instantiating a state-of-the-art policy learning algorithm known as Classification-Based Approximate Policy Iteration. Our experiments on multiple video datasets show that our learning approach and framework is able to significantly reduce computation time, and maintain competitive accuracy under varying budgets.
Error-Resilient Machine Learning in Near Threshold Voltage via Classifier Ensemble
Venue: arXiv cs.LG 2016
Year: 2016

In this paper, we present the design of error-resilient machine learning architectures by employing a distributed machine learning framework referred to as classifier ensemble (CE). CE combines several simple classifiers to obtain a strong one. In contrast, centralized machine learning employs a single complex block. We compare the random forest (RF) and the support vector machine (SVM), which are representative techniques from the CE and centralized frameworks, respectively. Employing the dataset from UCI machine learning repository and architectural-level error models in a commercial 45 nm CMOS process, it is demonstrated that RF-based architectures are significantly more robust than SVM architectures in presence of timing errors due to process variations in near-threshold voltage (NTV) regions (0.3 V - 0.7 V). In particular, the RF architecture exhibits a detection accuracy (P_{det}) that varies by 3.2% while maintaining a median P_{det} > 0.9 at a gate level delay variation of 28.9% . In comparison, SVM exhibits a P_{det} that varies by 16.8%. Additionally, we propose an error weighted voting technique that incorporates the timing error statistics of the NTV circuit fabric to further enhance robustness. Simulation results confirm that the error weighted voting achieves a P_{det} that varies by only 1.4%, which is 12X lower compared to SVM.
Computing the k Nearest-Neighbors for all Vertices via Dijkstra
Venue: arXiv cs.DS 2016
Year: 2016

We are given a directed graph $G = (V,E)$ with $n$ vertices and $m$ edges, with positive weights on the edges, and a parameter $k >0$. We show how to compute, for every vertex $v \in V$, its $k$ nearest-neighbors. The algorithm runs in $O( k ( n \log n + m ) )$ time, and follows by a somewhat careful modification of Dijkstra's shortest path algorithm. This result is probably folklore, but we were unable to find a reference to it -- thus, this note.
Exploiting Workload Cycles for Orchestration of Virtual Machine Live Migrations in Clouds
Venue: arXiv cs.DC 2016
Year: 2016

Virtual machine live migration in cloud environments aims at reducing energy costs and increasing resource utilization. However, its potential has not been fully explored because of simultaneous migrations that may cause user application performance degradation and network congestion. Research efforts on live migration orchestration policies still mostly rely on system level metrics. This work introduces an Application-aware Live Migration Architecture (ALMA) that selects suitable moments for migrations using application characterization data. This characterization consists in recognizing resource usage cycles via Fast Fourier Transform. From our experiments, live migration times were reduced by up to 74% for benchmarks and by up to 67% for real applications, when compared to migration policies with no application workload analysis. Network data transfer during the live migration was reduced by up to 62%.
Technical Report: Giving Hints for Logic Programming Examples without Revealing Solutions
Venue: arXiv cs.AI 2016
Year: 2016

We introduce a framework for supporting learning to program in the paradigm of Answer Set Programming (ASP), which is a declarative logic programming formalism. Based on the idea of teaching by asking the student to complete small example ASP programs, we introduce a three-stage method for giving hints to the student without revealing the correct solution of an example. We categorize mistakes into (i) syntactic mistakes, (ii) unexpected but syntactically correct input, and (iii) semantic mistakes, describe mathematical definitions of these mistakes, and show how to compute hints from these definitions.
PIWD: A Plugin-based Framework for Well-Designed SPARQL
Venue: arXiv cs.DB 2016
Year: 2016

In the real world datasets (e.g.,DBpedia query log), queries built on well-designed patterns containing only AND and OPT operators (for short, WDAO-patterns) account for a large proportion among all SPARQL queries. In this paper, we present a plugin-based framework for all SELECT queries built on WDAO-patterns, named PIWD. The framework is based on a parse tree called \emph{well-designed AND-OPT tree} (for short, WDAO-tree) whose leaves are basic graph patterns (BGP) and inner nodes are the OPT operators. We prove that for any WDAO-pattern, its parse tree can be equivalently transformed into a WDAO-tree. Based on the proposed framework, we can employ any query engine to evaluate BGP for evaluating queries built on WDAO-patterns in a convenient way. Theoretically, we can reduce the query evaluation of WDAO-patterns to subgraph homomorphism as well as BGP since the query evaluation of BGP is equivalent to subgraph homomorphism. Finally, our preliminary experiments on gStore and RDF-3X show that PIWD can answer all queries built on WDAO-patterns effectively and efficiently.
System-level Scalable Checkpoint-Restart for Petascale Computing
Venue: arXiv cs.DC 2016
Year: 2016

Fault tolerance for the upcoming exascale generation has long been an area of active research. One of the components of a fault tolerance strategy is checkpointing. Petascale-level checkpointing is demonstrated through a new mechanism for virtualization of the InfiniBand UD (unreliable datagram) mode, and for updating the remote address on each UD-based send, due to lack of a fixed peer. Note that InfiniBand UD is required to support modern MPI implementations. An extrapolation from the current results to future SSD-based storage systems provides evidence that the current approach will remain practical in the exascale generation. This transparent checkpointing approach is evaluated using a framework of the DMTCP checkpointing package. Results are shown for HPCG (linear algebra), NAMD (molecular dynamics), and the NAS NPB benchmarks. In tests up to 32,752 MPI processes on 32,752 CPU cores, checkpointing of a computation with a 38 TB memory footprint in 11 minutes is demonstrated. Runtime overhead is reduced to less than 1%. The approach is also evaluated across three widely used MPI implementations.
Harmonization of conflicting medical opinions using argumentation protocols and textual entailment - a case study on Parkinson disease
Venue: arXiv cs.AI 2016
Year: 2016

Parkinson's disease is the second most common neurodegenerative disease, affecting more than 1.2 million people in Europe. Medications are available for the management of its symptoms, but the exact cause of the disease is unknown and there is currently no cure on the market. To better understand the relations between new findings and current medical knowledge, we need tools able to analyse published medical papers based on natural language processing and tools capable to identify various relationships of new findings with the current medical knowledge. Our work aims to fill the above technological gap. To identify conflicting information in medical documents, we enact textual entailment technology. To encapsulate existing medical knowledge, we rely on ontologies. To connect the formal axioms in ontologies with natural text in medical articles, we exploit ontology verbalisation techniques. To assess the level of disagreement between human agents with respect to a medical issue, we rely on fuzzy aggregation. To harmonize this disagreement, we design mediation protocols within a multi-agent framework.
Read-Tuned STT-RAM and eDRAM Cache Hierarchies for Throughput and Energy Enhancement
Venue: arXiv cs.AR 2016
Year: 2016

As capacity and complexity of on-chip cache memory hierarchy increases, the service cost to the critical loads from Last Level Cache (LLC), which are frequently repeated, has become a major concern. The processor may stall for a considerable interval while waiting to access the data stored in the cache blocks in LLC, if there are no independent instructions to execute. To provide accelerated service to the critical loads requests from LLC, this work concentrates on leveraging the additional capacity offered by replacing SRAM-based L2 with Spin-Transfer Torque Random Access Memory (STT-RAM) to accommodate frequently accessed cache blocks in exclusive read mode in favor of reducing the overall read service time. Our proposed technique partitions L2 cache into two STT-RAM arrangements with different write performance and data retention time. The retention-relaxed STT-RAM arrays are utilized to effectively deal with the regular L2 cache requests while the high retention STT-RAM arrays in L2 are selected for maintaining repeatedly read accessed cache blocks from LLC by incurring negligible energy consumption for data retention. Our experimental results show that the proposed technique can reduce the mean L2 read miss ratio by 51.4% and increase the IPC by 11.7% on average across PARSEC benchmark suite while significantly decreasing the total L2 energy consumption compared to conventional SRAM-based L2 design.