OpenRaiser/Intern-Atlas huggingface dataset:
The swept rule for breaking the latency barrier in time advancing PDEs
Venue: arXiv cs.CE 2015
Year: 2015

This article investigates the swept rule of space-time domain decomposition, an idea to break the latency barrier via communicating less often when explicitly solving time-dependent PDEs. The swept rule decomposes space and time among computing nodes in ways that exploit the domains of influence and the domain of dependency, making it possible to communicate once per many timesteps without redundant computation. The article presents simple theoretical analysis to the performance of the swept rule which then was shown to be accurate by conducting numerical experiments.
Understanding Soft Errors in Uncore Components
Venue: arXiv cs.OH 2015
Year: 2015

The effects of soft errors in processor cores have been widely studied. However, little has been published about soft errors in uncore components, such as memory subsystem and I/O controllers, of a System-on-a-Chip (SoC). In this work, we study how soft errors in uncore components affect system-level behaviors. We have created a new mixed-mode simulation platform that combines simulators at two different levels of abstraction, and achieves 20,000x speedup over RTL-only simulation. Using this platform, we present the first study of the system-level impact of soft errors inside various uncore components of a large-scale, multi-core SoC using the industrial-grade, open-source OpenSPARC T2 SoC design. Our results show that soft errors in uncore components can significantly impact system-level reliability. We also demonstrate that uncore soft errors can create major challenges for traditional system-level checkpoint recovery techniques. To overcome such recovery challenges, we present a new replay recovery technique for uncore components belonging to the memory subsystem. For the L2 cache controller and the DRAM controller components of OpenSPARC T2, our new technique reduces the probability that an application run fails to produce correct results due to soft errors by more than 100x with 3.32% and 6.09% chip-level area and power impact, respectively.
A Metric to Classify Style of Spoken Speech
Venue: arXiv cs.CL 2015
Year: 2015

The ability to classify spoken speech based on the style of speaking is an important problem. With the advent of BPO's in recent times, specifically those that cater to a population other than the local population, it has become necessary for BPO's to identify people with certain style of speaking (American, British etc). Today BPO's employ accent analysts to identify people having the required style of speaking. This process while involving human bias, it is becoming increasingly infeasible because of the high attrition rate in the BPO industry. In this paper, we propose a new metric, which robustly and accurately helps classify spoken speech based on the style of speaking. The role of the proposed metric is substantiated by using it to classify real speech data collected from over seventy different people working in a BPO. We compare the performance of the metric against human experts who independently carried out the classification process. Experimental results show that the performance of the system using the novel metric performs better than two different human expert.
If the Current Clique Algorithms are Optimal, so is Valiant's Parser
Venue: arXiv cs.CC 2015
Year: 2015

The CFG recognition problem is: given a context-free grammar $\mathcal{G}$ and a string $w$ of length $n$, decide if $w$ can be obtained from $\mathcal{G}$. This is the most basic parsing question and is a core computer science problem. Valiant's parser from 1975 solves the problem in $O(n^ω)$ time, where $ω<2.373$ is the matrix multiplication exponent. Dozens of parsing algorithms have been proposed over the years, yet Valiant's upper bound remains unbeaten. The best combinatorial algorithms have mildly subcubic $O(n^3/\log^3{n})$ complexity. Lee (JACM'01) provided evidence that fast matrix multiplication is needed for CFG parsing, and that very efficient and practical algorithms might be hard or even impossible to obtain. Lee showed that any algorithm for a more general parsing problem with running time $O(|\mathcal{G}|\cdot n^{3-\varepsilon})$ can be converted into a surprising subcubic algorithm for Boolean Matrix Multiplication. Unfortunately, Lee's hardness result required that the grammar size be $|\mathcal{G}|=Ω(n^6)$. Nothing was known for the more relevant case of constant size grammars. In this work, we prove that any improvement on Valiant's algorithm, even for constant size grammars, either in terms of runtime or by avoiding the inefficiencies of fast matrix multiplication, would imply a breakthrough algorithm for the $k$-Clique problem: given a graph on $n$ nodes, decide if there are $k$ that form a clique. Besides classifying the complexity of a fundamental problem, our reduction has led us to similar lower bounds for more modern and well-studied cubic time problems for which faster algorithms are highly desirable in practice: RNA Folding, a central problem in computational biology, and Dyck Language Edit Distance, answering an open question of Saha (FOCS'14).
Local Measurement and Reconstruction for Noisy Graph Signals
Venue: arXiv cs.IT 2015
Year: 2015

