OpenRaiser/Intern-Atlas huggingface dataset:
Recognition of Emerging Technology Trends. Class-selective study of citations in the U.S. Patent Citation Network
Venue: arXiv cs.DL 2016
Year: 2016

By adopting a citation-based recursive ranking method for patents the evolution of new fields of technology can be traced. Specifically, it is demonstrated that the laser / inkjet printer technology emerged from the recombination of two existing technologies: sequential printing and static image production. The dynamics of the citations coming from the different "precursor" classes illuminates the mechanism of the emergence of new fields and give the possibility to make predictions about future technological development. For the patent network the optimal value of the PageRank damping factor is close to 0.5; the application of d=0.85 leads to unacceptable ranking results.
Practical Riemannian Neural Networks
Venue: arXiv cs.NE 2016
Year: 2016

We provide the first experimental results on non-synthetic datasets for the quasi-diagonal Riemannian gradient descents for neural networks introduced in [Ollivier, 2015]. These include the MNIST, SVHN, and FACE datasets as well as a previously unpublished electroencephalogram dataset. The quasi-diagonal Riemannian algorithms consistently beat simple stochastic gradient gradient descents by a varying margin. The computational overhead with respect to simple backpropagation is around a factor $2$. Perhaps more interestingly, these methods also reach their final performance quickly, thus requiring fewer training epochs and a smaller total computation time. We also present an implementation guide to these Riemannian gradient descents for neural networks, showing how the quasi-diagonal versions can be implemented with minimal effort on top of existing routines which compute gradients.
Recognizing Optimal 1-Planar Graphs in Linear Time
Venue: arXiv cs.DM 2016
Year: 2016

A graph with n vertices is 1-planar if it can be drawn in the plane such that each edge is crossed at most once, and is optimal if it has the maximum of 4n-8 edges. We show that optimal 1-planar graphs can be recognized in linear time. Our algorithm implements a graph reduction system with two rules, which can be used to reduce every optimal 1-planar graph to an irreducible extended wheel graph. The graph reduction system is non-deterministic, constraint, and non-confluent.
Improve Positioning Accuracy in WCDMA/FDD Networks Utilizing Adaptive Threshold for Direct Component Detection
Venue: arXiv cs.NI 2016
Year: 2016

In NLOS propagation conditions power of direct component can be attenuated significantly. Therefore detection of direct component is aggravated which can degrades accuracy of Time of Arrival mobile positioning. The goal of this paper is to determine possibilities to improve estimation of direct component time delay by reducing detection threshold. Three different methods for calculating threshold has been tested and compared in terms of positioning error.
Recognising Multidimensional Euclidean Preferences
Venue: arXiv cs.GT 2016
Year: 2016

Euclidean preferences are a widely studied preference model, in which decision makers and alternatives are embedded in d-dimensional Euclidean space. Decision makers prefer those alternatives closer to them. This model, also known as multidimensional unfolding, has applications in economics, psychometrics, marketing, and many other fields. We study the problem of deciding whether a given preference profile is d-Euclidean. For the one-dimensional case, polynomial-time algorithms are known. We show that, in contrast, for every other fixed dimension d > 1, the recognition problem is equivalent to the existential theory of the reals (ETR), and so in particular NP-hard. We further show that some Euclidean preference profiles require exponentially many bits in order to specify any Euclidean embedding, and prove that the domain of d-Euclidean preferences does not admit a finite forbidden minor characterisation for any d > 1. We also study dichotomous preferencesand the behaviour of other metrics, and survey a variety of related work.
Interference-Normalised Least Mean Square Algorithm
Venue: arXiv cs.SY 2016
Year: 2016

An interference-normalised least mean square (INLMS) algorithm for robust adaptive filtering is proposed. The INLMS algorithm extends the gradient-adaptive learning rate approach to the case where the signals are non-stationary. In particular, we show that the INLMS algorithm can work even for highly non-stationary interference signals, where previous gradient-adaptive learning rate algorithms fail.
Taming Limits with Approximate Networking
Venue: arXiv cs.NI 2016
Year: 2016

Internet is the linchpin of modern society, which the various threads of modern life weave around. But being a part of the bigger energy-guzzling industrial economy, it is vulnerable to disruption. It is widely believed that our society is exhausting its vital resources to meet our energy requirements, and the cheap fossil fuel fiesta will soon abate as we cross the tipping point of global oil production. We will then enter the long arc of scarcity, constraints, and limits---a post-peak "long emergency" that may subsist for a long time. To avoid the collapse of the networking ecosystem in this long emergency, it is imperative that we start thinking about how networking should adapt to these adverse "undeveloping" societal conditions. We propose using the idea of "\textit{approximate networking}"---which will provide \textit{good-enough} networking services by employing \textit{contextually-appropriate} tradeoffs---to survive, or even thrive, in the conditions of scarcity and limits.
Associative Memories and Human-Robot Social Interaction
Venue: arXiv cs.RO 2016
Year: 2016

