OpenRaiser/Intern-Atlas huggingface dataset:
Nearest Neighbor search in Complex Network for Community Detection
Venue: arXiv cs.SI 2015
Year: 2015

Nearest neighbor search is a basic computational tool used extensively in almost research domains of computer science specially when dealing with large amount of data. However, the use of nearest neighbor search is restricted for the purpose of algorithmic development by the existence of the notion of nearness among the data points. The recent trend of research is on large, complex networks and their structural analysis, where nodes represent entities and edges represent any kind of relation between entities. Community detection in complex network is an important problem of much interest. In general, a community detection algorithm represents an objective function and captures the communities by optimizing it to extract the interesting communities for the user. In this article, we have studied the nearest neighbor search problem in complex network via the development of a suitable notion of nearness. Initially, we have studied and analyzed the exact nearest neighbor search using metric tree on proposed metric space constructed from complex network. After, the approximate nearest neighbor search problem is studied using locality sensitive hashing. For evaluation of the proposed nearest neighbor search on complex network we applied it in community detection problem. The results obtained using our methods are very competitive with most of the well known algorithms exists in the literature and this is verified on collection of real networks. On the other-hand, it can be observed that time taken by our algorithm is quite less compared to popular methods.
Predicting Relevance based on Assessor Disagreement: Analysis and Practical Applications for Search Evaluation
Venue: arXiv cs.IR 2015
Year: 2015

Evaluation of search engines relies on assessments of search results for selected test queries, from which we would ideally like to draw conclusions in terms of relevance of the results for general (e.g., future, unknown) users. In practice however, most evaluation scenarios only allow us to conclusively determine the relevance towards the particular assessor that provided the judgments. A factor that cannot be ignored when extending conclusions made from assessors towards users, is the possible disagreement on relevance, assuming that a single gold truth label does not exist. This paper presents and analyzes the Predicted Relevance Model (PRM), which allows predicting a particular result's relevance for a random user, based on an observed assessment and knowledge on the average disagreement between assessors. With the PRM, existing evaluation metrics designed to measure binary assessor relevance, can be transformed into more robust and effectively graded measures that evaluate relevance towards a random user. It also leads to a principled way of quantifying multiple graded or categorical relevance levels for use as gains in established graded relevance measures, such as normalized discounted cumulative gain (nDCG), which nowadays often use heuristic and data-independent gain values. Given a set of test topics with graded relevance judgments, the PRM allows evaluating systems on different scenarios, such as their capability of retrieving top results, or how well they are able to filter out non-relevant ones. Its use in actual evaluation scenarios is illustrated on several information retrieval test collections.
On the total $(k,r)$-domination number of random graphs
Venue: arXiv cs.DM 2015
Year: 2015

A subset $S$ of a vertex set of a graph $G$ is a total $(k,r)$-dominating set if every vertex $u \in V(G)$ is within distance $k$ of at least $r$ vertices in $S$. The minimum cardinality among all total $(k,r)$-dominating sets of $G$ is called the total $(k,r)$-domination number of $G$, denoted by $γ^{t}_{(k,r)}(G)$. We previously gave an upper bound on $γ^{t}_{(2,r)}(G(n,p))$ in random graphs with non-fixed $p \in (0,1)$. In this paper we generalize this result to give an upper bound on $γ^{t}_{(k,r)}(G(n,p))$ in random graphs with non-fixed $p \in (0,1)$ for $k\geq 3$ as well as present an upper bound on $γ^{t}_{(k,r)}(G)$ in graphs with large girth.
Rendering refraction and reflection of eyeglasses for synthetic eye tracker images
Venue: arXiv cs.CV 2015
Year: 2015