The emerging field of signal processing on graph plays a more and more important role in processing signals and information related to networks. Existing works have shown that under certain conditions a smooth graph signal can be uniquely reconstructed from its decimation, i.e., data associated with a subset of vertices. However, in some potential applications (e.g., sensor networks with clustering structure), the obtained data may be a combination of signals associated with several vertices, rather than the decimation. In this paper, we propose a new concept of local measurement, which is a generalization of decimation. Using the local measurements, a local-set-based method named iterative local measurement reconstruction (ILMR) is proposed to reconstruct bandlimited graph signals. It is proved that ILMR can reconstruct the original signal perfectly under certain conditions. The performance of ILMR against noise is theoretically analyzed. The optimal choice of local weights and a greedy algorithm of local set partition are given in the sense of minimizing the expected reconstruction error. Compared with decimation, the proposed local measurement sampling and reconstruction scheme is more robust in noise existing scenarios.
Tight Size-Degree Bounds for Sums-of-Squares Proofs
Venue: arXiv cs.CC 2015
Year: 2015

We exhibit families of $4$-CNF formulas over $n$ variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) $d$ but require SOS proofs of size $n^{Ω(d)}$ for values of $d = d(n)$ from constant all the way up to $n^δ$ for some universal constant$δ$. This shows that the $n^{O(d)}$ running time obtained by using the Lasserre semidefinite programming relaxations to find degree-$d$ SOS proofs is optimal up to constant factors in the exponent. We establish this result by combining $\mathsf{NP}$-reductions expressible as low-degree SOS derivations with the idea of relativizing CNF formulas in [Krajíček '04] and [Dantchev and Riis'03], and then applying a restriction argument as in [Atserias, Müller, and Oliva '13] and [Atserias, Lauria, and Nordström '14]. This yields a generic method of amplifying SOS degree lower bounds to size lower bounds, and also generalizes the approach in [ALN14] to obtain size lower bounds for the proof systems resolution, polynomial calculus, and Sherali-Adams from lower bounds on width, degree, and rank, respectively.
Does Gaming Help Improve Cognitive Skills?
Venue: arXiv cs.CY 2015
Year: 2015

A nationally representative study of video game play among adolescents in the United States showed that 97% of adolescents aged 12 to 17 years play computer, web, and portable (or console) video games (Lenhart et al., 2008). We hypothesized that if people play games as a regular exercise regime, gaming will correlate with an improvement in their cognitive skills. For this experiment, a few games that tested the logical reasoning and critical analysis skills under a given time constraint were coded in Python using Pygame and were played by a group of 7th grade students. In order to test whether there is a relationship between gaming and test performance, we divided the students into two groups and gave them tests before and after the experimentation period in order to measure their improvement. One group played the games while the other did not. In the group of students that played the games, an average improvement of 62.19% was seen (p < 0.0001). The group that did not play the games only improved their performance by an average of 18.51% (p = 0.0882).
Jointly Embedding Relations and Mentions for Knowledge Population
Venue: arXiv cs.CL 2015
Year: 2015