In this position paper, we discuss how the use of a cognitive architecture based on unsupervised clustering (the Kohonen Self-Organizing Map) enables us to meet our goals of efficient action selection in a mobile robot. This architecture provides several opportunities for human-robot interaction, and we discuss how its features facilitate these interactions.
Streaming Verification of Graph Properties
Venue: arXiv cs.DS 2016
Year: 2016

Streaming interactive proofs (SIPs) are a framework for outsourced computation. A computationally limited streaming client (the verifier) hands over a large data set to an untrusted server (the prover) in the cloud and the two parties run a protocol to confirm the correctness of result with high probability. SIPs are particularly interesting for problems that are hard to solve (or even approximate) well in a streaming setting. The most notable of these problems is finding maximum matchings, which has received intense interest in recent years but has strong lower bounds even for constant factor approximations. In this paper, we present efficient streaming interactive proofs that can verify maximum matchings exactly. Our results cover all flavors of matchings (bipartite/non-bipartite and weighted). In addition, we also present streaming verifiers for approximate metric TSP. In particular, these are the first efficient results for weighted matchings and for metric TSP in any streaming verification model.
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Venue: arXiv cs.CC 2016
Year: 2016

Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model. Each result has a very compelling take-away message: 1. Fast $Δ$-coloring of trees requires random bits: Building on the recent lower bounds of Brandt et al., we prove that the randomized complexity of $Δ$-coloring a tree with maximum degree $Δ\ge 55$ is $Θ(\log_Δ\log n)$, whereas its deterministic complexity is $Θ(\log_Δn)$ for any $Δ\ge 3$. This also establishes a large separation between the deterministic complexity of $Δ$-coloring and $(Δ+1)$-coloring trees. 2. Randomized lower bounds imply deterministic lower bounds: We prove that any deterministic algorithm for a natural class of problems that runs in $O(1)+o(\log_Δn)$ rounds can be transformed to run in $O(\log^*n-\log^*Δ+1)$ rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires $Ω(\log_Δn)$ time deterministically. 3. Deterministic lower bounds imply randomized lower bounds: We prove that the randomized complexity of any natural problem on instances of size $n$ is at least its deterministic complexity on instances of size $\sqrt{\log n}$. This shows that a deterministic $Ω(\log_Δn)$ lower bound for any problem implies a randomized $Ω(\log_Δ\log n)$ lower bound. It also illustrates that the graph shattering technique is absolutely essential to the LOCAL model.
Theoretical Analysis of the $k$-Means Algorithm - A Survey
Venue: arXiv cs.DS 2016
Year: 2016

The $k$-means algorithm is one of the most widely used clustering heuristics. Despite its simplicity, analyzing its running time and quality of approximation is surprisingly difficult and can lead to deep insights that can be used to improve the algorithm. In this paper we survey the recent results in this direction as well as several extension of the basic $k$-means method.
Optimal Observation Mode Scheduling for Systems under Temporal Constraints
Venue: arXiv cs.LO 2016
Year: 2016

Autonomous control systems use various sensors to decrease the amount of uncertainty under which they operate. While providing partial observation of the current state of the system, sensors require resources such as energy, time and communication. We consider discrete systems with non-deterministic transitions and multiple observation modes. The observation modes provide different information about the states of the system and are associated with non-negative costs. We consider two control problems. First, we aim to construct a control and observation mode switching strategy that guarantees satisfaction of a finite-time temporal property given as a formula of syntactically co-safe fragment of LTL (scLTL) and at the same time, minimizes the worst-case cost accumulated until the point of satisfaction. Second, the bounded version of the problem is considered, where the temporal property must be satisfied within given finite time bound. We present correct and optimal solutions to both problems and demonstrate their usability on a case study motivated by robotic applications.
Bounded Rational Decision-Making in Feedforward Neural Networks
Venue: arXiv cs.AI 2016
Year: 2016

Bounded rational decision-makers transform sensory input into motor output under limited computational resources. Mathematically, such decision-makers can be modeled as information-theoretic channels with limited transmission rate. Here, we apply this formalism for the first time to multilayer feedforward neural networks. We derive synaptic weight update rules for two scenarios, where either each neuron is considered as a bounded rational decision-maker or the network as a whole. In the update rules, bounded rationality translates into information-theoretically motivated types of regularization in weight space. In experiments on the MNIST benchmark classification task for handwritten digits, we show that such information-theoretic regularization successfully prevents overfitting across different architectures and attains results that are competitive with other recent techniques like dropout, dropconnect and Bayes by backprop, for both ordinary and convolutional neural networks.
Remote Heart Rate Sensing and Projection to Renew Traditional Board Games and Foster Social Interactions
Venue: arXiv cs.HC 2016
Year: 2016

