OpenRaiser/Intern-Atlas huggingface dataset:
The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm
Venue: arXiv cs.DS 2017
Year: 2017

In the stochastic matching problem, we are given a general (not necessarily bipartite) graph $G(V,E)$, where each edge in $E$ is realized with some constant probability $p > 0$ and the goal is to compute a bounded-degree (bounded by a function depending only on $p$) subgraph $H$ of $G$ such that the expected maximum matching size in $H$ is close to the expected maximum matching size in $G$. The algorithms in this setting are considered non-adaptive as they have to choose the subgraph $H$ without knowing any information about the set of realized edges in $G$. Originally motivated by an application to kidney exchange, the stochastic matching problem and its variants have received significant attention in recent years. The state-of-the-art non-adaptive algorithms for stochastic matching achieve an approximation ratio of $\frac{1}{2}-ε$ for any $ε> 0$, naturally raising the question that if $1/2$ is the limit of what can be achieved with a non-adaptive algorithm. In this work, we resolve this question by presenting the first algorithm for stochastic matching with an approximation guarantee that is strictly better than $1/2$: the algorithm computes a subgraph $H$ of $G$ with the maximum degree $O(\frac{\log{(1/ p)}}{p})$ such that the ratio of expected size of a maximum matching in realizations of $H$ and $G$ is at least $1/2+δ_0$ for some absolute constant $δ_0 > 0$. The degree bound on $H$ achieved by our algorithm is essentially the best possible (up to an $O(\log{(1/p)})$ factor) for any constant factor approximation algorithm, since an $Ω(\frac{1}{p})$ degree in $H$ is necessary for a vertex to acquire at least one incident edge in a realization.
Formal Computational Unlinkability Proofs of RFID Protocols
Venue: arXiv cs.CR 2017
Year: 2017

We set up a framework for the formal proofs of RFID protocols in the computational model. We rely on the so-called computationally complete symbolic attacker model. Our contributions are: i) To design (and prove sound) axioms reflecting the properties of hash functions (Collision-Resistance, PRF); ii) To formalize computational unlinkability in the model; iii) To illustrate the method, providing the first formal proofs of unlinkability of RFID protocols, in the computational model.
Consistent Sensor, Relay, and Link Selection in Wireless Sensor Networks
Venue: arXiv cs.IT 2017
Year: 2017

In wireless sensor networks, where energy is scarce, it is inefficient to have all nodes active because they consume a non-negligible amount of battery. In this paper we consider the problem of jointly selecting sensors, relays and links in a wireless sensor network where the active sensors need to communicate their measurements to one or multiple access points. Information messages are routed stochastically in order to capture the inherent reliability of the broadcast links via multiple hops, where the nodes may be acting as sensors or as relays. We aim at finding optimal sparse solutions where both, the consistency between the selected subset of sensors, relays and links, and the graph connectivity in the selected subnetwork are guaranteed. Furthermore, active nodes should ensure a network performance in a parameter estimation scenario. Two problems are studied: sensor and link selection; and sensor, relay and link selection. To solve such problems, we present tractable optimization formulations and propose two algorithms that satisfy the previous network requirements. We also explore an extension scenario: only link selection. Simulation results show the performance of the algorithms and illustrate how they provide a sparse solution, which not only saves energy but also guarantees the network requirements.
Efficient Parallel Strategy Improvement for Parity Games
Venue: arXiv cs.DS 2017
Year: 2017

We study strategy improvement algorithms for solving parity games. While these algorithms are known to solve parity games using a very small number of iterations, experimental studies have found that a high step complexity causes them to perform poorly in practice. In this paper we seek to address this situation. Every iteration of the algorithm must compute a best response, and while the standard way of doing this uses the Bellman-Ford algorithm, we give experimental results that show that one-player strategy improvement significantly outperforms this technique in practice. We then study the best way to implement one-player strategy improvement, and we develop an efficient parallel algorithm for carrying out this task, by reducing the problem to computing prefix sums on a linked list. We report experimental results for these algorithms, and we find that a GPU implementation of this algorithm shows a significant speedup over single-core and multi-core CPU implementations.
Fairness Incentives for Myopic Agents
Venue: arXiv cs.GT 2017
Year: 2017

