OpenRaiser/Intern-Atlas huggingface dataset:
Profile-based optimal matchings in the Student/Project Allocation problem
Venue: arXiv cs.DS 2015
Year: 2015

In the Student / Project Allocation problem (SPA) we seek to assign students to individual or group projects offered by lecturers. Students provide a list of projects they find acceptable in order of preference. Each student can be assigned to at most one project and there are constraints on the maximum number of students that can be assigned to each project and lecturer. We seek matchings of students to projects that are optimal with respect to profile, which is a vector whose rth component indicates how many students have their rth-choice project. We present an efficient algorithm for finding a greedy maximum matching in the SPA context - this is a maximum matching whose profile is lexicographically maximum. We then show how to adapt this algorithm to find a generous maximum matching - this is a matching whose reverse profile is lexicographically minimum. Our algorithms involve finding optimal flows in networks. We demonstrate how this approach can allow for additional constraints, such as lecturer lower quotas, to be handled flexibly. Finally we present results obtained from an empirical evaluation of the algorithms.
Optimal Energy-Aware Epidemic Routing in DTNs
Venue: arXiv cs.SY 2015
Year: 2015

In this work, we investigate the use of epidemic routing in energy constrained Delay Tolerant Networks (DTNs). In epidemic routing, messages are relayed by intermediate nodes at contact opportunities, i.e., when pairs of nodes come within the transmission range of each other. Each node needs to decide whether to forward its message upon contact with a new node based on its own residual energy level and the age of that message. We mathematically characterize the fundamental trade-off between energy conservation and a measure of Quality of Service as a dynamic energy-dependent optimal control problem. We prove that in the mean-field regime, the optimal dynamic forwarding decisions follow simple threshold-based structures in which the forwarding threshold for each node depends on its current remaining energy. We then characterize the nature of this dependence. Our simulations reveal that the optimal dynamic policy significantly outperforms heuristics.
Joint Wireless Information and Energy Transfer with Reduced Feedback in MIMO Interference Channels
Venue: arXiv cs.IT 2015
Year: 2015

To determine the transmission strategy for joint wireless information and energy transfer (JWIET) in the MIMO interference channel (IFC), the information access point (IAP) and energy access point (EAP) require the channel state information (CSI) of their associated links to both the information-decoding (ID) mobile stations (MSs) and energy-harvesting (EH) MSs (so-called local CSI). In this paper, to reduce th e feedback overhead of MSs for the JWIET in two-user MIMO IFC, we propose a Geodesic energy beamforming scheme that requires partial CSI at the EAP. Furthermore, in the two-user MIMO IFC, it is proved that the Geodesic energy beamforming is the optimal strategy. By adding a rank-one constraint on the transmit signal covariance of IAP, we can further reduce the feedback overhead to IAP by exploiting Geodesic information beamforming. Under the rank-one constraint of IAP's transmit signal, we prove that Geodesic information/energy beamforming approach is the optimal strategy for JWIET in the two-user MIMO IFC. We also discuss the extension of the proposed rank-one Geodesic information/energy beamforming strategies to general K-user MIMO IFC. Finally, by analyzing the achievable rate-energy performance statistically under imperfect partial CSIT, we propose an adaptive bit allocation strategy for both EH MS and ID MS.
Numerical Investigations on Hatching Process Strategies for Powder Bed Based Additive Manufacturing using an Electron Beam
Venue: arXiv cs.CE 2015
Year: 2015

This paper investigates in hatching process strategies for additive manufacturing using an electron beam by numerical simulations. The underlying physical model and the corresponding three dimensional thermal free surface lattice Boltzmann method of the simulation software are briefly presented. The simulation software has already been validated on the basis of experiments up to 1.2 kW beam power by hatching a cuboid with a basic process strategy, whereby the results are classified into `porous', `good' and `uneven', depending on their relative density and top surface smoothness. In this paper we study the limitations of this basic process strategy in terms of higher beam powers and scan velocities to exploit the future potential of high power electron beam guns up to 10 kW. Subsequently, we introduce modified process strategies, which circumvent these restrictions, to build the part as fast as possible under the restriction of a fully dense part with a smooth top surface. These process strategies are suitable to reduce the build time and costs, maximize the beam power usage and therefore use the potential of high power electron beam guns.
Asynchronous Convex Consensus in the Presence of Crash Faults
Venue: arXiv cs.DC 2015
Year: 2015

