OpenRaiser/Intern-Atlas huggingface dataset:
Hierarchical Time-Dependent Oracles
Venue: arXiv cs.DS 2016
Year: 2016

We study networks obeying \emph{time-dependent} min-cost path metrics, and present novel oracles for them which \emph{provably} achieve two unique features: % (i) \emph{subquadratic} preprocessing time and space, \emph{independent} of the metric's amount of disconcavity; % (ii) \emph{sublinear} query time, in either the network size or the actual Dijkstra-Rank of the query at hand.
Radial Fuzzy Systems
Venue: arXiv cs.SY 2016
Year: 2016

The class of radial fuzzy systems is introduced. The fuzzy systems in this class use radial functions to implement membership functions of fuzzy sets and exhibit a shape preservation property in antecedents of their rules. The property is called the radial property. It enables the radial fuzzy systems to have their computational model mathematically tractable under both conjunctive and implicative representations of their rule bases. Coherence of radial implicative fuzzy systems is discussed and a sufficient condition for coherence is stated.
XFT: Practical Fault Tolerance Beyond Crashes
Venue: arXiv cs.DC 2016
Year: 2016

Despite years of intensive research, Byzantine fault-tolerant (BFT) systems have not yet been adopted in practice. This is due to additional cost of BFT in terms of resources, protocol complexity and performance, compared with crash fault-tolerance (CFT). This overhead of BFT comes from the assumption of a powerful adversary that can fully control not only the Byzantine faulty machines, but at the same time also the message delivery schedule across the entire network, effectively inducing communication asynchrony and partitioning otherwise correct machines at will. To many practitioners, however, such strong attacks appear irrelevant. In this paper, we introduce cross fault tolerance or XFT, a novel approach to building reliable and secure distributed systems and apply it to the classical state-machine replication (SMR) problem. In short, an XFT SMR protocol provides the reliability guarantees of widely used asynchronous CFT SMR protocols such as Paxos and Raft, but also tolerates Byzantine faults in combination with network asynchrony, as long as a majority of replicas are correct and communicate synchronously. This allows the development of XFT systems at the price of CFT (already paid for in practice), yet with strictly stronger resilience than CFT --- sometimes even stronger than BFT itself. As a showcase for XFT, we present XPaxos, the first XFT SMR protocol, and deploy it in a geo-replicated setting. Although it offers much stronger resilience than CFT SMR at no extra resource cost, the performance of XPaxos matches that of the state-of-the-art CFT protocols.
A partial taxonomy of judgment aggregation rules, and their properties
Venue: arXiv cs.AI 2016
Year: 2016

The literature on judgment aggregation is moving from studying impossibility results regarding aggregation rules towards studying specific judgment aggregation rules. Here we give a structured list of most rules that have been proposed and studied recently in the literature, together with various properties of such rules. We first focus on the majority-preservation property, which generalizes Condorcet-consistency, and identify which of the rules satisfy it. We study the inclusion relationships that hold between the rules. Finally, we consider two forms of unanimity, monotonicity, homogeneity, and reinforcement, and we identify which of the rules satisfy these properties.
Artificial-Noise-Aided Physical Layer Phase Challenge-Response Authentication for Practical OFDM Transmission
Venue: arXiv cs.IT 2016
Year: 2016

Recently, we have developed a PHYsical layer Phase Challenge-Response Authentication Scheme (PHY-PCRAS) for independent multicarrier transmission. In this paper, we make a further step by proposing a novel artificial-noise-aided PHY-PCRAS (ANA-PHY-PCRAS) for practical orthogonal frequency division multiplexing (OFDM) transmission, where the Tikhonov-distributed artificial noise is introduced to interfere with the phase-modulated key for resisting potential key-recovery attacks whenever a static channel between two legitimate users is unfortunately encountered. Then, we address various practical issues for ANA-PHY-PCRAS with OFDM transmission, including correlation among subchannels, imperfect carrier and timing recoveries. Among them, we show that the effect of sampling offset is very significant and a search procedure in the frequency domain should be incorporated for verification. With practical OFDM transmission, the number of uncorrelated subchannels is often not sufficient. Hence, we employ a time-separated approach for allocating enough subchannels and a modified ANA-PHY-PCRAS is proposed to alleviate the discontinuity of channel phase at far-separated time slots. Finally, the key equivocation is derived for the worst case scenario. We conclude that the enhanced security of ANA-PHY-PCRAS comes from the uncertainty of both the wireless channel and introduced artificial noise, compared to the traditional challenge-response authentication scheme implemented at the upper layer.
Joint Hybrid Backhaul and Access Links Design in Cloud-Radio Access Networks
Venue: arXiv cs.IT 2016
Year: 2016

