OpenRaiser/Intern-Atlas huggingface dataset:
The Distant Heart: Mediating Long-Distance Relationships through Connected Computational Jewelry
Venue: arXiv cs.HC 2015
Year: 2015

In the world where increasingly mobility and long-distance relationships with family, friends and loved-ones became commonplace, there exists a gap in intimate interpersonal communication mediated by technology. Considering the advances in the field of mediation of relationships through technology, as well as prevalence of use of jewelry as love-tokens for expressing a wish to be remembered and to evoke the presence of the loved-one, developments in the new field of computational jewelry offer some truly exciting possibilities. In this paper we investigate the role that the jewelry-like form factor of prototypes can play in the context of studying effects of computational jewelry in mediating long-distance relationships.
Recent Developments in the Optimization of Space Robotics for Perception in Planetary Exploration
Venue: arXiv cs.RO 2015
Year: 2015

The following paper reviews recent developments in the field of optimization of space robotics. The extent of focus of this paper is on the perception (robotic sense of analyzing surroundings) in space robots in the exploration of extra-terrestrial planets. Robots play a crucial role in exploring extra-terrestrial and planetary bodies. Their advantages are far from being counted on finger tips. With the advent of autonomous robots in the field of robotics, the role for space exploration has further hustled up. Optimization of such autonomous robots has turned into a necessity of the hour. Optimized robots tend to have a superior role in space exploration. With so many considerations to monitor, an optimized solution will nevertheless help a planetary rover perform better under tight circumstances. Keeping in view the above mentioned area, the paper describes recent developments in the optimization of autonomous extra-terrestrial rovers.
Triple State QuickSort, A replacement for the C/C++ library qsort
Venue: arXiv cs.DS 2015
Year: 2015

An industrial grade Quicksort function along with its new algorithm is presented. Compared to 4 other well known implementations of Quicksort, the new algorithm reduces both the number of comparisons and swaps in most cases while staying close to the best of the 4 in worst cases. We trade space for performance, at the price of n/2 temporary extra spaces in the worst case. Run time tests reveal an overall improvement of at least 15.8% compared to the overall best of the other 4 functions. Furthermore, our function scores a 32.7% run time improvement against Yaroslavskiy's new Dual Pivot Quicksort. Our function is pointer based, which is meant as a replacement for the C/C++ library qsort(). But we also provide an array based function of the same algorithm for easy porting to different programming languages.
Higher Order Maximum Persistency and Comparison Theorems
Venue: arXiv cs.CV 2015
Year: 2015

We address combinatorial problems that can be formulated as minimization of a partially separable function of discrete variables (energy minimization in graphical models, weighted constraint satisfaction, pseudo-Boolean optimization, 0-1 polynomial programming). For polyhedral relaxations of such problems it is generally not true that variables integer in the relaxed solution will retain the same values in the optimal discrete solution. Those which do are called persistent. Such persistent variables define a part of a globally optimal solution. Once identified, they can be excluded from the problem, reducing its size. To any polyhedral relaxation we associate a sufficient condition proving persistency of a subset of variables. We set up a specially constructed linear program which determines the set of persistent variables maximal with respect to the relaxation. The condition improves as the relaxation is tightened and possesses all its invariances. The proposed framework explains a variety of existing methods originating from different areas of research and based on different principles. A theoretical comparison is established that relates these methods to the standard linear relaxation and proves that the proposed technique identifies same or larger set of persistent variables.
MIMO DF Relay Beamforming for Secrecy with Artificial Noise, Imperfect CSI, and Finite-Alphabet
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider decode-and-forward (DF) relay beamforming with imperfect channel state information (CSI), cooperative artificial noise (AN) injection, and finite-alphabet input in the presence of an user and $J$ non-colluding eavesdroppers. The communication between the source and the user is aided by a multiple-input-multiple-output (MIMO) DF relay. We use the fact that a wiretap code consists of two parts: i) common message (non-secret), and ii) secret message. The source transmits two independent messages: i) common message (non-secret), and ii) secret message. The common message is transmitted at a fixed rate $R_{0}$, and it is intended for the user. The secret message is also intended for the user but it should be kept secret from the $J$ eavesdroppers. The source and the MIMO DF relay operate under individual power constraints. In order to improve the secrecy rate, the MIMO relay also injects artificial noise. The CSI on all the links are assumed to be imperfect and CSI errors are assumed to be norm bounded. In order to maximize the worst case secrecy rate, we maximize the worst case link information rate to the user subject to: i) the individual power constraints on the source and the MIMO relay, and ii) the best case link information rates to $J$ eavesdroppers be less than or equal to $R_{0}$ in order to support a fixed common message rate $R_{0}$. Numerical results showing the effect of perfect/imperfect CSI, presence/absence of AN with finite-alphabet input on the secrecy rate are presented.
Dynamic resource management in Cloud datacenters for Server consolidation
Venue: arXiv cs.DC 2015
Year: 2015