While for the evaluation of robustness of eye tracking algorithms the use of real-world data is essential, there are many applications where simulated, synthetic eye images are of advantage. They can generate labelled ground-truth data for appearance based gaze estimation algorithms or enable the development of model based gaze estimation techniques by showing the influence on gaze estimation error of different model factors that can then be simplified or extended. We extend the generation of synthetic eye images by a simulation of refraction and reflection for eyeglasses. On the one hand this allows for the testing of pupil and glint detection algorithms under different illumination and reflection conditions, on the other hand the error of gaze estimation routines can be estimated in conjunction with different eyeglasses. We show how a polynomial function fitting calibration performs equally well with and without eyeglasses, and how a geometrical eye model behaves when exposed to glasses.
Approximation Algorithms for Route Planning with Nonlinear Objectives
Venue: arXiv cs.DS 2015
Year: 2015

We consider optimal route planning when the objective function is a general nonlinear and non-monotonic function. Such an objective models user behavior more accurately, for example, when a user is risk-averse, or the utility function needs to capture a penalty for early arrival. It is known that as nonlinearity arises, the problem becomes NP-hard and little is known about computing optimal solutions when in addition there is no monotonicity guarantee. We show that an approximately optimal non-simple path can be efficiently computed under some natural constraints. In particular, we provide a fully polynomial approximation scheme under hop constraints. Our approximation algorithm can extend to run in pseudo-polynomial time under a more general linear constraint that sometimes is useful. As a by-product, we show that our algorithm can be applied to the problem of finding a path that is most likely to be on time for a given deadline.
Parity Separation: A Scientifically Proven Method for Permanent Weight Loss
Venue: arXiv cs.CC 2015
Year: 2015

Given an edge-weighted graph G, let PerfMatch(G) denote the weighted sum over all perfect matchings M in G, weighting each matching M by the product of weights of edges in M. If G is unweighted, this plainly counts the perfect matchings of G. In this paper, we introduce parity separation, a new method for reducing PerfMatch to unweighted instances: For graphs G with edge-weights -1 and 1, we construct two unweighted graphs G1 and G2 such that PerfMatch(G) = PerfMatch(G1) - PerfMatch(G2). This yields a novel weight removal technique for counting perfect matchings, in addition to those known from classical #P-hardness proofs. We derive the following applications: 1. An alternative #P-completeness proof for counting unweighted perfect matchings. 2. C=P-completeness for deciding whether two given unweighted graphs have the same number of perfect matchings. To the best of our knowledge, this is the first C=P-completeness result for the "equality-testing version" of any natural counting problem that is not already #P-hard under parsimonious reductions. 3. An alternative tight lower bound for counting unweighted perfect matchings under the counting exponential-time hypothesis #ETH. Our technique is based upon matchgates and the Holant framework. To make our #P-hardness proof self-contained, we also apply matchgates for an alternative #P-hardness proof of PerfMatch on graphs with edge-weights -1 and 1.
Decoding Reed-Muller codes over product sets
Venue: arXiv cs.CC 2015
Year: 2015

We give a polynomial time algorithm to decode multivariate polynomial codes of degree $d$ up to half their minimum distance, when the evaluation points are an arbitrary product set $S^m$, for every $d < |S|$. Previously known algorithms can achieve this only if the set $S$ has some very special algebraic structure, or if the degree $d$ is significantly smaller than $|S|$. We also give a near-linear time randomized algorithm, which is based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided $d < (1-ε)|S|$ for constant $ε> 0$. Our result gives an $m$-dimensional generalization of the well known decoding algorithms for Reed-Solomon codes, and can be viewed as giving an algorithmic version of the Schwartz-Zippel lemma.
On the Computational Complexity of Limit Cycles in Dynamical Systems
Venue: arXiv cs.CC 2015
Year: 2015

We study the Poincare-Bendixson theorem for two-dimensional continuous dynamical systems in compact domains from the point of view of computation, seeking algorithms for finding the limit cycle promised by this classical result. We start by considering a discrete analogue of this theorem and show that both finding a point on a limit cycle, and determining if a given point is on one, are PSPACE-complete. For the continuous version, we show that both problems are uncomputable in the real complexity sense; i.e., their complexity is arbitrarily high. Subsequently, we introduce a notion of an "approximate cycle" and prove an "approximate" Poincaré-Bendixson theorem guaranteeing that some orbits come very close to forming a cycle in the absence of approximate fixpoints; surprisingly, it holds for all dimensions. The corresponding computational problem defined in terms of arithmetic circuits is PSPACE-complete.
Exploiting Environmental Computation in a Multi-Agent Model of Slime Mould
Venue: arXiv cs.ET 2015
Year: 2015