This paper defines a new consensus problem, convex consensus. Similar to vector consensus [13, 20, 19], the input at each process is a d-dimensional vector of reals (or, equivalently, a point in the d-dimensional Euclidean space). However, for convex consensus, the output at each process is a convex polytope contained within the convex hull of the inputs at the fault-free processes. We explore the convex consensus problem under crash faults with incorrect inputs, and present an asynchronous approximate convex consensus algorithm with optimal fault tolerance that reaches consensus on an optimal output polytope. Convex consensus can be used to solve other related problems. For instance, a solution for convex consensus trivially yields a solution for vector consensus. More importantly, convex consensus can potentially be used to solve other more interesting problems, such as convex function optimization [5, 4].
VESICLE: Volumetric Evaluation of Synaptic Interfaces using Computer vision at Large Scale
Venue: arXiv cs.CV 2015
Year: 2015

An open challenge problem at the forefront of modern neuroscience is to obtain a comprehensive mapping of the neural pathways that underlie human brain function; an enhanced understanding of the wiring diagram of the brain promises to lead to new breakthroughs in diagnosing and treating neurological disorders. Inferring brain structure from image data, such as that obtained via electron microscopy (EM), entails solving the problem of identifying biological structures in large data volumes. Synapses, which are a key communication structure in the brain, are particularly difficult to detect due to their small size and limited contrast. Prior work in automated synapse detection has relied upon time-intensive biological preparations (post-staining, isotropic slice thicknesses) in order to simplify the problem. This paper presents VESICLE, the first known approach designed for mammalian synapse detection in anisotropic, non-post-stained data. Our methods explicitly leverage biological context, and the results exceed existing synapse detection methods in terms of accuracy and scalability. We provide two different approaches - one a deep learning classifier (VESICLE-CNN) and one a lightweight Random Forest approach (VESICLE-RF) to offer alternatives in the performance-scalability space. Addressing this synapse detection challenge enables the analysis of high-throughput imaging data soon expected to reach petabytes of data, and provide tools for more rapid estimation of brain-graphs. Finally, to facilitate community efforts, we developed tools for large-scale object detection, and demonstrated this framework to find $\approx$ 50,000 synapses in 60,000 $μm ^3$ (220 GB on disk) of electron microscopy data.
Exploiting Regional Differences: A Spatially Adaptive Random Access
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we discuss the potential for improvement of the simple random access scheme by utilizing local information such as the received signal-to-interference-plus-noise-ratio (SINR). We propose a spatially adaptive random access (SARA) scheme in which the transmitters in the network utilize different transmit probabilities depending on the local situation. In our proposed scheme, the transmit probability is adaptively updated by the ratio of the received SINR and the target SINR. We investigate the performance of the spatially adaptive random access scheme. For the comparison, we derive an optimal transmit probability of ALOHA random access scheme in which all transmitters use the same transmit probability. We illustrate the performance of the spatially adaptive random access scheme through simulations. We show that the performance of the proposed scheme surpasses that of the optimal ALOHA random access scheme and is comparable with the CSMA/CA scheme.
Throughput Optimization for Massive MIMO Systems Powered by Wireless Energy Transfer
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies a wireless-energy-transfer (WET) enabled massive multiple-input-multiple-output (MIMO) system (MM) consisting of a hybrid data-and-energy access point (H-AP) and multiple single-antenna users. In the WET-MM system, the H-AP is equipped with a large number $M$ of antennas and functions like a conventional AP in receiving data from users, but additionally supplies wireless power to the users. We consider frame-based transmissions. Each frame is divided into three phases: the uplink channel estimation (CE) phase, the downlink WET phase, as well as the uplink wireless information transmission (WIT) phase. Firstly, users use a fraction of the previously harvested energy to send pilots, while the H-AP estimates the uplink channels and obtains the downlink channels by exploiting channel reciprocity. Next, the H-AP utilizes the channel estimates just obtained to transfer wireless energy to all users in the downlink via energy beamforming. Finally, the users use a portion of the harvested energy to send data to the H-AP simultaneously in the uplink (reserving some harvested energy for sending pilots in the next frame). To optimize the throughput and ensure rate fairness, we consider the problem of maximizing the minimum rate among all users. In the large-$M$ regime, we obtain the asymptotically optimal solutions and some interesting insights for the optimal design of WET-MM system. We define a metric, namely, the massive MIMO degree-of-rate-gain (MM-DoRG), as the asymptotic UL rate normalized by $\log(M)$. We show that the proposed WET-MM system is optimal in terms of MM-DoRG, i.e., it achieves the same MM-DoRG as the case with ideal CE.
An Achievable rate region for the $3-$user interference channel based on coset codes
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of communication over a three user discrete memoryless interference channel ($3-$IC). The current known coding techniques for communicating over an arbitrary $3-$IC are based on message splitting, superposition coding and binning using independent and identically distributed (iid) random codebooks. In this work, we propose a new ensemble of codes - partitioned coset codes (PCC) - that possess an appropriate mix of empirical and algebraic closure properties. We develop coding techniques that exploit algebraic closure property of PCC to enable efficient communication over $3-$IC. We analyze the performance of the proposed coding technique to derive an achievable rate region for the general discrete $3-$IC. Additive and non-additive examples are identified for which the derived achievable rate region is the capacity, and moreover, strictly larger than current known largest achievable rate regions based on iid random codebooks.
Analytic Expressions and Bounds for Special Functions and Applications in Communication Theory
Venue: arXiv cs.IT 2015
Year: 2015