This paper contributes a joint embedding model for predicting relations between a pair of entities in the scenario of relation inference. It differs from most stand-alone approaches which separately operate on either knowledge bases or free texts. The proposed model simultaneously learns low-dimensional vector representations for both triplets in knowledge repositories and the mentions of relations in free texts, so that we can leverage the evidence both resources to make more accurate predictions. We use NELL to evaluate the performance of our approach, compared with cutting-edge methods. Results of extensive experiments show that our model achieves significant improvement on relation extraction.
Large Margin Nearest Neighbor Embedding for Knowledge Representation
Venue: arXiv cs.AI 2015
Year: 2015

Traditional way of storing facts in triplets ({\it head\_entity, relation, tail\_entity}), abbreviated as ({\it h, r, t}), makes the knowledge intuitively displayed and easily acquired by mankind, but hardly computed or even reasoned by AI machines. Inspired by the success in applying {\it Distributed Representations} to AI-related fields, recent studies expect to represent each entity and relation with a unique low-dimensional embedding, which is different from the symbolic and atomic framework of displaying knowledge in triplets. In this way, the knowledge computing and reasoning can be essentially facilitated by means of a simple {\it vector calculation}, i.e. ${\bf h} + {\bf r} \approx {\bf t}$. We thus contribute an effective model to learn better embeddings satisfying the formula by pulling the positive tail entities ${\bf t^{+}}$ to get together and close to {\bf h} + {\bf r} ({\it Nearest Neighbor}), and simultaneously pushing the negatives ${\bf t^{-}}$ away from the positives ${\bf t^{+}}$ via keeping a {\it Large Margin}. We also design a corresponding learning algorithm to efficiently find the optimal solution based on {\it Stochastic Gradient Descent} in iterative fashion. Quantitative experiments illustrate that our approach can achieve the state-of-the-art performance, compared with several latest methods on some benchmark datasets for two classical applications, i.e. {\it Link prediction} and {\it Triplet classification}. Moreover, we analyze the parameter complexities among all the evaluated models, and analytical results indicate that our model needs fewer computational resources on outperforming the other methods.
User Effort and Network Structure Mediate Access to Information in Networks
Venue: arXiv cs.SI 2015
Year: 2015

Individuals' access to information in a social network depends on its distributed and where in the network individuals position themselves. However, individuals have limited capacity to manage their social connections and process information. In this work, we study how this limited capacity and network structure interact to affect the diversity of information social media users receive. Previous studies of the role of networks in information access were limited in their ability to measure the diversity of information. We address this problem by learning the topics of interest to social media users by observing messages they share online with their followers. We present a probabilistic model that incorporates human cognitive constraints in a generative model of information sharing. We then use the topics learned by the model to measure the diversity of information users receive from their social media contacts. We confirm that users in structurally diverse network positions, which bridge otherwise disconnected regions of the follower graph, are exposed to more diverse information. In addition, we identify user effort as an important variable that mediates access to diverse information in social media. Users who invest more effort into their activity on the site not only place themselves in more structurally diverse positions within the network than the less engaged users, but they also receive more diverse information when located in similar network positions. These findings indicate that the relationship between network structure and access to information in networks is more nuanced than previously thought.
Social media in scholarly communication
Venue: arXiv cs.DL 2015
Year: 2015

Social media metrics - commonly coined as "altmetrics" - have been heralded as great democratizers of science, providing broader and timelier indicators of impact than citations. These metrics come from a range of sources, including Twitter, blogs, social reference managers, post-publication peer review, and other social media platforms. Social media metrics have begun to be used as indicators of scientific impact, yet the theoretical foundation, empirical validity, and extent of use of platforms underlying these metrics lack thorough treatment in the literature. This editorial provides an overview of terminology and definitions of altmetrics and summarizes current research regarding social media use in academia, social media metrics as well as data reliability and validity. The papers of the special issue are introduced.
Evaluating Two-Stream CNN for Video Classification
Venue: arXiv cs.CV 2015
Year: 2015