We consider settings in which we wish to incentivize myopic agents (such as Airbnb landlords, who may emphasize short-term profits and property safety) to treat arriving clients fairly, in order to prevent overall discrimination against individuals or groups. We model such settings in both classical and contextual bandit models in which the myopic agents maximize rewards according to current empirical averages, but are also amenable to exogenous payments that may cause them to alter their choices. Our notion of fairness asks that more qualified individuals are never (probabilistically) preferred over less qualified ones [Joseph et al]. We investigate whether it is possible to design inexpensive {subsidy} or payment schemes for a principal to motivate myopic agents to play fairly in all or almost all rounds. When the principal has full information about the state of the myopic agents, we show it is possible to induce fair play on every round with a subsidy scheme of total cost $o(T)$ (for the classic setting with $k$ arms, $\tilde{O}(\sqrt{k^3T})$, and for the $d$-dimensional linear contextual setting $\tilde{O}(d\sqrt{k^3 T})$). If the principal has much more limited information (as might often be the case for an external regulator or watchdog), and only observes the number of rounds in which members from each of the $k$ groups were selected, but not the empirical estimates maintained by the myopic agent, the design of such a scheme becomes more complex. We show both positive and negative results in the classic and linear bandit settings by upper and lower bounding the cost of fair subsidy schemes.
Weights at the Bottom Matter When the Top is Heavy
Venue: arXiv cs.CC 2017
Year: 2017

Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the size of THR of MAJ circuits were shown by Razborov and Sherstov (SIAM J.Comput., 2010) even for computing functions in depth-3 AC^0. Yet, no separation among the two depth-2 threshold circuit classes were known. In fact, it is not clear a priori that they ought to be different. In particular, Goldmann, Hastad and Razborov (Computational Complexity, 1992) showed that the class MAJ of MAJ is identical to the class MAJ of THR. In this work, we provide an exponential separation between THR of MAJ and THR of THR. We achieve this by showing a function f that is computed by linear size THR of THR circuits and yet has exponentially large sign rank. This, by a well-known result, implies that f requires exponentially large THR of MAJ circuits to be computed. Our result suggests that the sign rank method alone is unlikely to prove strong lower bounds against THR of THR circuits. The main technical ingredient of our work is to prove a strong sign rank lower bound for an XOR function. This requires novel use of approximation theoretic tools.
Group Marching Tree: Sampling-Based Approximately Optimal Motion Planning on GPUs
Venue: arXiv cs.RO 2017
Year: 2017

This paper presents a novel approach, named the Group Marching Tree (GMT*) algorithm, to planning on GPUs at rates amenable to application within control loops, allowing planning in real-world settings via repeated computation of near-optimal plans. GMT*, like the Fast Marching Tree (FMT) algorithm, explores the state space with a "lazy" dynamic programming recursion on a set of samples to grow a tree of near-optimal paths. GMT*, however, alters the approach of FMT with approximate dynamic programming by expanding, in parallel, the group of all active samples with cost below an increasing threshold, rather than only the minimum cost sample. This group approximation enables low-level parallelism over the sample set and removes the need for sequential data structures, while the "lazy" collision checking limits thread divergence---all contributing to a very efficient GPU implementation. While this approach incurs some suboptimality, we prove that GMT* remains asymptotically optimal up to a constant multiplicative factor. We show solutions for complex planning problems under differential constraints can be found in ~10 ms on a desktop GPU and ~30 ms on an embedded GPU, representing a significant speed up over the state of the art, with only small losses in performance. Finally, we present a scenario demonstrating the efficacy of planning within the control loop (~100 Hz) towards operating in dynamic, uncertain settings.
Quantum Security of Cryptographic Primitives
Venue: arXiv cs.CR 2017
Year: 2017

