OpenRaiser/Intern-Atlas huggingface dataset:
Filtering Patent Maps for Visualization of Diversification Paths of Inventors and Organizations
Venue: arXiv cs.SI 2016
Year: 2016

In the information science literature, recent studies have used patent databases and patent classification information to construct network maps of patent technology classes. In such a patent technology map, almost all pairs of technology classes are connected, whereas most of the connections between them are extremely weak. This observation suggests the possibility of filtering the patent network map by removing weak links. However, removing links may reduce the explanatory power of the network on inventor or organization diversification. The network links may explain the patent portfolio diversification paths of inventors and inventing organizations. We measure the diversification explanatory power of the patent network map, and present a method to objectively choose an optimal trade-off between explanatory power and removing weak links. We show that this method can remove a degree of arbitrariness compared with previous filtering methods based on arbitrary thresholds, and also identify previous filtering methods that created filters outside the optimal trade-off. The filtered map aims to aid in network visualization analyses of the technological diversification of inventors, organizations and other innovation agents, and potential foresight analysis. Such applications to a prolific inventor (Leonard Forbes) and company (Google) are demonstrated.
Space-Efficient Plane-Sweep Algorithms
Venue: arXiv cs.DS 2016
Year: 2016

We introduce space-efficient plane-sweep algorithms for basic planar geometric problems. It is assumed that the input is in a read-only array of $n$ items and that the available workspace is $Θ(s)$ bits, where $\lg n \leq s \leq n \cdot \lg n$. Three techniques that can be used as general tools in different space-efficient algorithms are introduced and employed within our algorithms. In particular, we give an almost-optimal algorithm for finding the closest pair among a set of $n$ points that runs in $O(n^2/s + n \cdot \lg s)$ time. We also give a simple algorithm to enumerate the intersections of $n$ line segments that runs in $O((n^2/s^{2/3}) \cdot \lg s + k)$ time, where $k$ is the number of intersections. The counting version can be solved in $O((n^2/s^{2/3}) \cdot \lg s)$~time. When the segments are axis-parallel, we give an $O((n^2/s) \cdot \lg^{4/3} s + n^{4/3} \cdot \lg^{1/3} n)$-time algorithm for counting the intersections, and an algorithm for enumerating the intersections that runs in $O((n^2/s) \cdot \lg s \cdot \lg \lg s + n \cdot \lg s + k)$ time, where $k$ is the number of intersections. We finally present an algorithm that runs in $O((n^2/s + n \cdot \lg s) \cdot \sqrt{(n/s) \cdot \lg n})$ time to calculate Klee's measure of axis-parallel rectangles.
Distinguishing Hidden Markov Chains
Venue: arXiv cs.DS 2016
Year: 2016

Hidden Markov Chains (HMCs) are commonly used mathematical models of probabilistic systems. They are employed in various fields such as speech recognition, signal processing, and biological sequence analysis. We consider the problem of distinguishing two given HMCs based on an observation sequence that one of the HMCs generates. More precisely, given two HMCs and an observation sequence, a distinguishing algorithm is expected to identify the HMC that generates the observation sequence. Two HMCs are called distinguishable if for every $\varepsilon > 0$ there is a distinguishing algorithm whose error probability is less than $\varepsilon$. We show that one can decide in polynomial time whether two HMCs are distinguishable. Further, we present and analyze two distinguishing algorithms for distinguishable HMCs. The first algorithm makes a decision after processing a fixed number of observations, and it exhibits two-sided error. The second algorithm processes an unbounded number of observations, but the algorithm has only one-sided error. The error probability, for both algorithms, decays exponentially with the number of processed observations. We also provide an algorithm for distinguishing multiple HMCs. Finally, we discuss an application in stochastic runtime verification.
Online Algorithms for Multi-Level Aggregation
Venue: arXiv cs.DS 2016
Year: 2016

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4 2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We also show several additional lower and upper bound results for some special cases of MLAP, including the Single-Phase variant and the case when the tree is a path.
Optimized Compressed Sensing via Incoherent Frames Designed by Convex Optimization
Venue: arXiv cs.IT 2016
Year: 2016

The construction of highly incoherent frames, sequences of vectors placed on the unit hyper sphere of a finite dimensional Hilbert space with low correlation between them, has proven very difficult. Algorithms proposed in the past have focused in minimizing the absolute value off-diagonal entries of the Gram matrix of these structures. Recently, a method based on convex optimization that operates directly on the vectors of the frame has been shown to produce promising results. This paper gives a detailed analysis of the optimization problem at the heart of this approach and, based on these insights, proposes a new method that substantially outperforms the initial approach and all current methods in the literature for all types of frames, with low and high redundancy. We give extensive experimental results that show the effectiveness of the proposed method and its application to optimized compressed sensing.
Testing Shape Restrictions of Discrete Distributions
Venue: arXiv cs.DS 2016
Year: 2016