While physiological sensors enter the mass market and reach the general public, they are still mainly employed to monitor health -- whether it is for medical purpose or sports. We describe an application that uses heart rate feedback as an incentive for social interactions. A traditional board game has been "augmented" through remote physiological sensing, using webcams. Projection helped to conceal the technological aspects from users. We detail how players reacted -- stressful situations could emerge when users are deprived from their own signals -- and we give directions for game designers to integrate physiological sensors.
Approximation Complexity of Max-Cut on Power Law Graphs
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we study the MAX-CUT problem on power law graphs (PLGs) with power law exponent $β$. We prove some new approximability results on that problem. In particular we show that there exist polynomial time approximation schemes (PTAS) for MAX-CUT on PLGs for the power law exponent $β$ in the interval $(0,2)$. For $β>2$ we show that for some $ε>0$, MAX-CUT is NP-hard to approximate within approximation ratio $1+ε$, ruling out the existence of a PTAS in this case. Moreover we give an approximation algorithm with improved constant approximation ratio for the case of $β>2$.
Coordinate Update Algorithms for Robust Power Loading for the MU-MISO Downlink with Outage Constraints
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of power allocation for the single-cell multi-user (MU) multiple-input single-output (MISO) downlink with quality-of-service (QoS) constraints. The base station acquires an estimate of the channels and, for a given beamforming structure, designs the power allocation so as to minimize the total transmission power required to ensure that target signal-to-interference-and-noise ratios at the receivers are met, subject to a specified outage probability. We consider scenarios in which the errors in the base station's channel estimates can be modelled as being zero-mean and Gaussian. Such a model is particularly suitable for time division duplex (TDD) systems with quasi-static channels, in which the base station estimates the channel during the uplink phase. Under that model, we employ a precise deterministic characterization of the outage probability to transform the chance-constrained formulation to a deterministic one. Although that deterministic formulation is not convex, we develop a coordinate descent algorithm that can be shown to converge to a globally optimal solution when the starting point is feasible. Insight into the structure of the deterministic formulation yields approximations that result in coordinate update algorithms with good performance and significantly lower computational cost. The proposed algorithms provide better performance than existing robust power loading algorithms that are based on tractable conservative approximations, and can even provide better performance than robust precoding algorithms based on such approximations.
The Research Space: using the career paths of scholars to predict the evolution of the research output of individuals, institutions, and nations
Venue: arXiv cs.DL 2016
Year: 2016

In recent years scholars have built maps of science by connecting the academic fields that cite each other, are cited together, or that cite a similar literature. But since scholars cannot always publish in the fields they cite, or that cite them, these science maps are only rough proxies for the potential of a scholar, organization, or country, to enter a new academic field. Here we use a large dataset of scholarly publications disambiguated at the individual level to create a map of science-or research space-where links connect pairs of fields based on the probability that an individual has published in both of them. We find that the research space is a significantly more accurate predictor of the fields that individuals and organizations will enter in the future than citation based science maps. At the country level, however, the research space and citations based science maps are equally accurate. These findings show that data on career trajectories-the set of fields that individuals have previously published in-provide more accurate predictors of future research output for more focalized units-such as individuals or organizations-than citation based science maps.
Enabling Digital Health by Automatic Classification of Short Messages
Venue: arXiv cs.CY 2016
Year: 2016

In response to the growing HIV/AIDS and other health-related issues, UNICEF through their U-Report platform receives thousands of messages (SMS) every day to provide prevention strategies, health case advice, and counsel- ing support to vulnerable population. Due to a rapid increase in U-Report usage (up to 300% in last 3 years), plus approximately 1,000 new registrations each day, the volume of messages has thus continued to increase, which made it impossible for the team at UNICEF to process them in a timely manner. In this paper, we present a platform designed to perform automatic classification of short messages (SMS) in real-time to help UNICEF categorize and prioritize health-related messages as they arrive. We employ a hybrid approach, which combines human and machine intelligence that seeks to resolve the information overload issue by introducing processing of large-scale data at high-speed while maintaining a high classification accuracy. The system has recently been tested in conjunction with UNICEF in Zambia to classify short messages received via the U-Report platform on various health related issues. The system is designed to enable UNICEF make sense of a large volume of short messages in a timely manner. In terms of evaluation, we report design choices, challenges, and performance of the system observed during the deployment to validate its effectiveness.
Take up DNSSEC When Needed
Venue: arXiv cs.CR 2016
Year: 2016