Cloud resource management has been a key factor for the cloud datacenters development. Many cloud datacenters have problems in understanding and implementing the techniques to manage, allocate and migrate the resources in their premises. The consequences of improper resource management may result into underutilized and wastage of resources which may also result into poor service delivery in these datacenters. Resources like, CPU, memory, Hard disk and servers need to be well identified and managed. In this Paper, Dynamic Resource Management Algorithm(DRMA) shall limit itself in the management of CPU and memory as the resources in cloud datacenters. The target is to save those resources which may be underutilized at a particular period of time. It can be achieved through Implementation of suitable algorithms. Here, Bin packing algorithm can be used whereby the best fit algorithm is deployed to obtain results and compared to select suitable algorithm for efficient use of resources.
On the Feedback Reduction of Relay Aided Multiuser Networks using Compressive Sensing
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a feedback reduction scheme for full-duplex relay-aided multiuser networks. The proposed scheme permits the base station (BS) to obtain channel state information (CSI) from a subset of strong users under substantially reduced feedback overhead. More specifically, we cast the problem of user identification and CSI estimation as a block sparse signal recovery problem in compressive sensing (CS). Using existing CS block recovery algorithms, we first obtain the identity of the strong users and then estimate their CSI using the best linear unbiased estimator (BLUE). To minimize the effect of noise on the estimated CSI, we introduce a back-off strategy that optimally backs-off on the noisy estimated CSI and derive the error covariance matrix of the post-detection noise. In addition to this, we provide exact closed form expressions for the average maximum equivalent SNR at the destination user. Numerical results show that the proposed algorithm drastically reduces the feedback air-time and achieves a rate close to that obtained by scheduling schemes that require dedicated error-free feedback from all the network users.
Oblivious Lookup Tables
Venue: arXiv cs.CR 2015
Year: 2015

We consider the following question: given a group-homomorphic public-key encryption $E$, a ciphertext $c=E(x,pk)$ hiding a value $x$ using a key $pk$, and a "suitable" description of a function $f$, can we evaluate $E(f(x), pk)$ without decrypting $c$? We call this an "oblivious lookup table" and show the existence of such a primitive. To this end, we describe a concrete construction, discuss its security and relations to other cryptographic primitives, and point out directions of future investigations towards generalizations.
Delay-Distortion-Power Trade Offs in Quasi-Stationary Source Transmission over Block Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates delay-distortion-power trade offs in transmission of quasi-stationary sources over block fading channels by studying encoder and decoder buffering techniques to smooth out the source and channel variations. Four source and channel coding schemes that consider buffer and power constraints are presented to minimize the reconstructed source distortion. The first one is a high performance scheme, which benefits from optimized source and channel rate adaptation. In the second scheme, the channel coding rate is fixed and optimized along with transmission power with respect to channel and source variations; hence this scheme enjoys simplicity of implementation. The two last schemes have fixed transmission power with optimized adaptive or fixed channel coding rate. For all the proposed schemes, closed form solutions for mean distortion, optimized rate and power are provided and in the high SNR regime, the mean distortion exponent and the asymptotic mean power gains are derived. The proposed schemes with buffering exploit the diversity due to source and channel variations. Specifically, when the buffer size is limited, fixed channel rate adaptive power scheme outperforms an adaptive rate fixed power scheme. Furthermore, analytical and numerical results demonstrate that with limited buffer size, the system performance in terms of reconstructed signal SNR saturates as transmission power is increased, suggesting that appropriate buffer size selection is important to achieve a desired reconstruction quality.
Parameterized Approximation Algorithms for Packing Problems
Venue: arXiv cs.DS 2015
Year: 2015

In the past decade, many parameterized algorithms were developed for packing problems. Our goal is to obtain tradeoffs that improve the running times of these algorithms at the cost of computing approximate solutions. Consider a packing problem for which there is no known algorithm with approximation ratio $α$, and a parameter $k$. If the value of an optimal solution is at least $k$, we seek a solution of value at least $αk$; otherwise, we seek an arbitrary solution. Clearly, if the best known parameterized algorithm that finds a solution of value $t$ runs in time $O^*(f(t))$ for some function $f$, we are interested in running times better than $O^*(f(αk))$. We present tradeoffs between running times and approximation ratios for the $P_2$-Packing, $3$-Set $k$-Packing and $3$-Dimensional $k$-Matching problems. Our tradeoffs are based on combinations of several known results, as well as a computation of "approximate lopsided universal sets."
Econometrics for Learning Agents
Venue: arXiv cs.GT 2015
Year: 2015