The cloud-radio access network (CRAN) is expected to be the core network architecture for next generation mobile radio systems. In this paper, we consider the downlink of a CRAN formed of one central processor (the cloud) and several base-station (BS), where each BS is connected to the cloud via either a wireless or capacity-limited wireline backhaul link. The paper addresses the joint design of the hybrid backhaul links (i.e., designing the wireline and wireless backhaul connections from the cloud to the BSs) and the access links (i.e., determining the sparse beamforming solution from the BSs to the users). The paper formulates the hybrid backhaul and access link design problem by minimizing the total network power consumption. The paper solves the problem using a two-stage heuristic algorithm. At one stage, the sparse beamforming solution is found using a weighted mixed `1=`2 norm minimization approach; the correlation matrix of the quantization noise of the wireline backhaul links is computed using the classical rate-distortion theory. At the second stage, the transmit powers of the wireless backhaul links are found by solving a power minimization problem subject to quality-of-service constraints, based on the principle of conservation of rate by utilizing the rates found in the first stage. Simulation results suggest that the performance of the proposed algorithm approaches the global optimum solution, especially at high signal-to-interference-plus-noise ratio (SINR).
Influence Maximization with Bandits
Venue: arXiv cs.SI 2016
Year: 2016

We consider the problem of \emph{influence maximization}, the problem of maximizing the number of people that become aware of a product by finding the `best' set of `seed' users to expose the product to. Most prior work on this topic assumes that we know the probability of each user influencing each other user, or we have data that lets us estimate these influences. However, this information is typically not initially available or is difficult to obtain. To avoid this assumption, we adopt a combinatorial multi-armed bandit paradigm that estimates the influence probabilities as we sequentially try different seed sets. We establish bounds on the performance of this procedure under the existing edge-level feedback as well as a novel and more realistic node-level feedback. Beyond our theoretical results, we describe a practical implementation and experimentally demonstrate its efficiency and effectiveness on four real datasets.
Consistent Probabilistic Social Choice
Venue: arXiv cs.GT 2016
Year: 2016

Two fundamental axioms in social choice theory are consistency with respect to a variable electorate and consistency with respect to components of similar alternatives. In the context of traditional non-probabilistic social choice, these axioms are incompatible with each other. We show that in the context of probabilistic social choice, these axioms uniquely characterize a function proposed by Fishburn (Rev. Econ. Stud., 51(4), 683--692, 1984). Fishburn's function returns so-called maximal lotteries, i.e., lotteries that correspond to optimal mixed strategies of the underlying plurality game. Maximal lotteries are guaranteed to exist due to von Neumann's Minimax Theorem, are almost always unique, and can be efficiently computed using linear programming.
MODS: Fast and Robust Method for Two-View Matching
Venue: arXiv cs.CV 2016
Year: 2016

A novel algorithm for wide-baseline matching called MODS - Matching On Demand with view Synthesis - is presented. The MODS algorithm is experimentally shown to solve a broader range of wide-baseline problems than the state of the art while being nearly as fast as standard matchers on simple problems. The apparent robustness vs. speed trade-off is finessed by the use of progressively more time-consuming feature detectors and by on-demand generation of synthesized images that is performed until a reliable estimate of geometry is obtained. We introduce an improved method for tentative correspondence selection, applicable both with and without view synthesis. A modification of the standard first to second nearest distance rule increases the number of correct matches by 5-20% at no additional computational cost. Performance of the MODS algorithm is evaluated on several standard publicly available datasets, and on a new set of geometrically challenging wide baseline problems that is made public together with the ground truth. Experiments show that the MODS outperforms the state-of-the-art in robustness and speed. Moreover, MODS performs well on other classes of difficult two-view problems like matching of images from different modalities, with wide temporal baseline or with significant lighting changes.
Computing Heat Kernel Pagerank and a Local Clustering Algorithm
Venue: arXiv cs.DS 2016
Year: 2016

Heat kernel pagerank is a variation of Personalized PageRank given in an exponential formulation. In this work, we present a sublinear time algorithm for approximating the heat kernel pagerank of a graph. The algorithm works by simulating random walks of bounded length and runs in time $O\big(\frac{\log(ε^{-1})\log n}{ε^3\log\log(ε^{-1})}\big)$, assuming performing a random walk step and sampling from a distribution with bounded support take constant time. The quantitative ranking of vertices obtained with heat kernel pagerank can be used for local clustering algorithms. We present an efficient local clustering algorithm that finds cuts by performing a sweep over a heat kernel pagerank vector, using the heat kernel pagerank approximation algorithm as a subroutine. Specifically, we show that for a subset $S$ of Cheeger ratio $ϕ$, many vertices in $S$ may serve as seeds for a heat kernel pagerank vector which will find a cut of conductance $O(\sqrtϕ)$.
On definite program answers and least Herbrand models
Venue: arXiv cs.LO 2016
Year: 2016