Very simple organisms, such as the single-celled amoeboid slime mould Physarum polycephalum possess no neural tissue yet, despite this, are known to exhibit complex biological and computational behaviour. Given such limited resources, can environmental stimuli play a role in generating the complexity of slime mould behaviour? We use a multi-agent collective model of slime mould to explore a two-way mechanism where the collective behaviour is influenced by simulated chemical concentration gradient fields and, in turn, this behaviour alters the spatial pattern of the concentration gradients. This simple mechanism yields complex behaviour amid the dynamically changing gradient profiles and suggests how the apparently intelligent response of the slime mould could possibly be due to outsourcing of computation to the environment.
A Note on Fault Tolerant Reachability for Directed Graphs
Venue: arXiv cs.DS 2015
Year: 2015

In this note we describe an application of low-high orders in fault-tolerant network design. Baswana et al. [DISC 2015] study the following reachability problem. We are given a flow graph $G = (V, A)$ with start vertex $s$, and a spanning tree $T =(V, A_T)$ rooted at $s$. We call a set of arcs $A'$ valid if the subgraph $G' = (V, A_T \cup A')$ of $G$ has the same dominators as $G$. The goal is to find a valid set of minimum size. Baswana et al. gave an $O(m \log{n})$-time algorithm to compute a minimum-size valid set in $O(m \log{n})$ time, where $n = |V|$ and $m = |A|$. Here we provide a simple $O(m)$-time algorithm that uses the dominator tree $D$ of $G$ and a low-high order of it.
Two Countermeasures Against Hardware Trojans Exploiting Non-Zero Aliasing Probability of BIST
Venue: arXiv cs.CR 2015
Year: 2015

The threat of hardware Trojans has been widely recognized by academia, industry, and government agencies. A Trojan can compromise security of a system in spite of cryptographic protection. The damage caused by a Trojan may not be limited to a business or reputation, but could have a severe impact on public safety, national economy, or national security. An extremely stealthy way of implementing hardware Trojans has been presented by Becker et al. at CHES'2012. Their work have shown that it is possible to inject a Trojan in a random number generator compliant with FIPS 140-2 and NIST SP800-90 standards by exploiting non-zero aliasing probability of Logic Built-In-Self-Test (LBIST). In this paper, we present two methods for modifying LBIST to prevent such an attack. The first method makes test patterns dependent on a configurable key which is programed into a chip after the manufacturing stage. The second method uses a remote test management system which can execute LBIST using a different set of test patterns at each test cycle.
Multipartite entangled states, symmetric matrices and error-correcting codes
Venue: arXiv cs.IT 2015
Year: 2015

A pure quantum state is called $k$-uniform if all its reductions to $k$-qudit are maximally mixed. We investigate the general constructions of $k$-uniform pure quantum states of $n$ subsystems with $d$ levels. We provide one construction via symmetric matrices and the second one through classical error-correcting codes. There are three main results arising from our constructions. Firstly, we show that for any given even $n\ge 2$, there always exists an $n/2$-uniform $n$-qudit quantum state of level $p$ for sufficiently large prime $p$. Secondly, both constructions show that their exist $k$-uniform $n$-qudit pure quantum states such that $k$ is proportional to $n$, i.e., $k=Ω(n)$ although the construction from symmetric matrices outperforms the one by error-correcting codes. Thirdly, our symmetric matrix construction provides a positive answer to the open question in \cite{DA} on whether there exists $3$-uniform $n$-qudit pure quantum state for all $n\ge 8$. In fact, we can further prove that, for every $k$, there exists a constant $M_k$ such that there exists a $k$-uniform $n$-qudit quantum state for all $n\ge M_k$. In addition, by using concatenation of algebraic geometry codes, we give an explicit construction of $k$-uniform quantum state when $k$ tends to infinity.
Learning to detect video events from zero or very few video examples
Venue: arXiv cs.LG 2015
Year: 2015

In this work we deal with the problem of high-level event detection in video. Specifically, we study the challenging problems of i) learning to detect video events from solely a textual description of the event, without using any positive video examples, and ii) additionally exploiting very few positive training samples together with a small number of ``related'' videos. For learning only from an event's textual description, we first identify a general learning framework and then study the impact of different design choices for various stages of this framework. For additionally learning from example videos, when true positive training samples are scarce, we employ an extension of the Support Vector Machine that allows us to exploit ``related'' event videos by automatically introducing different weights for subsets of the videos in the overall training set. Experimental evaluations performed on the large-scale TRECVID MED 2014 video dataset provide insight on the effectiveness of the proposed methods.
SlicerPET: A workflow based software module for PET/CT guided needle biopsy
Venue: arXiv cs.GR 2015
Year: 2015