We study the question of testing structured properties (classes) of discrete distributions. Specifically, given sample access to an arbitrary distribution $D$ over $[n]$ and a property $\mathcal{P}$, the goal is to distinguish between $D\in\mathcal{P}$ and $\ell_1(D,\mathcal{P})>\varepsilon$. We develop a general algorithm for this question, which applies to a large range of "shape-constrained" properties, including monotone, log-concave, $t$-modal, piecewise-polynomial, and Poisson Binomial distributions. Moreover, for all cases considered, our algorithm has near-optimal sample complexity with regard to the domain size and is computationally efficient. For most of these classes, we provide the first non-trivial tester in the literature. In addition, we also describe a generic method to prove lower bounds for this problem, and use it to show our upper bounds are nearly tight. Finally, we extend some of our techniques to tolerant testing, deriving nearly-tight upper and lower bounds for the corresponding questions.
Energy Efficient Mobile Cloud Computing Powered by Wireless Energy Transfer (extended version)
Venue: arXiv cs.IT 2016
Year: 2016

Achieving long battery lives or even self sustainability has been a long standing challenge for designing mobile devices. This paper presents a novel solution that seamlessly integrates two technologies, mobile cloud computing and microwave power transfer (MPT), to enable computation in passive low-complexity devices such as sensors and wearable computing devices. Specifically, considering a single-user system, a base station (BS) either transfers power to or offloads computation from a mobile to the cloud; the mobile uses harvested energy to compute given data either locally or by offloading. A framework for energy efficient computing is proposed that comprises a set of policies for controlling CPU cycles for the mode of local computing, time division between MPT and offloading for the other mode of offloading, and mode selection. Given the CPU-cycle statistics information and channel state information (CSI), the policies aim at maximizing the probability of successfully computing given data, called computing probability, under the energy harvesting and deadline constraints. The policy optimization is translated into the equivalent problems of minimizing the mobile energy consumption for local computing and maximizing the mobile energy savings for offloading which are solved using convex optimization theory. The structures of the resultant policies are characterized in closed form. Furthermore, given non-causal CSI, the said analytical framework is further developed to support computation load allocation over multiple channel realizations, which further increases computing probability. Last, simulation demonstrates the feasibility of wirelessly powered mobile cloud computing and the gain of its optimal control.
Ordering with precedence constraints and budget minimization
Venue: arXiv cs.DM 2016
Year: 2016

We introduce a variation of the scheduling with precedence constraints problem that has applications to molecular folding and production management. We are given a bipartite graph $H=(B,S)$. Vertices in $B$ are thought of as goods or services that must be \emph{bought} to produce items in $S$ that are to be \emph{sold}. An edge from $j\in S$ to $i\in B$ indicates that the production of $j$ requires the purchase of $i$. Each vertex in $B$ has a cost, and each vertex in $S$ results in some gain. The goal is to obtain an ordering of $B\cup S$ that respects the precedence constraints and maximizes the minimal net profit encountered as the vertices are processed. We call this optimal value the \emph{budget} or \emph{capital} investment required for the bipartite graph, and refer to our problem as \emph{the bipartite graph ordering problem}. The problem is equivalent to a version of an NP-complete molecular folding problem that has been studied recently [12]. Work on the molecular folding problem has focused on heuristic algorithms and exponential-time exact algorithms for the un-weighted problem where costs are $\pm 1$ and when restricted to graphs arising from RNA folding. The bipartite graph present work seeks exact algorithms for solving the bipartite ordering problem. We demonstrate an algorithm that computes the optimal ordering in time $O^*(2^n)$ when $n$ is the number of vertices in the input bipartite graph. Our main result is a general strategy that can be used to find an optimal ordering in polynomial time for bipartite graphs that satisfy certain properties. We apply the technique to a variety of graph classes, obtaining polynomial-time solutions to the bipartite graph ordering problem for bipartite permutation graphs, trivially perfect, co-bipartite graphs, and trees.
Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program
Venue: arXiv cs.DS 2016
Year: 2016