A sufficient and necessary condition is given under which least Herbrand models exactly characterize the answers of definite clause programs. To appear in Theory and Practice of Logic Programming (TPLP).
An Improved Pseudo-Polynomial Upper Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games
Venue: arXiv cs.DS 2016
Year: 2016

In this work we offer an $O(|V|^2 |E|\, W)$ pseudo-polynomial time deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. This improves by a factor $\log(|V|\, W)$ the best previously known pseudo-polynomial time upper bound due to Brim,~\etal The improvement hinges on a suitable characterization of values, and a description of optimal positional strategies, in terms of reweighted Energy Games and Small Energy-Progress Measures.
A Monte Carlo Simulation Approach for Quantitatively Evaluating Keyboard Layouts for Gesture Input
Venue: arXiv cs.HC 2016
Year: 2016

Gesture typing is a method of text entry that is ergonomically well-suited to the form factor of touchscreen devices and allows for much faster input than tapping each letter individually. The QWERTY keyboard was, however, not designed with gesture input in mind and its particular layout results in a high frequency of gesture recognition errors. In this paper, we describe a new approach to quantifying the frequency of gesture input recognition errors through the use of modeling and simulating realistically imperfect user input. We introduce new methodologies for modeling randomized gesture inputs, efficiently reconstructing words from gestures on arbitrary keyboard layouts, and using these in conjunction with a frequency weighted lexicon to perform Monte Carlo evaluations of keyboard error rates or any other arbitrary metric. An open source framework, Dodona, is also provided that allows for these techniques to be easily employed and customized in the evaluation of a wide spectrum of possible keyboards and input methods. Finally, we perform an optimization procedure over permutations of the QWERTY keyboard to demonstrate the effectiveness of this approach and describe ways that future analyses can build upon these results.
Family of Controllers for Attitude Synchronization on the Sphere
Venue: arXiv cs.SY 2016
Year: 2016

In this paper we study a family of controllers that guarantees attitude synchronization for a network of elements in the unit sphere domain, i.e. $\mathcal{S}^2$. We propose distributed continuous controllers for elements whose dynamics are controllable (i.e. control with torque as command), and which can be implemented by each individual agent without the need of a common global orientation frame among the network, i.e. it requires only local information that can be measured by each individual agent from its own orientation frame. The controllers are specified according to arbitrary distance functions in $\mathcal{S}^2$, and we provide conditions on those distance functions that guarantee that i) a synchronized network of agents is locally asymptotically stable for an arbitrary network graph; ii) a synchronized network can be achieved for almost all initial conditions in a tree graph network. We also study the equilibria configurations that come with specific types of network graphs. The proposed strategies can be used in attitude synchronization of swarms of fully actuated rigid bodies, such as satellites.
Event-Triggered Control over Unreliable Networks Subject to Jamming Attacks
Venue: arXiv cs.SY 2016
Year: 2016

Event-triggered networked control of a linear dynamical system is investigated. Specifically, the dynamical system and the controller are assumed to be connected through a communication channel. State and control input information packets between the system and the controller are attempted to be exchanged over the network only at time instants when certain triggering conditions are satisfied. We provide a probabilistic characterization for the link failures which allows us to model random packet losses due to unreliability in transmissions as well as those caused by malicious jamming attacks. We obtain conditions for the almost sure stability of the closed-loop system, and we illustrate the efficacy of our approach with a numerical example.
ASPeRiX, a First Order Forward Chaining Approach for Answer Set Computing
Venue: arXiv cs.LO 2016
Year: 2016

The natural way to use Answer Set Programming (ASP) to represent knowledge in Artificial Intelligence or to solve a combinatorial problem is to elaborate a first order logic program with default negation. In a preliminary step this program with variables is translated in an equivalent propositional one by a first tool: the grounder. Then, the propositional program is given to a second tool: the solver. This last one computes (if they exist) one or many answer sets (stable models) of the program, each answer set encoding one solution of the initial problem. Until today, almost all ASP systems apply this two steps computation. In this article, the project ASPeRiX is presented as a first order forward chaining approach for Answer Set Computing. This project was amongst the first to introduce an approach of answer set computing that escapes the preliminary phase of rule instantiation by integrating it in the search process. The methodology applies a forward chaining of first order rules that are grounded on the fly by means of previously produced atoms. Theoretical foundations of the approach are presented, the main algorithms of the ASP solver ASPeRiX are detailed and some experiments and comparisons with existing systems are provided.
Recent advances on inconsistency indices for pairwise comparisons - a commentary
Venue: arXiv cs.AI 2016
Year: 2016