We call quantum security the area of IT security dealing with scenarios where one or more parties have access to quantum hardware. This encompasses both the fields of post-quantum cryptography (that is, traditional cryptography engineered to be resistant against quantum adversaries), and quantum cryptography (that is, security protocols designed to be natively run on a quantum infrastructure, such as quantum key distribution). In this work, we propose the first systematic classification of quantum security scenarios, and for each of them we recall the main tools and results, as well as presenting new ones. We achieve this goal by identifying four distinct quantum security classes, or domains, each of them encompassing the security notions and constructions related to a particular scenario. We start with the class QS0, which is `classical cryptography' (meaning that no quantum scenario is considered). Regarding post-quantum cryptography, we introduce the class QS1, where we discuss in detail the problems arising when designing a classical cryptographic object meant to be resistant against adversaries with local quantum computing power, and we provide a classification of the possible quantum security reductions in this scenario when considering provable security. In respect to hybrid classical-quantum models, in the security class QS2 we discuss in detail the possible scenarios where these scenarios arise, and what a correct formalization should be in terms of quantum oracle access. Finally, in the class QS3 we consider all those cryptographic constructions designed to run natively on quantum hardware. We believe that the framework we introduce in this work will be a valuable tool for the scientific community in addressing the challenges arising when formalizing sound constructions and notions of security in the quantum world.
On Discrete Conformal Seamless Similarity Maps
Venue: arXiv cs.GR 2017
Year: 2017

An algorithm for the computation of global discrete conformal parametrizations with prescribed global holonomy signatures for triangle meshes was recently described in [Campen and Zorin 2017]. In this paper we provide a detailed analysis of convergence and correctness of this algorithm. We generalize and extend ideas of [Springborn et al. 2008] to show a connection of the algorithm to Newton's algorithm applied to solving the system of constraints on angles in the parametric domain, and demonstrate that this system can be obtained as a gradient of a convex energy.
Interface and Data Biopolitics in the Age of Hyperconnectivity
Venue: arXiv cs.CY 2017
Year: 2017

This article describes their biopolitical implications for design from psychological, cultural, legal, functional and aesthetic/perceptive ways, in the framework of Hyperconnectivity: the condition according to which person-to-person, person-to-machine and machine-to-machine communication progressively shift to networked and digital means. A definition is given for the terms of "interface biopolitics" and "data biopolitics", as well as evidence supporting these definitions and a description of the technological, theoretical and practice-based innovations bringing them into meaningful existence. Interfaces, algorithms, artificial intelligences of various types, the tendency in quantified self and the concept of "information bubbles" will be examined in terms of interface and data biopolitics, from the point of view of design, and for their implications in terms of freedoms, transparency, justice and accessibility to human rights. A working hypothesis is described for technologically relevant design practices and education processes, in order to confront with these issues in critical, ethical and inclusive ways.
A Generative Model of a Pronunciation Lexicon for Hindi
Venue: arXiv cs.CL 2017
Year: 2017

Voice browser applications in Text-to- Speech (TTS) and Automatic Speech Recognition (ASR) systems crucially depend on a pronunciation lexicon. The present paper describes the model of pronunciation lexicon of Hindi developed to automatically generate the output forms of Hindi at two levels, the <phoneme> and the <PS> (PS, in short for Prosodic Structure). The latter level involves both syllable-division and stress placement. The paper describes the tool developed for generating the two-level outputs of lexica in Hindi.
PANFIS++: A Generalized Approach to Evolving Learning
Venue: arXiv cs.AI 2017
Year: 2017

The concept of evolving intelligent system (EIS) provides an effective avenue for data stream mining because it is capable of coping with two prominent issues: online learning and rapidly changing environments. We note at least three uncharted territories of existing EISs: data uncertainty, temporal system dynamic, redundant data streams. This book chapter aims at delivering a concrete solution of this problem with the algorithmic development of a novel learning algorithm, namely PANFIS++. PANFIS++ is a generalized version of the PANFIS by putting forward three important components: 1) An online active learning scenario is developed to overcome redundant data streams. This module allows to actively select data streams for the training process, thereby expediting execution time and enhancing generalization performance, 2) PANFIS++ is built upon an interval type-2 fuzzy system environment, which incorporates the so-called footprint of uncertainty. This component provides a degree of tolerance for data uncertainty. 3) PANFIS++ is structured under a recurrent network architecture with a self-feedback loop. This is meant to tackle the temporal system dynamic. The efficacy of the PANFIS++ has been numerically validated through numerous real-world and synthetic case studies, where it delivers the highest predictive accuracy while retaining the lowest complexity.
Exploring Latent Semantic Factors to Find Useful Product Reviews
Venue: arXiv cs.AI 2017
Year: 2017

Online reviews provided by consumers are a valuable asset for e-Commerce platforms, influencing potential consumers in making purchasing decisions. However, these reviews are of varying quality, with the useful ones buried deep within a heap of non-informative reviews. In this work, we attempt to automatically identify review quality in terms of its helpfulness to the end consumers. In contrast to previous works in this domain exploiting a variety of syntactic and community-level features, we delve deep into the semantics of reviews as to what makes them useful, providing interpretable explanation for the same. We identify a set of consistency and semantic factors, all from the text, ratings, and timestamps of user-generated reviews, making our approach generalizable across all communities and domains. We explore review semantics in terms of several latent factors like the expertise of its author, his judgment about the fine-grained facets of the underlying product, and his writing style. These are cast into a Hidden Markov Model -- Latent Dirichlet Allocation (HMM-LDA) based model to jointly infer: (i) reviewer expertise, (ii) item facets, and (iii) review helpfulness. Large-scale experiments on five real-world datasets from Amazon show significant improvement over state-of-the-art baselines in predicting and ranking useful reviews.
A Decentralized Framework for Real-Time Energy Trading in Distribution Networks with Load and Generation Uncertainty
Venue: arXiv cs.SY 2017
Year: 2017

The proliferation of small-scale renewable generators and price-responsive loads makes it a challenge for distribution network operators (DNOs) to schedule the controllable loads of the load aggregators and the generation of the generators in real-time. Additionally, the high computational burden and violation of the entities' (i.e., load aggregators' and generators') privacy make a centralized framework impractical. In this paper, we propose a decentralized energy trading algorithm that can be executed by the entities in a real-time fashion. To address the privacy issues, the DNO provides the entities with proper control signals using the Lagrange relaxation technique to motivate them towards an operating point with maximum profit for entities. To deal with uncertainty issues, we propose a probabilistic load model and robust framework for renewable generation. The performance of the proposed algorithm is evaluated on an IEEE 123-node test feeder. When compared with a benchmark of not performing load management for the aggregators, the proposed algorithm benefits both the load aggregators and generators by increasing their profit by 17.8%and 10.3%, respectively. When compared with a centralized approach, our algorithm converges to the solution of the DNO's centralized problem with a significantly lower running time in 50 iterations per time slot.
Reliable Restricted Process Theory
Venue: arXiv cs.LO 2017
Year: 2017

Malfunctions of a mobile ad hoc network (MANET) protocol caused by a conceptual mistake in the protocol design, rather than unreliable communication, can often be detected only by considering communication among the nodes in the network to be reliable. In Restricted Broadcast Process Theory, which was developed for the specification and verification of MANET protocols, the communication operator is lossy. Replacing unreliable with reliable communication invalidates existing results for this process theory. We examine the effects of this adaptation on the semantics of the framework with regard to the non-blocking property of communication in MANETs, the notion of behavioral equivalence relation and its axiomatization. We illustrate the applicability of our framework through a simple routing protocol. To prove its correctness, we introduce a novel proof process, based on a precongruence relation.
Static Timing Model Extraction for Combinational Circuits
Venue: arXiv cs.AR 2017
Year: 2017

For large circuits, static timing analysis (STA) needs to be performed in a hierarchical manner to achieve higher performance in arrival time propagation. In hierarchical STA, efficient and accurate timing models of sub-modules need to be created. We propose a timing model extraction method that significantly reduces the size of timing models without losing any accuracy by removing redundant timing information. Circuit components which do not contribute to the delay of any input to output pair are removed. The proposed method is deterministic. Compared to the original models, the numbers of edges and vertices of the resulting timing models are reduced by 84% and 85% on average, respectively, which are significantly more than the results achieved by other methods.
DropIn: Making Reservoir Computing Neural Networks Robust to Missing Inputs by Dropout
Venue: arXiv cs.LG 2017
Year: 2017

The paper presents a novel, principled approach to train recurrent neural networks from the Reservoir Computing family that are robust to missing part of the input features at prediction time. By building on the ensembling properties of Dropout regularization, we propose a methodology, named DropIn, which efficiently trains a neural model as a committee machine of subnetworks, each capable of predicting with a subset of the original input features. We discuss the application of the DropIn methodology in the context of Reservoir Computing models and targeting applications characterized by input sources that are unreliable or prone to be disconnected, such as in pervasive wireless sensor networks and ambient intelligence. We provide an experimental assessment using real-world data from such application domains, showing how the Dropin methodology allows to maintain predictive performances comparable to those of a model without missing features, even when 20\%-50\% of the inputs are not available.
Identifying the social signals that drive online discussions: A case study of Reddit communities
Venue: arXiv cs.SI 2017
Year: 2017

Increasingly people form opinions based on information they consume on online social media. As a result, it is crucial to understand what type of content attracts people's attention on social media and drive discussions. In this paper we focus on online discussions. Can we predict which comments and what content gets the highest attention in an online discussion? How does this content differ from community to community? To accomplish this, we undertake a unique study of Reddit involving a large sample comments from 11 popular subreddits with different properties. We introduce a large number of sentiment, relevance, content analysis features including some novel features customized to reddit. Through a comparative analysis of the chosen subreddits, we show that our models are correctly able to retrieve top replies under a post with great precision. In addition, we explain our findings with a detailed analysis of what distinguishes high scoring posts in different communities that differ along the dimensions of the specificity of topic and style, audience and level of moderation.
Spatiotemporal Recurrent Convolutional Networks for Traffic Prediction in Transportation Networks
Venue: arXiv cs.LG 2017
Year: 2017

Predicting large-scale transportation network traffic has become an important and challenging topic in recent decades. Inspired by the domain knowledge of motion prediction, in which the future motion of an object can be predicted based on previous scenes, we propose a network grid representation method that can retain the fine-scale structure of a transportation network. Network-wide traffic speeds are converted into a series of static images and input into a novel deep architecture, namely, spatiotemporal recurrent convolutional networks (SRCNs), for traffic forecasting. The proposed SRCNs inherit the advantages of deep convolutional neural networks (DCNNs) and long short-term memory (LSTM) neural networks. The spatial dependencies of network-wide traffic can be captured by DCNNs, and the temporal dynamics can be learned by LSTMs. An experiment on a Beijing transportation network with 278 links demonstrates that SRCNs outperform other deep learning-based algorithms in both short-term and long-term traffic prediction.