This work is devoted to the derivation of novel analytic expressions and bounds for a family of special functions that are useful in wireless communication theory. These functions are the well-known Nuttall $Q{-}$function, the incomplete Toronto function, the Rice $Ie$-function and the incomplete Lipschitz-Hankel integrals. Capitalizing on the offered results, useful identities are additionally derived between the above functions and the Humbert, $Φ_{1}$, function as well as for specific cases of the Kamp${\it \acute{e}}$ de F${\it \acute{e}}$riet function. These functions can be considered useful mathematical tools that can be employed in applications relating to the analytic performance evaluation of modern wireless communication systems such as cognitive radio, cooperative and free-space optical communications as well as radar, diversity and multi-antenna systems. As an example, new closed-form expressions are derived for the outage probability over non-linear generalized fading channels, namely, $α{-}η{-}μ$, $α{-}λ{-}μ$ and $α{-}κ{-}μ$ as well as for specific cases of the $η{-}μ$ and $λ{-}μ$ fading channels. Furthermore, simple expressions are presented for the channel capacity for the truncated channel inversion with fixed rate and the corresponding optimum cut-off signal-to-noise ratio for single-and multi-antenna communication systems over Rician fading channels. The accuracy and validity of the derived expressions is justified through extensive comparisons with respective numerical results.
Cooperative Energy Trading in CoMP Systems Powered by Smart Grids
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the energy management in the coordinated multi-point (CoMP) systems powered by smart grids, where each base station (BS) with local renewable energy generation is allowed to implement the two-way energy trading with the grid. Due to the uneven renewable energy supply and communication energy demand over distributed BSs as well as the difference in the prices for their buying/selling energy from/to the gird, it is beneficial for the cooperative BSs to jointly manage their energy trading with the grid and energy consumption in CoMP based communication for reducing the total energy cost. Specifically, we consider the downlink transmission in one CoMP cluster by jointly optimizing the BSs' purchased/sold energy units from/to the grid and their cooperative transmit precoding, so as to minimize the total energy cost subject to the given quality of service (QoS) constraints for the users. First, we obtain the optimal solution to this problem by developing an algorithm based on techniques from convex optimization and the uplink-downlink duality. Next, we propose a sub-optimal solution of lower complexity than the optimal solution, where zero-forcing (ZF) based precoding is implemented at the BSs. Finally, through extensive simulations, we show the performance gain achieved by our proposed joint energy trading and communication cooperation schemes in terms of energy cost reduction, as compared to conventional schemes that separately design communication cooperation and energy trading.
Efficient Synthesis of Network Updates
Venue: arXiv cs.PL 2015
Year: 2015

Software-defined networking (SDN) is revolutionizing the networking industry, but current SDN programming platforms do not provide automated mechanisms for updating global configurations on the fly. Implementing updates by hand is challenging for SDN programmers because networks are distributed systems with hundreds or thousands of interacting nodes. Even if initial and final configurations are correct, naively updating individual nodes can lead to incorrect transient behaviors, including loops, black holes, and access control violations. This paper presents an approach for automatically synthesizing updates that are guaranteed to preserve specified properties. We formalize network updates as a distributed programming problem and develop a synthesis algorithm based on counterexample-guided search and incremental model checking. We describe a prototype implementation, and present results from experiments on real-world topologies and properties demonstrating that our tool scales to updates involving over one-thousand nodes.
Analyzing Network Reliability Using Structural Motifs
Venue: arXiv cs.SI 2015
Year: 2015

This paper uses the reliability polynomial, introduced by Moore and Shannon in 1956, to analyze the effect of network structure on diffusive dynamics such as the spread of infectious disease. We exhibit a representation for the reliability polynomial in terms of what we call {\em structural motifs} that is well suited for reasoning about the effect of a network's structural properties on diffusion across the network. We illustrate by deriving several general results relating graph structure to dynamical phenomena.
A Mirage of Market Allocation
Venue: arXiv cs.GT 2015
Year: 2015