We give a lower bound of $\tildeΩ(\sqrt{n})$ for the degree-4 Sum-of-Squares SDP relaxation for the planted clique problem. Specifically, we show that on an Erdös-Rényi graph $G(n,\tfrac{1}{2})$, with high probability there is a feasible point for the degree-4 SOS relaxation of the clique problem with an objective value of $\tildeΩ(\sqrt{n})$, so that the program cannot distinguish between a random graph and a random graph with a planted clique of size $\tilde{O}(\sqrt{n})$. This bound is tight. We build on the works of Deshpande and Montanari and Meka et al., who give lower bounds of $\tildeΩ(n^{1/3})$ and $\tildeΩ(n^{1/4})$ respectively. We improve on their results by making a perturbation to the SDP solution proposed in their work, then showing that this perturbation remains PSD as the objective value approaches $\tildeΩ(n^{1/2})$. In an independent work, Hopkins, Kothari and Potechin [HKP15] have obtained a similar lower bound for the degree-$4$ SOS relaxation.
Interception in Distance-Vector Routing Networks
Venue: arXiv cs.CR 2016
Year: 2016

Despite the large effort devoted to cybersecurity research over the last decades, cyber intrusions and attacks are still increasing. With respect to routing networks, route hijacking has highlighted the need to reexamine the existing protocols that govern traffic routing. In particular, our pri- mary question is how the topology of a network affects the susceptibility of a routing protocol to endogenous route misdirection. In this paper we define and analyze an abstract model of traffic interception (i.e. eavesdropping) in distance-vector routing networks. Specifically, we study al- gorithms that measure the potential of groups of dishonest agents to divert traffic through their infrastructure under the constraint that messages must reach their intended destinations. We relate two variants of our model based on the allowed kinds of lies, define strategies for colluding agents, and prove optimality in special cases. In our main theorem we derive a provably optimal monitoring strategy for subsets of agents in which no two are adjacent, and we extend this strategy to the general case. Finally, we use our results to analyze the susceptibility of real and synthetic networks to endogenous traffic interception. In the Autonomous Systems (AS) graph of the United States, we show that compromising only 18 random nodes in the AS graph surprisingly captures 10% of all traffic paths in the network in expectation when a distance-vector routing protocol is in use.
I/Q-Imbalance Self-Interference Coordination
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we present a novel low-complexity scheme, which improves the performance of single-antenna multi-carrier communication systems, suffering from in-phase and quadrature (I/Q)-imbalance (IQI) at the receiver. We refer to the proposed scheme as I/Q-imbalance self-interference coordination (IQSC). IQSC does not only mitigate the detrimental effects of IQI, but, through appropriate signal processing, also coordinates the self-interference terms produced by IQI in order to achieve second-order frequency diversity. However, these benefits come at the expense of a reduction in transmission rate. More specifically, IQSC is a simple transmit diversity scheme that improves the signal quality at the receiver by elementary signal processing operations across symmetric (mirror) pairs of subcarriers. Thereby, the proposed transmission protocol has a similar complexity as Alamouti's space-time block coding scheme and does not require extra transmit power nor any feedback. To evaluate the performance of IQSC, we derive closed-form expressions for the resulting outage probability and symbol error rate. Interestingly, IQSC outperforms not only existing IQI compensation schemes but also the ideal system without IQI for the same spectral efficiency and practical target error rates, while it achieves almost the same performance as ideal (i.e., IQI-free) equal-rate repetition coding. Our findings reveal that IQSC is a promising low-complexity technique for significantly increasing the reliability of low-cost devices that suffer from high levels of IQI.
Analyzing research performance: proposition of a new complementary index
Venue: arXiv cs.DL 2016
Year: 2016

A researcher collaborating with many groups will normally have more papers (and thus higher citations and $h$-index) than a researcher spending all his/her time working alone or in a small group. While analyzing an author's research merit, it is therefore not enough to consider only the collective impact of the published papers, it is also necessary to quantify his/her share in the impact. For this quantification, here I propose the $I$-index which is defined as an author's percentage share in the total citations that his/her papers have attracted. It is argued that this $I$-index does not directly depend on the most of the subjective issues like an author's influence, affiliation, seniority or career break. A simple application of the Central Limit Theorem shows that, the scheme of equidistribution of credit among the coauthors of a paper will give us the most probable value of the $I$-index (with an associated small standard deviation which decreases with increasing $h$-index). I show that the total citations ($N_c$), the $h$-index and the $I$-index are three independent parameters (within their bounds), and together they give a comprehensive idea of an author's overall research performance.
Analysis of an offloading scheme for data centers in the framework of fog computing
Venue: arXiv cs.NI 2016
Year: 2016

