OpenRaiser/Intern-Atlas huggingface dataset:
Fast Heuristics for Power Allocation in Zero-Forcing OFDMA-SDMA Systems with Minimum Rate Constraints
Venue: arXiv cs.IT 2014
Year: 2014

We investigate in this paper the optimal power allocation in an OFDM-SDMA system when some users have minimum downlink transmission rate requirements. We first solve the unconstrained power allocation problem for which we propose a fast zero-finding technique that is guaranteed to find an optimal solution, and an approximate solution that has lower complexity but is not guaranteed to converge. For the more complex minimum rate constrained problem, we propose two approximate algorithms. One is an iterative technique that finds an optimal solution on the rate boundaries so that the solution is feasible, but not necessarily optimal. The other is not iterative but cannot guarantee a feasible solution. We present numerical results showing that the computation time for the iterative heuristic is one order of magnitude faster than finding the exact solution with a numerical solver, and the non-iterative technique is an additional order of magnitude faster than the iterative heuristic. We also show that in most cases, the amount of infeasibility with the non-iterative technique is small enough that it could probably be used in practice.
Multithreshold Entropy Linear Classifier
Venue: arXiv cs.LG 2014
Year: 2014

Linear classifiers separate the data with a hyperplane. In this paper we focus on the novel method of construction of multithreshold linear classifier, which separates the data with multiple parallel hyperplanes. Proposed model is based on the information theory concepts -- namely Renyi's quadratic entropy and Cauchy-Schwarz divergence. We begin with some general properties, including data scale invariance. Then we prove that our method is a multithreshold large margin classifier, which shows the analogy to the SVM, while in the same time works with much broader class of hypotheses. What is also interesting, proposed method is aimed at the maximization of the balanced quality measure (such as Matthew's Correlation Coefficient) as opposed to very common maximization of the accuracy. This feature comes directly from the optimization problem statement and is further confirmed by the experiments on the UCI datasets. It appears, that our Multithreshold Entropy Linear Classifier (MELC) obtaines similar or higher scores than the ones given by SVM on both synthetic and real data. We show how proposed approach can be benefitial for the cheminformatics in the task of ligands activity prediction, where despite better classification results, MELC gives some additional insight into the data structure (classes of underrepresented chemical compunds).
Lime: Data Lineage in the Malicious Environment
Venue: arXiv cs.CR 2014
Year: 2014

Intentional or unintentional leakage of confidential data is undoubtedly one of the most severe security threats that organizations face in the digital era. The threat now extends to our personal lives: a plethora of personal information is available to social networks and smartphone providers and is indirectly transferred to untrustworthy third party and fourth party applications. In this work, we present a generic data lineage framework LIME for data flow across multiple entities that take two characteristic, principal roles (i.e., owner and consumer). We define the exact security guarantees required by such a data lineage mechanism toward identification of a guilty entity, and identify the simplifying non repudiation and honesty assumptions. We then develop and analyze a novel accountable data transfer protocol between two entities within a malicious environment by building upon oblivious transfer, robust watermarking, and signature primitives. Finally, we perform an experimental evaluation to demonstrate the practicality of our protocol.
Competitive performance analysis of two evolutionary algorithms for routing optimization in graded network
Venue: arXiv cs.NI 2014
Year: 2014

In this paper we compare the two intelligent route generation system and its performance capability in graded networks using Artificial Bee Colony (ABC) algorithm and Genetic Algorithm (GA). Both ABC and GA have found its importance in optimization technique for determining optimal path while routing operations in the network. The paper shows how ABC approach has been utilized for determining the optimal path based on bandwidth availability of the links and determines better quality paths over GA. Here the nodes participating in the routing are evaluated for their QoS metric. The nodes which satisfy the minimum threshold value of the metric are chosen and enabled to participate in routing. A quadrant is synthesized on the source as the centre and depending on which quadrant the destination node belongs to, a search for optimal path is performed. The simulation results show that ABC speeds up local minimum search convergence by around 60% as compared to GA with respect to traffic intensity, and opens the possibility for cognitive routing in future intelligent networks.
It is hard to see a needle in a haystack: Modeling contrast masking effect in a numerical observer
Venue: arXiv cs.CV 2014
Year: 2014