Videos contain very rich semantic information. Traditional hand-crafted features are known to be inadequate in analyzing complex video semantics. Inspired by the huge success of the deep learning methods in analyzing image, audio and text data, significant efforts are recently being devoted to the design of deep nets for video analytics. Among the many practical needs, classifying videos (or video clips) based on their major semantic categories (e.g., "skiing") is useful in many applications. In this paper, we conduct an in-depth study to investigate important implementation options that may affect the performance of deep nets on video classification. Our evaluations are conducted on top of a recent two-stream convolutional neural network (CNN) pipeline, which uses both static frames and motion optical flows, and has demonstrated competitive performance against the state-of-the-art methods. In order to gain insights and to arrive at a practical guideline, many important options are studied, including network architectures, model fusion, learning parameters and the final prediction methods. Based on the evaluations, very competitive results are attained on two popular video classification benchmarks. We hope that the discussions and conclusions from this work can help researchers in related fields to quickly set up a good basis for further investigations along this very promising direction.
Solving the Closest Vector Problem in $2^n$ Time--- The Discrete Gaussian Strikes Again!
Venue: arXiv cs.DS 2015
Year: 2015

We give a $2^{n+o(n)}$-time and space randomized algorithm for solving the exact Closest Vector Problem (CVP) on $n$-dimensional Euclidean lattices. This improves on the previous fastest algorithm, the deterministic $\widetilde{O}(4^{n})$-time and $\widetilde{O}(2^{n})$-space algorithm of Micciancio and Voulgaris. We achieve our main result in three steps. First, we show how to modify the sampling algorithm from [ADRS15] to solve the problem of discrete Gaussian sampling over lattice shifts, $L- t$, with very low parameters. While the actual algorithm is a natural generalization of [ADRS15], the analysis uses substantial new ideas. This yields a $2^{n+o(n)}$-time algorithm for approximate CVP for any approximation factor $γ= 1+2^{-o(n/\log n)}$. Second, we show that the approximate closest vectors to a target vector $t$ can be grouped into "lower-dimensional clusters," and we use this to obtain a recursive reduction from exact CVP to a variant of approximate CVP that "behaves well with these clusters." Third, we show that our discrete Gaussian sampling algorithm can be used to solve this variant of approximate CVP. The analysis depends crucially on some new properties of the discrete Gaussian distribution and approximate closest vectors, which might be of independent interest.
An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles
Venue: arXiv cs.DS 2015
Year: 2015

The Lovasz Local Lemma is a seminal result in probabilistic combinatorics. It gives a sufficient condition on a probability space and a collection of events for the existence of an outcome that simultaneously avoids all of those events. Finding such an outcome by an efficient algorithm has been an active research topic for decades. Breakthrough work of Moser and Tardos (2009) presented an efficient algorithm for a general setting primarily characterized by a product structure on the probability space. In this work we present an efficient algorithm for a much more general setting. Our main assumption is that there exist certain functions, called resampling oracles, that can be invoked to address the undesired occurrence of the events. We show that, in all scenarios to which the original Lovasz Local Lemma applies, there exist resampling oracles, although they are not necessarily efficient. Nevertheless, for essentially all known applications of the Lovasz Local Lemma and its generalizations, we have designed efficient resampling oracles. As applications of these techniques, we present new results for packings of Latin transversals, rainbow matchings and rainbow spanning trees.
Revolutionary Hybrid E-Books for Enhanced Higher Learning
Venue: arXiv cs.CY 2015
Year: 2015

Books are the best friends of human beings and make them a rational animal. In this E-world our traditional books are losing their values. Recent surveys are proving that the younger generations are not much interested in visiting libraries and reading books due to their addiction towards the electronic gadgets. Many publishers are now changed their strategy by publishing and promoting ebooks. Academicians are also badly affected by this trend and they are forced to motivate the students to improve their reading habits for their better performance in the institutions and to be responsible citizens of a country. There are many difficulties faced by the ebook readers and it discourages the people to read an ebook for long time like a normal printed book. The main objective of this paper is to introduce a hybrid Ebook which is capable of having audio and video files also in it. This makes the people to read the e-book with modern electronic formats. This multimedia facility makes the people to read or listen or watch the ebooks for long time. We have quoted the survey results which prove that the students prefer to read hybrid books than normal ebooks or the printed handouts in College of Applied Sciences, Oman. Still we feel these books should have few more facilities, so that people who like traditional books will also adopt these ebooks, without losing the satisfaction of reading printed books. These things are listed in the recommendations and conclusion section.
Unwrapping ADMM: Efficient Distributed Computing via Transpose Reduction
Venue: arXiv cs.DC 2015
Year: 2015