This paper recalls the definition of consistency for pairwise comparison matrices and briefly presents the concept of inconsistency index in connection to other aspects of the theory of pairwise comparisons. By commenting on a recent contribution by Koczkodaj and Szwarc, it will be shown that the discussion on inconsistency indices is far from being over, and the ground is still fertile for debates.
Secure two-party quantum computation for non-rational and rational settings
Venue: arXiv cs.CR 2016
Year: 2016

Since the negative result of Lo (Physical Review A, 1997), it has been left open whether there exist some functions that can be securely computed in two-party setting in quantum domain when one of the parties is malicious. In this paper, we for the first time, show that there are some functions for which secure two-party quantum computation is indeed possible for non-simultaneous channel model. This is in sharp contrast with the impossibility result of Ben -Or et al. (FOCS, 2006) in broadcast channel model. The functions we study are of two types - one is any function without an embedded XOR, and the other one is a particular function containing an embedded XOR. Contrary to classical solutions, security against adversaries with unbounded power of computation is achieved by the quantum protocols due to entanglement. Further, in the context of secure multi-party quantum computation, for the first time we introduce rational parties, each of whom tries to maximize its utility by obtaining the function output alone. We adapt our quantum protocols for both the above types of functions in rational setting to achieve fairness and strict Nash equilibrium.
Equivocations, Exponents and Second-Order Coding Rates under Various Rényi Information Measures
Venue: arXiv cs.IT 2016
Year: 2016

We evaluate the asymptotics of equivocations, their exponents as well as their second-order coding rates under various Rényi information measures. Specifically, we consider the effect of applying a hash function on a source and we quantify the level of non-uniformity and dependence of the compressed source from another correlated source when the number of copies of the sources is large. Unlike previous works that use Shannon information measures to quantify randomness, information or uniformity, we define our security measures in terms of a more general class of information measures--the Rényi information measures and their Gallager-type counterparts. A special case of these Rényi information measure is the class of Shannon information measures. We prove tight asymptotic results for the security measures and their exponential rates of decay. We also prove bounds on the second-order asymptotics and show that these bounds match when the magnitudes of the second-order coding rates are large. We do so by establishing new classes non-asymptotic bounds on the equivocation and evaluating these bounds using various probabilistic limit theorems asymptotically.
Performance measures for classification systems with rejection
Venue: arXiv cs.CV 2016
Year: 2016

Classifiers with rejection are essential in real-world applications where misclassifications and their effects are critical. However, if no problem specific cost function is defined, there are no established measures to assess the performance of such classifiers. We introduce a set of desired properties for performance measures for classifiers with rejection, based on which we propose a set of three performance measures for the evaluation of the performance of classifiers with rejection that satisfy the desired properties. The nonrejected accuracy measures the ability of the classifier to accurately classify nonrejected samples; the classification quality measures the correct decision making of the classifier with rejector; and the rejection quality measures the ability to concentrate all misclassified samples onto the set of rejected samples. From the measures, we derive the concept of relative optimality that allows us to connect the measures to a family of cost functions that take into account the trade-off between rejection and misclassification. We illustrate the use of the proposed performance measures on classifiers with rejection applied to synthetic and real-world data.
Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients
Venue: arXiv cs.LG 2016
Year: 2016

Nonlinear component analysis such as kernel Principle Component Analysis (KPCA) and kernel Canonical Correlation Analysis (KCCA) are widely used in machine learning, statistics and data analysis, but they can not scale up to big datasets. Recent attempts have employed random feature approximations to convert the problem to the primal form for linear computational complexity. However, to obtain high quality solutions, the number of random features should be the same order of magnitude as the number of data points, making such approach not directly applicable to the regime with millions of data points. We propose a simple, computationally efficient, and memory friendly algorithm based on the "doubly stochastic gradients" to scale up a range of kernel nonlinear component analysis, such as kernel PCA, CCA and SVD. Despite the \emph{non-convex} nature of these problems, our method enjoys theoretical guarantees that it converges at the rate $\tilde{O}(1/t)$ to the global optimum, even for the top $k$ eigen subspace. Unlike many alternatives, our algorithm does not require explicit orthogonalization, which is infeasible on big datasets. We demonstrate the effectiveness and scalability of our algorithm on large scale synthetic and real world datasets.