Can noncooperative behaviour of merchants lead to a market split that prima facie seems anticompetitive? We introduce a model in which service providers, with ISPs being the main example, aim at optimizing the number of customers using their services, while customers aim at choosing service providers with low customer load (high bandwidth per subscriber, for ISPs). Each service provider chooses between a variety of levels of service (latencies, for ISPs), and as long as it does not lose customers, aims at minimizing its level of service; the minimum level of service required to satisfy a customer varies across customers. We consider a two-stage competition: in the first stage, service providers select their levels of service; in the second stage, customers choose between service providers. In the two-stage game, we show that the competition among service providers possesses a unique Nash equilibrium, which is moreover super-strong; we also show that sequential better-response dynamics of service providers reach this equilibrium, with best-response dynamics doing so surprisingly fast. If service providers choose their levels of service according to this equilibrium, then the unique Nash equilibrium among customers in the second phase is a split of the market between the service providers, based on the customers' minimum acceptable quality of service; moreover, each service provider's chosen level of service is the lowest acceptable by the entirety of its market slice, seemingly making no attempt to attract other customers. Our results show that this prima facie market allocation (collusive split of the market) arises as the unique and highly robust outcome of noncooperative, even myopic, service-provider behaviour. These results are applicable to a wide variety of scenarios, from explaining phenomena observable in food markets, to shedding a surprising light on aspects of location theory.
A comparison of concepts from computable analysis and effective descriptive set theory
Venue: arXiv cs.LO 2015
Year: 2015

Computable analysis and effective descriptive set theory are both concerned with complete metric spaces, functions between them and subsets thereof in an effective setting. The precise relationship of the various definitions used in the two disciplines has so far been neglected, a situation this paper is meant to remedy. As the role of the Cauchy completion is relevant for both effective approaches to Polish spaces, we consider the interplay of effectivity and completion in some more detail.
Mental Disorder Recovery Correlated with Centralities and Interactions on an Online Social Network
Venue: arXiv cs.SI 2015
Year: 2015

Recent research has established both a theoretical basis and strong empirical evidence that effective social behavior plays a beneficial role in the maintenance of physical and psychological well-being of people. To test whether social behavior and well-being are also associated in online communities, we studied the correlations between the recovery of patients with mental disorders and their behaviors in online social media. As the source of the data related to the social behavior and progress of mental recovery, we used PatientsLikeMe (PLM), the world's first open-participation research platform for the development of patient-centered health outcome measures. We first constructed an online social network structure based on patient-to-patient ties among 200 patients obtained from PLM. We then characterized patients' online social activities by measuring the numbers of "posts and views" and "helpful marks" each patient obtained. The patients' recovery data were obtained from their self-reported status information that was also available on PLM. We found that some node properties (in-degree, eigenvector centrality and PageRank) and the two online social activity measures were significantly correlated with patients' recovery. Furthermore, we re-collected the patients' recovery data two months after the first data collection. We found significant correlations between the patients' social behaviors and the second recovery data, which were collected two months apart. Our results indicated that social interactions in online communities such as PLM were significantly associated with the current and future recoveries of patients with mental disorders.
Tighter Fourier Transform Complexity Tradeoffs
Venue: arXiv cs.CC 2015
Year: 2015

The Fourier Transform is one of the most important linear transformations used in science and engineering. Cooley and Tukey's Fast Fourier Transform (FFT) from 1964 is a method for computing this transformation in time $O(n\log n)$. Achieving a matching lower bound in a reasonable computational model is one of the most important open problems in theoretical computer science. In 2014, improving on his previous work, Ailon showed that if an algorithm speeds up the FFT by a factor of $b=b(n)\geq 1$, then it must rely on computing, as an intermediate "bottleneck" step, a linear mapping of the input with condition number $Ω(b(n))$. Our main result shows that a factor $b$ speedup implies existence of not just one but $Ω(n)$ $b$-ill conditioned bottlenecks occurring at $Ω(n)$ different steps, each causing information from independent (orthogonal) components of the input to either overflow or underflow. This provides further evidence that beating FFT is hard. Our result also gives the first quantitative tradeoff between computation speed and information loss in Fourier computation on fixed word size architectures. The main technical result is an entropy analysis of the Fourier transform under transformations of low trace, which is interesting in its own right.
Privacy Implications of Health Information Seeking on the Web
Venue: arXiv cs.CY 2015
Year: 2015

This article investigates privacy risks to those visiting health- related web pages. The population of pages analyzed is derived from the 50 top search results for 1,986 common diseases. This yielded a total population of 80,124 unique pages which were analyzed for the presence of third-party HTTP requests. 91% of pages were found to make requests to third parties. Investigation of URIs revealed that 70% of HTTP Referer strings contained information exposing specific conditions, treatments, and diseases. This presents a risk to users in the form of personal identification and blind discrimination. An examination of extant government and corporate policies reveals that users are insufficiently protected from such risks.