The main goal of this paper is to develop a theory of inference of player valuations from observed data in the generalized second price auction without relying on the Nash equilibrium assumption. Existing work in Economics on inferring agent values from data relies on the assumption that all participant strategies are best responses of the observed play of other players, i.e. they constitute a Nash equilibrium. In this paper, we show how to perform inference relying on a weaker assumption instead: assuming that players are using some form of no-regret learning. Learning outcomes emerged in recent years as an attractive alternative to Nash equilibrium in analyzing game outcomes, modeling players who haven't reached a stable equilibrium, but rather use algorithmic learning, aiming to learn the best way to play from previous observations. In this paper we show how to infer values of players who use algorithmic learning strategies. Such inference is an important first step before we move to testing any learning theoretic behavioral model on auction data. We apply our techniques to a dataset from Microsoft's sponsored search ad auction system.
Large-scale Classification of Fine-Art Paintings: Learning The Right Metric on The Right Feature
Venue: arXiv cs.CV 2015
Year: 2015

In the past few years, the number of fine-art collections that are digitized and publicly available has been growing rapidly. With the availability of such large collections of digitized artworks comes the need to develop multimedia systems to archive and retrieve this pool of data. Measuring the visual similarity between artistic items is an essential step for such multimedia systems, which can benefit more high-level multimedia tasks. In order to model this similarity between paintings, we should extract the appropriate visual features for paintings and find out the best approach to learn the similarity metric based on these features. We investigate a comprehensive list of visual features and metric learning approaches to learn an optimized similarity measure between paintings. We develop a machine that is able to make aesthetic-related semantic-level judgments, such as predicting a painting's style, genre, and artist, as well as providing similarity measures optimized based on the knowledge available in the domain of art historical interpretation. Our experiments show the value of using this similarity measure for the aforementioned prediction tasks.
On the Complexity of an Unregulated Traffic Crossing
Venue: arXiv cs.CG 2015
Year: 2015

The steady development of motor vehicle technology will enable cars of the near future to assume an ever increasing role in the decision making and control of the vehicle itself. In the foreseeable future, cars will have the ability to communicate with one another in order to better coordinate their motion. This motivates a number of interesting algorithmic problems. One of the most challenging aspects of traffic coordination involves traffic intersections. In this paper we consider two formulations of a simple and fundamental geometric optimization problem involving coordinating the motion of vehicles through an intersection. We are given a set of $n$ vehicles in the plane, each modeled as a unit length line segment that moves monotonically, either horizontally or vertically, subject to a maximum speed limit. Each vehicle is described by a start and goal position and a start time and deadline. The question is whether, subject to the speed limit, there exists a collision-free motion plan so that each vehicle travels from its start position to its goal position prior to its deadline. We present three results. We begin by showing that this problem is NP-complete with a reduction from 3-SAT. Second, we consider a constrained version in which cars traveling horizontally can alter their speeds while cars traveling vertically cannot. We present a simple algorithm that solves this problem in $O(n \log n)$ time. Finally, we provide a solution to the discrete version of the problem and prove its asymptotic optimality in terms of the maximum delay of a vehicle.
Zero Error Coordination
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider a zero error coordination problem wherein the nodes of a network exchange messages to be able to perfectly coordinate their actions with the individual observations of each other. While previous works on coordination commonly assume an asymptotically vanishing error, we assume exact, zero error coordination. Furthermore, unlike previous works that employ the empirical or strong notions of coordination, we define and use a notion of set coordination. This notion of coordination bears similarities with the empirical notion of coordination. We observe that set coordination, in its special case of two nodes with a one-way communication link is equivalent with the "Hide and Seek" source coding problem of McEliece and Posner. The Hide and Seek problem has known intimate connections with graph entropy, rate distortion theory, Renyi mutual information and even error exponents. Other special cases of the set coordination problem relate to Witsenhausen's zero error rate and the distributed computation problem. These connections motivate a better understanding of set coordination, its connections with empirical coordination, and its study in more general setups. This paper takes a first step in this direction by proving new results for two node networks.
A Coinductive Framework for Infinitary Rewriting and Equational Reasoning (Extended Version)
Venue: arXiv cs.LO 2015
Year: 2015