Within the framework of a virtual clinical trial for breast imaging, we aim to develop numerical observers that follow the same detection performance trends as those of a typical human observer. In our prior work, we showed that by including spatiotemporal contrast sensitivity function (stCSF) of human visual system (HVS) in a multi-slice channelized Hotelling observer (msCHO), we can correctly predict trends of a typical human observer performance with the viewing parameters of browsing speed, viewing distance and contrast. In this work we further improve our numerical observer by modeling contrast masking. After stCSF, contrast masking is the second most prominent property of HVS and it refers to the fact that the presence of one signal affects the visibility threshold for another signal. Our results indicate that the improved numerical observer better predicts changes in detection performance with background complexity.
A Review Paper on Oculus Rift-A Virtual Reality Headset
Venue: arXiv cs.HC 2014
Year: 2014

Oculus rift: Virtual reality (VR) is a burgeoning field that has the inherent potential of manipulating peoples mind with a superlative 3D experience. Oculus rift is one such application that assists in achieving the same. With the fleeting enhancements in VR it now seems very feasible to provide the user with experiences that were earlier thought to be merely a dream or a nightmare.
A Unifying Hierarchy of Valuations with Complements and Substitutes
Venue: arXiv cs.GT 2014
Year: 2014

We introduce a new hierarchy over monotone set functions, that we refer to as $\mathcal{MPH}$ (Maximum over Positive Hypergraphs). Levels of the hierarchy correspond to the degree of complementarity in a given function. The highest level of the hierarchy, $\mathcal{MPH}$-$m$ (where $m$ is the total number of items) captures all monotone functions. The lowest level, $\mathcal{MPH}$-$1$, captures all monotone submodular functions, and more generally, the class of functions known as $\mathcal{XOS}$. Every monotone function that has a positive hypergraph representation of rank $k$ (in the sense defined by Abraham, Babaioff, Dughmi and Roughgarden [EC 2012]) is in $\mathcal{MPH}$-$k$. Every monotone function that has supermodular degree $k$ (in the sense defined by Feige and Izsak [ITCS 2013]) is in $\mathcal{MPH}$-$(k+1)$. In both cases, the converse direction does not hold, even in an approximate sense. We present additional results that demonstrate the expressiveness power of $\mathcal{MPH}$-$k$. One can obtain good approximation ratios for some natural optimization problems, provided that functions are required to lie in low levels of the $\mathcal{MPH}$ hierarchy. We present two such applications. One shows that the maximum welfare problem can be approximated within a ratio of $k+1$ if all players hold valuation functions in $\mathcal{MPH}$-$k$. The other is an upper bound of $2k$ on the price of anarchy of simultaneous first price auctions. Being in $\mathcal{MPH}$-$k$ can be shown to involve two requirements -- one is monotonicity and the other is a certain requirement that we refer to as $\mathcal{PLE}$ (Positive Lower Envelope). Removing the monotonicity requirement, one obtains the $\mathcal{PLE}$ hierarchy over all non-negative set functions (whether monotone or not), which can be fertile ground for further research.
The complexity of computing a (quasi-)perfect equilibrium for an n-player extensive form game of perfect recall
Venue: arXiv cs.GT 2014
Year: 2014