In the context of fog computing, we consider a simple case when data centers are installed at the edge of the network and assume that if a request arrives at an overloaded data center, then it is forwarded to a neighboring data center with some probability. Data centers are assumed to have a large number of servers and that traffic at some of them is causing saturation. In this case the other data centers may help to cope with this saturation regime by accepting some of the rejected requests. Our aim is to qualitatively estimate the gain achieved via cooperation between neighboring data centers. After proving some convergence results, related to the scaling limits of loss systems, for the process describing the number of free servers at both data centers, we show that the performance of the system can be expressed in terms of the invariant distribution of a random walk in the quarter plane. By using and developing existing results in the technical literature, explicit formulas for the blocking rates of such a system are derived.
Noisy Rumor Spreading and Plurality Consensus
Venue: arXiv cs.DC 2016
Year: 2016

Error-correcting codes are efficient methods for handling \emph{noisy} communication channels in the context of technological networks. However, such elaborate methods differ a lot from the unsophisticated way biological entities are supposed to communicate. Yet, it has been recently shown by Feinerman, Haeupler, and Korman {[}PODC 2014{]} that complex coordination tasks such as \emph{rumor spreading} and \emph{majority consensus} can plausibly be achieved in biological systems subject to noisy communication channels, where every message transferred through a channel remains intact with small probability $\frac{1}{2}+ε$, without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has been nevertheless be established only in the case of 2-valued \emph{opinions}: rumor spreading aims at broadcasting a single-bit opinion to all nodes, and majority consensus aims at leading all nodes to adopt the single-bit opinion that was initially present in the system with (relative) majority. In this paper, we extend this previous work to $k$-valued opinions, for any $k\geq2$. Our extension requires to address a series of important issues, some conceptual, others technical. We had to entirely revisit the notion of noise, for handling channels carrying $k$-\emph{valued} messages. In fact, we precisely characterize the type of noise patterns for which plurality consensus is solvable. Also, a key result employed in the bivalued case by Feinerman et al. is an estimate of the probability of observing the most frequent opinion from observing the mode of a small sample. We generalize this result to the multivalued case by providing a new analytical proof for the bivalued case that is amenable to be extended, by induction, and that is of independent interest.
Efficient Dodgson-Score Calculation Using Heuristics and Parallel Computing
Venue: arXiv cs.AI 2016
Year: 2016

Conflict of interest is the permanent companion of any population of agents (computational or biological). For that reason, the ability to compromise is of paramount importance, making voting a key element of societal mechanisms. One of the voting procedures most often discussed in the literature and, due to its intuitiveness, also conceptually quite appealing is Charles Dodgson's scoring rule, basically using the respective closeness to being a Condorcet winner for evaluating competing alternatives. In this paper, we offer insights on the practical limits of algorithms computing the exact Dodgson scores from a number of votes. While the problem itself is theoretically intractable, this work proposes and analyses five different solutions which try distinct approaches to practically solve the issue in an effective manner. Additionally, three of the discussed procedures can be run in parallel which has the potential of drastically reducing the problem size.
Towards a Better Understanding of CAR, CDR, CADR and the Others
Venue: arXiv cs.AI 2016
Year: 2016

This paper describes the IBM 704 architecture and the genesis of the names for CAR, and CDR, which, as it turns out, probably don't quite make sense. The paper suggests that this may not be all bad, as the names lend themselves to compounding. Indeed that the compound function names , such as CADR, or even CADADR, etc. may be read as little access programs.
A generalization of majorization that characterizes Shannon entropy
Venue: arXiv cs.IT 2016
Year: 2016

We introduce a binary relation on the finite discrete probability distributions which generalizes notions of majorization that have been studied in quantum information theory. Motivated by questions in thermodynamics, our relation describes the transitions induced by bistochastic maps in the presence of additional auxiliary systems which may become correlated in the process. We show that this relation is completely characterized by Shannon entropy H, which yields an interpretation of H in resource-theoretic terms, and admits a particularly simple proof of a known characterization of H in terms of natural information-theoretic properties.
On the Problem of Optimal Path Encoding for Software-Defined Networks
Venue: arXiv cs.NI 2016
Year: 2016

Packet networks need to maintain state in the form of forwarding tables at each switch. The cost of this state increases as networks support ever more sophisticated per-flow routing, traffic engineering, and service chaining. Per-flow or per-path state at the switches can be eliminated by encoding each packet's desired path in its header. A key component of such a method is an efficient encoding of paths through the network. We introduce a mathematical formulation of this optimal path-encoding problem. We prove that the problem is APX-hard, by showing that approximating it to within a factor less than 8/7 is NP-hard. Thus, at best we can hope for a constant-factor approximation algorithm. We then present such an algorithm, approximating the optimal path-encoding problem to within a factor 2. Finally, we provide empirical results illustrating the effectiveness of the proposed algorithm.