Recent approaches to distributed model fitting rely heavily on consensus ADMM, where each node solves small sub-problems using only local data. We propose iterative methods that solve {\em global} sub-problems over an entire distributed dataset. This is possible using transpose reduction strategies that allow a single node to solve least-squares over massive datasets without putting all the data in one place. This results in simple iterative methods that avoid the expensive inner loops required for consensus methods. To demonstrate the efficiency of this approach, we fit linear classifiers and sparse linear models to datasets over 5 Tb in size using a distributed implementation with over 7000 cores in far less time than previous approaches.
Exploring Lexical, Syntactic, and Semantic Features for Chinese Textual Entailment in NTCIR RITE Evaluation Tasks
Venue: arXiv cs.CL 2015
Year: 2015

We computed linguistic information at the lexical, syntactic, and semantic levels for Recognizing Inference in Text (RITE) tasks for both traditional and simplified Chinese in NTCIR-9 and NTCIR-10. Techniques for syntactic parsing, named-entity recognition, and near synonym recognition were employed, and features like counts of common words, statement lengths, negation words, and antonyms were considered to judge the entailment relationships of two statements, while we explored both heuristics-based functions and machine-learning approaches. The reported systems showed robustness by simultaneously achieving second positions in the binary-classification subtasks for both simplified and traditional Chinese in NTCIR-10 RITE-2. We conducted more experiments with the test data of NTCIR-9 RITE, with good results. We also extended our work to search for better configurations of our classifiers and investigated contributions of individual features. This extended work showed interesting results and should encourage further discussion.
Towards SE and EE in 5G with NOMA and Massive MIMO Technologies
Venue: arXiv cs.IT 2015
Year: 2015

Non-Orthogonal Multiple Access (NOMA) has been proposed to enhance the Spectrum Efficiency (SE) and cell-edge capacity. This paper considers the massive Multi-Input Multi-Output (MIMO) with Non-Orthogonal Multiple Access (NOMA) encoding. The close-form expression of capacity of the massive MIMO with NOMA is given here. Apart from the previous Successive Interference Cancellation (SIC) method, the Power Hard Limiter (PHD) is introduced here for better reality implement.
ROPocop - Dynamic Mitigation of Code-Reuse Attacks
Venue: arXiv cs.CR 2015
Year: 2015

Control-flow attacks, usually achieved by exploiting a buffer-overflow vulnerability, have been a serious threat to system security for over fifteen years. Researchers have answered the threat with various mitigation techniques, but nevertheless, new exploits that successfully bypass these technologies still appear on a regular basis. In this paper, we propose ROPocop, a novel approach for detecting and preventing the execution of injected code and for mitigating code-reuse attacks such as return-oriented programming (RoP). ROPocop uses dynamic binary instrumentation, requiring neither access to source code nor debug symbols or changes to the operating system. It mitigates attacks by both monitoring the program counter at potentially dangerous points and by detecting suspicious program flows. We have implemented ROPocop for Windows x86 using PIN, a dynamic program instrumentation framework from Intel. Benchmarks using the SPEC CPU2006 suite show an average overhead of 2.4x, which is comparable to similar approaches, which give weaker guarantees. Real-world applications show only an initially noticeable input lag and no stutter. In our evaluation our tool successfully detected all 11 of the latest real-world code-reuse exploits, with no false alarms. Therefore, despite the overhead, it is a viable, temporary solution to secure critical systems against exploits if a vendor patch is not yet available.