We study the complexity of computing or approximating refinements of Nash equilibrium for a given finite n-player extensive form game of perfect recall (EFGPR), where n >= 3. Our results apply to a number of well-studied refinements, including sequential (SE), extensive-form perfect (PE), and quasi-perfect equilibrium (QPE). These refine Nash and subgame-perfect equilibrium. Of these, the most refined notions are PE and QPE. By classic results, all these equilibria exist in any EFGPR. We show that, for all these notions of equilibrium, approximating an equilibrium for a given EFGPR, to within a given desired precision, is FIXP_a-complete. We also consider the complexity of corresponding "almost" equilibrium notions, and show that they are PPAD-complete. In particular, we define "delta-almost epsilon-(quasi-)perfect" equilibrium, and show computing one is PPAD-complete. We show these notions refine "delta-almost subgame-perfect equilibrium" for EFGPRs, which is PPAD-complete. Thus, approximating one such (delta-almost) equilibrium for n-player EFGPRs, n >= 3, is P-time equivalent to approximating a (delta-almost) NE for a normal form game (NFG) with 3 or more players. NFGs are trivially encodable as EFGPRs without blowup in size. Thus our results extend the celebrated complexity results for NFGs to refinements of equilibrium in the more general setting of EFGPRs. For 2-player EFGPRs, analogous complexity results follow from the algorithms of Koller, Megiddo, and von Stengel (1996), von Stengel, van den Elzen, and Talman (2002), and Miltersen and Soerensen (2010). For n-player EFGPRs, an analogous result for Nash and subgame-perfect equilibrium was given by Daskalakis, Fabrikant, and Papadimitriou (2006). However, no analogous results were known for the more refined notions of equilibrium for EFGPRs with 3 or more players.
Demand Response Management For Power Throttling Air Conditioning Loads In Residential Smart Grids
Venue: arXiv cs.SY 2014
Year: 2014

In this paper we develop an algorithm for peak load reduction to reduce the impact of increased air conditioner usage in a residential smart grid community. We develop Demand Response Management (DRM) plans that clearly spell out the maximum duration as well as maximum severity of inconvenience. We model the air conditioner as a power throttling device and for any given DRM plan we study the impact of increasing the number of power states on the resulting peak load reduction. Through simulations, we find out that adding just one additional state to the basic ON/OFF model, which can throttle power to 50% of the rated air conditioner power, can result in significant amount of peak reduction. However, the peak load that can be reduced is diminishing with the increase in number of states. Furthermore, we also observe the impact of inconvenience duration and inconvenience severity in terms of peak load reduction. These observations can serve as useful guidelines for developing appropriate DRM plans.
Do feelings matter? On the correlation of affects and the self-assessed productivity in software engineering
Venue: arXiv cs.SE 2014
Year: 2014

Background: software engineering research (SE) lacks theory and methodologies for addressing human aspects in software development. Development tasks are undertaken through cognitive processing activities. Affects (emotions, moods, feelings) have a linkage to cognitive processing activities and the productivity of individuals. SE research needs to incorporate affect measurements to valorize human factors and to enhance management styles. Objective: analyze the affects dimensions of valence, arousal, and dominance of software developers and their real-time correlation with their self-assessed productivity (sPR). Method: repeated measurements design with 8 participants (4 students, 4 professionals), conveniently sampled and studied individually over 90 minutes of programming. The analysis was performed by fitting a linear mixed- effects (LME) model. Results: valence and dominance are positively correlated with the sPR. The model was able to express about 38% of deviance from the sPR. Many lessons were learned when employing psychological measurements in SE and for fitting LME. Conclusion: this article demonstrates the value of applying psychological tests in SE and echoes a call to valorize the human, individualized aspects of software developers. It reports a body of knowledge about affects, their classification, their measurement, and the best practices to perform psychological measurements in SE with LME models.
An intelligent routing approach using genetic algorithms for quality graded network
Venue: arXiv cs.NI 2014
Year: 2014