The threats of caching poisoning attacks largely stimulate the deployment of DNSSEC. Being a strong but demanding cryptographical defense, DNSSEC has its universal adoption predicted to go through a lengthy transition. Thus the DNSSEC practitioners call for a secure yet lightweight solution to speed up DNSSEC deployment while offering an acceptable DNSSEC-like defense. This paper proposes a new defense against cache poisoning attacks, still using but lightly using DNSSEC. In the solution, DNS operates in the DNSSEC-oblivious mode unless a potential attack is detected and triggers a switch to the DNSSEC-aware mode. The performance of the defense is analyzed and validated. The modeling checking results demonstrate that only a small DNSSEC query load is needed to ensure a small enough cache poisoning success rate.
ExpSOS: Secure and Verifiable Outsourcing of Exponentiation Operations for Mobile Cloud Computing
Venue: arXiv cs.CR 2016
Year: 2016

Discrete exponential operation, such as modular exponentiation and scalar multiplication on elliptic curves, is a basic operation of many public-key cryptosystems. However, the exponential operations are considered prohibitively expensive for resource-constrained mobile devices. In this paper, we address the problem of secure outsourcing of exponentiation operations to one single untrusted server. Our proposed scheme (ExpSOS) only requires very limited number of modular multiplications at local mobile environment thus it can achieve impressive computational gain. ExpSOS also provides a secure verification scheme with probability approximately 1 to ensure that the mobile end-users can always receive valid results. The comprehensive analysis as well as the simulation results in real mobile device demonstrates that our proposed ExpSOS can significantly improve the existing schemes in efficiency, security and result verifiability. We apply ExpSOS to securely outsource several cryptographic protocols to show that ExpSOS is widely applicable to many cryptographic computations.
On the computational complexity of minimum-concave-cost flow in a two-dimensional grid
Venue: arXiv cs.DS 2016
Year: 2016

We study the minimum-concave-cost flow problem on a two-dimensional grid. We characterize the computational complexity of this problem based on the number of rows and columns of the grid, the number of different capacities over all arcs, and the location of sources and sinks. The concave cost over each arc is assumed to be evaluated through an oracle machine, i.e., the oracle machine returns the cost over an arc in a single computational step, given the flow value and the arc index. We propose an algorithm whose running time is polynomial in the number of columns of the grid, for the following cases: (1) the grid has a constant number of rows, a constant number of different capacities over all arcs, and sources and sinks in at most two rows; (2) the grid has two rows and a constant number of different capacities over all arcs connecting rows; (3) the grid has a constant number of rows and all sources in one row, with infinite capacity over each arc. These are presumably the most general polynomially solvable cases, since we show the problem becomes NP-hard when any condition in these cases is removed. Our results apply to abundant variants and generalizations of the dynamic lot sizing model, and answer several questions raised in serial supply chain optimization.
A Case for Time Slotted Channel Hopping for ICN in the IoT
Venue: arXiv cs.NI 2016
Year: 2016

Recent proposals to simplify the operation of the IoT include the use of Information Centric Networking (ICN) paradigms. While this is promising, several challenges remain. In this paper, our core contributions (a) leverage ICN communication patterns to dynamically optimize the use of TSCH (Time Slotted Channel Hopping), a wireless link layer technology increasingly popular in the IoT, and (b) make IoT-style routing adaptive to names, resources, and traffic patterns throughout the network--both without cross-layering. Through a series of experiments on the FIT IoT-LAB interconnecting typical IoT hardware, we find that our approach is fully robust against wireless interference, and almost halves the energy consumed for transmission when compared to CSMA. Most importantly, our adaptive scheduling prevents the time-slotted MAC layer from sacrificing throughput and delay.
Dijkstra Graphs
Venue: arXiv cs.DM 2016
Year: 2016

We revisit a concept that has been central in some early stages of computer science, that of structured programming: a set of rules that an algorithm must follow in order to acquire a structure that is desirable in many aspects. While much has been written about structured programming, an important issue has been left unanswered: given an arbitrary, compiled program, describe an algorithm to decide whether or not it is structured, that is, whether it conforms to the stated principles of structured programming. We refer to the classical concept of structured programming, as described by Dijkstra. By employing a graph model and graph-theoretic techniques, we formulate an efficient algorithm for answering this question. To do so, we first introduce the class of graphs which correspond to structured programs, which we call Dijkstra Graphs. Our problem then becomes the recognition of such graphs, for which we present a greedy $O(n)$-time algorithm. Furthermore, we describe an isomorphism algorithm for Dijkstra graphs, whose complexity is also linear in the number of vertices of the graph. Both the recognition and isomorphism algorithms have potential important applications, such as in code similarity analysis.