Biopsy is commonly used to confirm cancer diagnosis when radiologically indicated. Given the ability of PET to localize malignancies in heterogeneous tumors and tumors that do not have a CT correlate, PET/CT guided biopsy may improve the diagnostic yield of biopsies. To facilitate PET/CT guided needle biopsy, we developed a workflow that allows us to bring PET image guidance into the interventional CT suite. In this abstract, we present SlicerPET, a user-friendly workflow based module developed using open source software libraries to guide needle biopsy in the interventional suite.
On Throughput-Smoothness Trade-offs in Streaming Communication
Venue: arXiv cs.IT 2015
Year: 2015

Unlike traditional file transfer where only total delay matters, streaming applications impose delay constraints on each packet and require them to be in order. To achieve fast in-order packet decoding, we have to compromise on the throughput. We study this trade-off between throughput and smoothness in packet decoding. We first consider a point-to-point streaming and analyze how the trade-off is affected by the frequency of block-wise feedback, whereby the source receives full channel state feedback at periodic intervals. We show that frequent feedback can drastically improve the throughput-smoothness trade-off. Then we consider the problem of multicasting a packet stream to two users. For both point-to-point and multicast streaming, we propose a spectrum of coding schemes that span different throughput-smoothness tradeoffs. One can choose an appropriate coding scheme from these, depending upon the delay-sensitivity and bandwidth limitations of the application. This work introduces a novel style of analysis using renewal processes and Markov chains to analyze coding schemes.
A declarative extension of parsing expression grammars for recognizing most programming languages
Venue: arXiv cs.PL 2015
Year: 2015

Parsing Expression Grammars are a popular foundation for describing syntax. Unfortunately, several syntax of programming languages are still hard to recognize with pure PEGs. Notorious cases appears: typedef-defined names in C/C++, indentation-based code layout in Python, and HERE document in many scripting languages. To recognize such PEG-hard syntax, we have addressed a declarative extension to PEGs. The "declarative" extension means no programmed semantic actions, which are traditionally used to realize the extended parsing behavior. Nez is our extended PEG language, including symbol tables and conditional parsing. This paper demonstrates that the use of Nez Extensions can realize many practical programming languages, such as C, C\#, Ruby, and Python, which involve PEG-hard syntax.
Simple one-shot bounds for various source coding problems using smooth Renyi quantities
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of source compression under three different scenarios in the one-shot (non- asymptotic) regime. To be specific, we prove one-shot achievability and converse bounds on the coding rates for distributed source coding, source coding with coded side information available at the decoder and source coding under maximum distortion criterion. The one-shot bounds obtained are in terms of smooth max Renyi entropy and smooth max Renyi divergence. Our results are powerful enough to yield the results that are known for these problems in the asymptotic regime both in the i.i.d. (independent and identically distributed) and non-i.i.d. settings
A Cooperative Scheduling Scheme of Local Cloud and Internet Cloud for Delay-Aware Mobile Cloud Computing
Venue: arXiv cs.NI 2015
Year: 2015