Intelligent routing in networks has opened up many challenges in modelling and methods, over the past decade. Many techniques do exist for routing on such an environment where path determination was carried out by advertisement, position and near-optimum node selection schemes. In this paper, an efficient routing scheme has been proposed using genetic algorithm for a grade-based two-level node selection method. This method assumes that nodes have the knowledge of its environment and is capable of taking decision for route discovery. The data learnt from the topology which is under consideration for routing, is saved in its local memory. In this two-level node selection scheme, the route discovery operation takes place in multiple levels. At the first level, the grade based selection is applied for considering the most optimal nodes which would be fit for sending data. At the second level, the optimal path is discovered using Genetic Algorithm. The simulation result shows that faster convergence of path took place in the case of the proposed method with good fitness value, as compared to non-graded network.
Lighthouse: A User-Centered Web Service for Linear Algebra Software
Venue: arXiv cs.MS 2014
Year: 2014

Various fields of science and engineering rely on linear algebra for large scale data analysis, modeling and simulation, machine learning, and other applied problems. Linear algebra computations often dominate the execution time of such applications. Meanwhile, experts in these domains typically lack the training or time required to develop efficient, high-performance implementations of linear algebra algorithms. In the Lighthouse project, we enable developers with varied backgrounds to readily discover and effectively apply the best available numerical software for their problems. We have developed a search-based expert system that combines expert knowledge, machine learningbased classification of existing numerical software collections, and automated code generation and optimization. Lighthouse provides a novel software engineering environment aimed at maximizing both developer productivity and application performance for dense and sparse linear algebra computations.
State of the Art and Prospects of Structured Sensing Matrices in Compressed Sensing
Venue: arXiv cs.IT 2014
Year: 2014

Compressed sensing (CS) enables people to acquire the compressed measurements directly and recover sparse or compressible signals faithfully even when the sampling rate is much lower than the Nyquist rate. However, the pure random sensing matrices usually require huge memory for storage and high computational cost for signal reconstruction. Many structured sensing matrices have been proposed recently to simplify the sensing scheme and the hardware implementation in practice. Based on the restricted isometry property and coherence, couples of existing structured sensing matrices are reviewed in this paper, which have special structures, high recovery performance, and many advantages such as the simple construction, fast calculation and easy hardware implementation. The number of measurements and the universality of different structure matrices are compared.
Maximum ATSP with Weights Zero and One via Half-Edges
Venue: arXiv cs.DS 2014
Year: 2014

We present a fast combinatorial $3/4$-approximation algorithm for the maximum asymmetric TSP with weights zero and one. The approximation factor of this algorithm matches the currently best one given by Bläser in 2004 and based on linear programming. Our algorithm first computes a maximum size matching and a maximum weight cycle cover without certain cycles of length two but possibly with {\em half-edges} - a half-edge of a given edge $e$ is informally speaking a half of $e$ that contains one of the endpoints of $e$. Then from the computed matching and cycle cover it extracts a set of paths, whose weight is large enough to be able to construct a traveling salesman tour with the claimed guarantee.
Fixed-point Characterization of Compositionality Properties of Probabilistic Processes Combinators
Venue: arXiv cs.PL 2014
Year: 2014

Bisimulation metric is a robust behavioural semantics for probabilistic processes. Given any SOS specification of probabilistic processes, we provide a method to compute for each operator of the language its respective metric compositionality property. The compositionality property of an operator is defined as its modulus of continuity which gives the relative increase of the distance between processes when they are combined by that operator. The compositionality property of an operator is computed by recursively counting how many times the combined processes are copied along their evolution. The compositionality properties allow to derive an upper bound on the distance between processes by purely inspecting the operators used to specify those processes.
Random Algorithms for the Loop Cutset Problem
Venue: arXiv cs.AI 2014
Year: 2014

We show how to find a minimum loop cutset in a Bayesian network with high probability. Finding such a loop cutset is the first step in Pearl's method of conditioning for inference. Our random algorithm for finding a loop cutset, called "Repeated WGuessI", outputs a minimum loop cutset, after O(c 6^k k n) steps, with probability at least 1-(1 over{6^k})^{c 6^k}), where c>1 is a constant specified by the user, k is the size of a minimum weight loop cutset, and n is the number of vertices. We also show empirically that a variant of this algorithm, called WRA, often finds a loop cutset that is closer to the minimum loop cutset than the ones found by the best deterministic algorithms known.
OS effect in SLM schemes with correlation
Venue: arXiv cs.IT 2014
Year: 2014