We present a coinductive framework for defining infinitary analogues of equational reasoning and rewriting in a uniform way. We define the relation =^infty, notion of infinitary equational reasoning, and ->^infty, the standard notion of infinitary rewriting as follows: =^infty := nu R. ( <-_root + ->_root + lift(R) )^* ->^infty := mu R. nu S. ( ->_root + lift(R) )^* ; lift(S) where lift(R) := { (f(s_1,...,s_n), f(t_1,...,t_n)) | s_1 R t_1,...,s_n R t_n } + id , and where mu is the least fixed point operator and nu is the greatest fixed point operator. The setup captures rewrite sequences of arbitrary ordinal length, but it has neither the need for ordinals nor for metric convergence. This makes the framework especially suitable for formalizations in theorem provers.
Learning Style Similarity for Searching Infographics
Venue: arXiv cs.GR 2015
Year: 2015

Infographics are complex graphic designs integrating text, images, charts and sketches. Despite the increasing popularity of infographics and the rapid growth of online design portfolios, little research investigates how we can take advantage of these design resources. In this paper we present a method for measuring the style similarity between infographics. Based on human perception data collected from crowdsourced experiments, we use computer vision and machine learning algorithms to learn a style similarity metric for infographic designs. We evaluate different visual features and learning algorithms and find that a combination of color histograms and Histograms-of-Gradients (HoG) features is most effective in characterizing the style of infographics. We demonstrate our similarity metric on a preliminary image retrieval test.
Mitigating Hardware Cyber-Security Risks in Error Correcting Decoders
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates hardware cyber-security risks associated with channel decoders, which are commonly acquired as a black box in semiconductor industry. It is shown that channel decoders are potentially attractive targets for hardware cyber-security attacks and can be easily embedded with malicious blocks. Several attack scenarios are considered in this work and suitable methods for mitigating the risks are proposed. These methods are based on randomizing the inputs of the channel decoder to obstruct the communications between attackers and the malicious blocks, ideally without changing the decoding performance.
Certification of Confluence Proofs using CeTA
Venue: arXiv cs.LO 2015
Year: 2015

CeTA was originally developed as a tool for certifying termination proofs which have to be provided as certificates in the CPF-format. Its soundness is proven as part of IsaFoR, the Isabelle Formalization of Rewriting. By now, CeTA can also be used for certifying confluence and non-confluence proofs. In this system description, we give a short overview on what kind of proofs are supported, and what information has to be given in the certificates. As we will see, only a small amount of information is required and so we hope that CSI will not stay the only confluence tool which can produce certificates.
KBCV 2.0 - Automatic Completion Experiments
Venue: arXiv cs.LO 2015
Year: 2015

This paper describes the automatic mode of the new version of the Knuth-Bendix Completion Visualizer. The internally used data structures have been overhauled and the performance was dramatically improved by introducing caching, parallelization, and term- indexing in the computation of critical pairs and simplification. The new version is much faster and can complete three more systems.
A Comprehensive Study On The Applications Of Machine Learning For Diagnosis Of Cancer
Venue: arXiv cs.LG 2015
Year: 2015

Collectively, lung cancer, breast cancer and melanoma was diagnosed in over 535,340 people out of which, 209,400 deaths were reported [13]. It is estimated that over 600,000 people will be diagnosed with these forms of cancer in 2015. Most of the deaths from lung cancer, breast cancer and melanoma result due to late detection. All of these cancers, if detected early, are 100% curable. In this study, we develop and evaluate algorithms to diagnose Breast cancer, Melanoma, and Lung cancer. In the first part of the study, we employed a normalised Gradient Descent and an Artificial Neural Network to diagnose breast cancer with an overall accuracy of 91% and 95% respectively. In the second part of the study, an artificial neural network coupled with image processing and analysis algorithms was employed to achieve an overall accuracy of 93% A naive mobile based application that allowed people to take diagnostic tests on their phones was developed. Finally, a Support Vector Machine algorithm incorporating image processing and image analysis algorithms was developed to diagnose lung cancer with an accuracy of 94%. All of the aforementioned systems had very low false positive and false negative rates. We are developing an online network that incorporates all of these systems and allows people to collaborate globally.
Performance Analysis of Opportunistic Relaying Over Imperfect Non-identical Log-normal Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

Motivated by the fact that full diversity order is achieved using the "best-relay" selection technique, we consider opportunistic amplify-and-forward and decode-and-forward relaying systems. We focus on the outage probability of such a systems and then derive closed-form expressions for the outage probability of these systems over independent but non-identical imperfect Log-normal fading channels. We consider the error of channel estimation as a Gaussian random variable. As a result the estimated channels distribution are not Log-normal either as would be in the case of the Rayleigh fading channels. This is exactly the reason why our simulation results do not exactly matched with analytical results. However, this difference is negligible for a wide variety of situations.