With the proliferation of mobile applications, Mobile Cloud Computing (MCC) has been proposed to help mobile devices save energy and improve computation performance. To further improve the quality of service (QoS) of MCC, cloud servers can be deployed locally so that the latency is decreased. However, the computational resource of the local cloud is generally limited. In this paper, we design a threshold-based policy to improve the QoS of MCC by cooperation of the local cloud and Internet cloud resources, which takes the advantages of low latency of the local cloud and abundant computational resources of the Internet cloud simultaneously. This policy also applies a priority queue in terms of delay requirements of applications. The optimal thresholds depending on the traffic load is obtained via a proposed algorithm. Numerical results show that the QoS can be greatly enhanced with the assistance of Internet cloud when the local cloud is overloaded. Better QoS is achieved if the local cloud order tasks according to their delay requirements, where delay-sensitive applications are executed ahead of delay-tolerant applications. Moreover, the optimal thresholds of the policy have a sound impact on the QoS of the system.
Self-Healing Audio System
Venue: arXiv cs.NI 2015
Year: 2015

Installed sound applications typically involve a large number of audio processors, amplifiers and speaker systems spread across the venue. They could be spatially distributed at the venue across different rack rooms and floors. These systems are commissioned and configured by sound engineers using software application(s). This is essentially a one-time activity, following which, the audio systems run independently. Detection of faults and reconfiguration of any audio device(s) that fail(s) is a time-consuming operation. This disruption in the audio system can affect the entire audio chain and affect the usability of the venue in question. In this paper, we provide an overview of an audio system that detects the replacement for any faulty audio device(s) in the network and re-purposes the same to restore the configuration to last working point.
HPA: An Opportunistic Approach to Embedded Energy Efficiency
Venue: arXiv cs.PF 2015
Year: 2015

Reducing energy consumption is a challenge that is faced on a daily basis by teams from the High-Performance Computing as well as the Embedded domain. This issue is mostly attacked from an hardware perspective, by devising architectures that put energy efficiency as a primary target, often at the cost of processing power. Lately, computing platforms have become more and more heterogeneous, but the exploitation of these additional capabilities is so complex from the application developer's perspective that they are left unused most of the time, resulting therefore in a supplemental waste of energy rather than in faster processing times. In this paper we present a transparent, on-the-fly optimization scheme that allows a generic application to automatically exploit the available computing units to partition its computational load. We have called our approach Heterogeneous Platform Accelerator (HPA). The idea is to use profiling to automatically select a computing-intensive candidate for acceleration, and then distribute the computations to the different units by off-loading blocks of code to them. Using an NVIDIA Jetson TK1 board, we demonstrate that not only HPA results in faster processing speed, but also in a considerable reduction in the total energy absorbed.
Energy Efficiency in Massive MIMO-Based 5G Networks: Opportunities and Challenges
Venue: arXiv cs.NI 2015
Year: 2015

As we make progress towards the era of fifth generation (5G) communication networks, energy efficiency (EE) becomes an important design criterion because it guarantees sustainable evolution. In this regard, the massive multiple-input multiple-output (MIMO) technology, where the base stations (BSs) are equipped with a large number of antennas so as to achieve multiple orders of spectral and energy efficiency gains, will be a key technology enabler for 5G. In this article, we present a comprehensive discussion on state-of-the-art techniques which further enhance the EE gains offered by massive MIMO (MM). We begin with an overview of MM systems and discuss how realistic power consumption models can be developed for these systems. Thereby, we discuss and identify few shortcomings of some of the most prominent EE-maximization techniques present in the current literature. Then, we discuss "hybrid MM systems" operating in a 5G architecture, where MM operates in conjunction with other potential technology enablers, such as millimetre wave, heterogenous networks, and energy harvesting networks. Multiple opportunities and challenges arise in such a 5G architecture because these technologies benefit mutually from each other and their coexistence introduces several new constraints on the design of energy-efficient systems. Despite clear evidence that hybrid MM systems can achieve significantly higher EE gains than conventional MM systems, several open research problems continue to roadblock system designers from fully harnessing the EE gains offered by hybrid MM systems. Our discussions lead to the conclusion that hybrid MM systems offer a sustainable evolution towards 5G networks and are therefore an important research topic for future work.