BER is analyzed SLM schemes with correlation metric.
Group colocation behavior in technological social networks
Venue: arXiv cs.SI 2014
Year: 2014

We analyze two large datasets from technological networks with location and social data: user location records from an online location-based social networking service, and anonymized telecommunications data from a European cellphone operator, in order to investigate the differences between individual and group behavior with respect to physical location. We discover agreements between the two datasets: firstly, that individuals are more likely to meet with one friend at a place they have not visited before, but tend to meet at familiar locations when with a larger group. We also find that groups of individuals are more likely to meet at places that their other friends have visited, and that the type of a place strongly affects the propensity for groups to meet there. These differences between group and solo mobility has potential technological applications, for example, in venue recommendation in location-based social networks.
Matrix Completion on Graphs
Venue: arXiv cs.LG 2014
Year: 2014

The problem of finding the missing values of a matrix given a few of its entries, called matrix completion, has gathered a lot of attention in the recent years. Although the problem under the standard low rank assumption is NP-hard, Candès and Recht showed that it can be exactly relaxed if the number of observed entries is sufficiently large. In this work, we introduce a novel matrix completion model that makes use of proximity information about rows and columns by assuming they form communities. This assumption makes sense in several real-world problems like in recommender systems, where there are communities of people sharing preferences, while products form clusters that receive similar ratings. Our main goal is thus to find a low-rank solution that is structured by the proximities of rows and columns encoded by graphs. We borrow ideas from manifold learning to constrain our solution to be smooth on these graphs, in order to implicitly force row and column proximities. Our matrix recovery model is formulated as a convex non-smooth optimization problem, for which a well-posed iterative scheme is provided. We study and evaluate the proposed matrix completion on synthetic and real data, showing that the proposed structured low-rank recovery model outperforms the standard matrix completion model in many situations.
A Partial-Order Approach to Array Content Analysis
Venue: arXiv cs.PL 2014
Year: 2014

We present a parametric abstract domain for array content analysis. The method maintains invariants for contiguous regions of the array, similar to the methods of Gopan, Reps and Sagiv, and of Halbwachs and Peron. However, it introduces a novel concept of an array content graph, avoiding the need for an up-front factorial partitioning step. The resulting analysis can be used with arbitrary numeric relational abstract domains; we evaluate the domain on a range of array manipulating program fragments.
Capacity and Stable Scheduling in Heterogeneous Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

Heterogeneous wireless networks (HetNets) provide a means to increase network capacity by introducing small cells and adopting a layered architecture. HetNets allocate resources flexibly through time sharing and cell range expansion/contraction allowing a wide range of possible schedulers. In this paper we define the capacity of a HetNet down link in terms of the maximum number of downloads per second which can be achieved for a given offered traffic density. Given this definition we show that the capacity is determined via the solution to a continuous linear program (LP). If the solution is smaller than 1 then there is a scheduler such that the number of mobiles in the network has ergodic properties with finite mean waiting time. If the solution is greater than 1 then no such scheduler exists. The above results continue to hold if a more general class of schedulers is considered.
Asymptotically exact streaming algorithms
Venue: arXiv cs.DS 2014
Year: 2014

We introduce a new computational model for data streams: asymptotically exact streaming algorithms. These algorithms have an approximation ratio that tends to one as the length of the stream goes to infinity while the memory used by the algorithm is restricted to polylog(n) size. Thus, the output of the algorithm is optimal in the limit. We show positive results in our model for a series of important problems that have been discussed in the streaming literature. These include computing the frequency moments, clustering problems and least squares regression. Our results also include lower bounds for problems, which have streaming algorithms in the ordinary setting but do not allow for sublinear space algorithms in our model.