OpenRaiser/Intern-Atlas huggingface dataset:
A Distributed Enumeration Algorithm and Applications to All Pairs Shortest Paths, Diameter
Venue: arXiv cs.DC 2015
Year: 2015

We consider the standard message passing model; we assume the system is fully synchronous: all processes start at the same time and time proceeds in synchronised rounds. In each round each vertex can transmit a different message of size $O(1)$ to each of its neighbours. This paper proposes and analyses a distributed enumeration algorithm of vertices of a graph having a distinguished vertex which satisfies that two vertices with consecutive numbers are at distance at most $3$. We prove that its time complexity is $O(n)$ where $n$ is the number of vertices of the graph. Furthermore, the size of each message is $O(1)$ thus its bit complexity is also $O(n).$ We provide some links between this enumeration and Hamiltonian graphs from which we deduce that this enumeration is optimal in the sense that there does not exist an enumeration which satisfies that two vertices with consecutive numbers are at distance at most $2$. We deduce from this enumeration algorithms which compute all pairs shortest paths and the diameter with a time complexity and a bit complexity equal to $O(n)$. This improves the best known distributed algorithms (under the same hypotheses) for computing all pairs shortest paths or the diameter presented in \cite{PRT12,HW12} having a time complexity equal to $O(n)$ and which use messages of size $O(\log n)$ bits.
LP decoding excess over symmetric channels
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of Linear Programming (LP) decoding of binary linear codes. The LP excess lemma was introduced by the first author, B. Ghazi, and R. Urbanke (IEEE Trans. Inf. Th., 2014) as a technique to trade crossover probability for "LP excess" over the Binary Symmetric Channel. We generalize the LP excess lemma to discrete, binary-input, Memoryless, Symmetric and LLR-Bounded (MSB) channels. As an application, we extend a result by the first author and H. Audah (IEEE Trans. Inf. Th., 2015) on the impact of redundant checks on LP decoding to discrete MSB channels.
Explicit Construction of AG Codes from Generalized Hermitian Curves
Venue: arXiv cs.IT 2015
Year: 2015

We present multi-point algebraic geometric codes overstepping the Gilbert-Varshamov bound. The construction is based on the generalized Hermitian curve introduced by A. Bassa, P. Beelen, A. Garcia, and H. Stichtenoth. These codes are described in detail by constrcting a generator matrix. It turns out that these codes have nice properties similar to those of Hermitian codes. It is shown that the duals are also such codes and an explicit formula is given.
Individual performance calibration using physiological stress signals
Venue: arXiv cs.HC 2015
Year: 2015

The relation between performance and stress is described by the Yerkes-Dodson Law but varies significantly between individuals. This paper describes a method for determining the individual optimal performance as a function of physiological signals. The method is based on attention and reasoning tests of increasing complexity under monitoring of three physiological signals: Galvanic Skin Response (GSR), Heart Rate (HR), and Electromyogram (EMG). Based on the test results with 15 different individuals, we first show that two of the signals, GSR and HR, have enough discriminative power to distinguish between relax and stress periods. We then show a positive correlation between the complexity level of the tests and the GSR and HR signals, and we finally determine the optimal performance point as the signal level just before a performance decrease. We also discuss the differences among signals depending on the type of test.
#mytweet via Instagram: Exploring User Behaviour across Multiple Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

We study how users of multiple online social networks (OSNs) employ and share information by studying a common user pool that use six OSNs - Flickr, Google+, Instagram, Tumblr, Twitter, and YouTube. We analyze the temporal and topical signature of users' sharing behaviour, showing how they exhibit distinct behaviorial patterns on different networks. We also examine cross-sharing (i.e., the act of user broadcasting their activity to multiple OSNs near-simultaneously), a previously-unstudied behaviour and demonstrate how certain OSNs play the roles of originating source and destination sinks.
Adverse Events in Robotic Surgery: A Retrospective Study of 14 Years of FDA Data
Venue: arXiv cs.RO 2015
Year: 2015

Understanding the causes and patient impacts of surgical adverse events will help improve systems and operational practices to avoid incidents in the future. We analyzed the adverse events data related to robotic systems and instruments used in minimally invasive surgery, reported to the U.S. FDA MAUDE database from January 2000 to December 2013. We determined the number of events reported per procedure and per surgical specialty, the most common types of device malfunctions and their impact on patients, and the causes for catastrophic events such as major complications, patient injuries, and deaths. During the study period, 144 deaths (1.4% of the 10,624 reports), 1,391 patient injuries (13.1%), and 8,061 device malfunctions (75.9%) were reported. The numbers of injury and death events per procedure have stayed relatively constant since 2007 (mean = 83.4, 95% CI, 74.2-92.7). Surgical specialties, for which robots are extensively used, such as gynecology and urology, had lower number of injuries, deaths, and conversions per procedure than more complex surgeries, such as cardiothoracic and head and neck (106.3 vs. 232.9, Risk Ratio = 2.2, 95% CI, 1.9-2.6). Device and instrument malfunctions, such as falling of burnt/broken pieces of instruments into the patient (14.7%), electrical arcing of instruments (10.5%), unintended operation of instruments (8.6%), system errors (5%), and video/imaging problems (2.6%), constituted a major part of the reports. Device malfunctions impacted patients in terms of injuries or procedure interruptions. In 1,104 (10.4%) of the events, the procedure was interrupted to restart the system (3.1%), to convert the procedure to non-robotic techniques (7.3%), or to reschedule it to a later time (2.5%). Adoption of advanced techniques in design and operation of robotic surgical systems may reduce these preventable incidents in the future.
Neural CRF Parsing
Venue: arXiv cs.CL 2015
Year: 2015

This paper describes a parsing model that combines the exact dynamic programming of CRF parsing with the rich nonlinear featurization of neural net approaches. Our model is structurally a CRF that factors over anchored rule productions, but instead of linear potential functions based on sparse features, we use nonlinear potentials computed via a feedforward neural network. Because potentials are still local to anchored rules, structured inference (CKY) is unchanged from the sparse case. Computing gradients during learning involves backpropagating an error signal formed from standard CRF sufficient statistics (expected rule counts). Using only dense features, our neural CRF already exceeds a strong baseline CRF model (Hall et al., 2014). In combination with sparse features, our system achieves 91.1 F1 on section 23 of the Penn Treebank, and more generally outperforms the best prior single parser results on a range of languages.
{dasasap}, an App for Syllogisms
Venue: arXiv cs.CY 2015
Year: 2015

The main goal of this contribution is to introduce a cross-platform application to learn-teach syllogistic. We call this application \textit{dasasap} for \textit{develop all syllogisms as soon as possible}. To introduce this application we show the logical foundations for the game with a system we call $\mathcal{L}_\square$, and its interface developed with LiveCode.
Using Automated Theorem Provers to Teach Knowledge Representation in First-Order Logic
Venue: arXiv cs.CY 2015
Year: 2015

Undergraduate students of artificial intelligence often struggle with representing knowledge as logical sentences. This is a skill that seems to require extensive practice to obtain, suggesting a teaching strategy that involves the assignment of numerous exercises involving the formulation of some bit of knowledge, communicated using a natural language such as English, as a sentence in some logic. The number of such exercises needed to master this skill is far too large to allow typical artificial intelligence course teaching teams to provide prompt feedback on student efforts. Thus, an automated assessment system for such exercises is needed to ensure that students receive an adequate amount of practice, with the rapid delivery of feedback allowing students to identify errors in their understanding and correct them. This paper describes an automated grading system for knowledge representation exercises using first-order logic. A resolution theorem prover, \textit{Prover9}, is used to check if a student-submitted formula is logically equivalent to a solution provided by the instructor. This system has been used by students enrolled in undergraduate artificial intelligence classes for several years. Use of this teaching tool resulted in a statistically significant improvement on first-order logic knowledge representation questions appearing on the course final examination. This article explains how this system works, provides an analysis of changes in student learning outcomes, and explores potential enhancements of this system, including the possibility of providing rich formative feedback by replacing the resolution theorem prover with a tableaux-based method.
Fail better: What formalized math can teach us about learning
Venue: arXiv cs.CY 2015
Year: 2015

Real-life conjectures do not come with instructions saying whether they they should be proven or, instead, refuted. Yet, as we now know, in either case the final argument produced had better be not just convincing but actually verifiable in as much detail as our need for eliminating risk might require. For those who do not happen to have direct access to the realm of mathematical truths, the modern field of formalized mathematics has quite a few lessons to contribute, and one might pay heed to what it has to say, for instance, about: the importance of employing proof strategies; the fine control of automation in unraveling the structure of a certain proof object; reasoning forward from the givens and backward from the goals, in developing proof scripts; knowing when and how definitions and identities apply in a helpful way, and when they do not apply; seeing proofs [and refutations] as dynamical objects, not reflected by the static derivation trees that Proof Theory wants them to be. I believe that the great challenge for teachers and learners resides currently less on the availability of suitable generic tools than in combining them wisely in view of their preferred education paradigms and introducing them in a way that best fits their specific aims, possibly with the help of intelligent online interactive tutoring systems. As a proof of concept, a computerized proof assistant that makes use of several successful tools already freely available on the market and that takes into account some of the above findings about teaching and learning Logic is hereby introduced. To fully account for our informed intuitions on the subject it would seem that a little bit extra technology would still be inviting, but no major breakthrough is really needed: We are talking about tools that are already within our reach to develop, as the fruits of collaborative effort.
Why teach an introductory course in Mathematical Logic in the Philosophy curriculum?
Venue: arXiv cs.CY 2015
Year: 2015

This paper tries to justify the relevance of an introductory course in Mathematical Logic in the Philosophy curriculum for analyzing philosophical arguments in natural language. It is argued that the representation of the structure of natural language arguments in Freeman's diagramming system can provide an intuitive foundation for the inferential processes involved in the use of First Order Logic natural deduction rules.
Closed Curves and Elementary Visual Object Identification
Venue: arXiv cs.CV 2015
Year: 2015

For two closed curves on a plane (discrete version) and local criteria for similarity of points on the curves one gets a potential, which describes the similarity between curve points. This is the base for a global similarity measure of closed curves (Fréchet distance). I use borderlines of handwritten digits to demonstrate an area of application. I imagine, measuring the similarity of closed curves is an essential and elementary task performed by a visual system. This approach to similarity measures may be used by visual systems.
Understanding the Affect of Developers: Theoretical Background and Guidelines for Psychoempirical Software Engineering
Venue: arXiv cs.SE 2015
Year: 2015

Affects---emotions and moods---have an impact on cognitive processing activities and the working performance of individuals. It has been established that software development tasks are undertaken through cognitive processing activities. Therefore, we have proposed to employ psychology theory and measurements in software engineering (SE) research. We have called it "psychoempirical software engineering". However, we found out that existing SE research has often fallen into misconceptions about the affect of developers, lacking in background theory and how to successfully employ psychological measurements in studies. The contribution of this paper is threefold. (1) It highlights the challenges to conduct proper affect-related studies with psychology; (2) it provides a comprehensive literature review in affect theory; and (3) it proposes guidelines for conducting psychoempirical software engineering.
Computing the Similarity Between Moving Curves
Venue: arXiv cs.CG 2015
Year: 2015

In this paper we study similarity measures for moving curves which can, for example, model changing coastlines or retreating glacier termini. Points on a moving curve have two parameters, namely the position along the curve as well as time. We therefore focus on similarity measures for surfaces, specifically the Fréchet distance between surfaces. While the Fréchet distance between surfaces is not even known to be computable, we show for variants arising in the context of moving curves that they are polynomial-time solvable or NP-complete depending on the restrictions imposed on how the moving curves are matched. We achieve the polynomial-time solutions by a novel approach for computing a surface in the so-called free-space diagram based on max-flow min-cut duality.
Transmit Power Minimization in Small Cell Networks Under Time Average QoS Constraints
Venue: arXiv cs.IT 2015
Year: 2015

We consider a small cell network (SCN) consisting of N cells, with the small cell base stations (SCBSs) equipped with Nt \geq 1 antennas each, serving K single antenna user terminals (UTs) per cell. Under this set up, we address the following question: given certain time average quality of service (QoS) targets for the UTs, what is the minimum transmit power expenditure with which they can be met? Our motivation to consider time average QoS constraint comes from the fact that modern wireless applications such as file sharing, multi-media etc. allow some flexibility in terms of their delay tolerance. Time average QoS constraints can lead to greater transmit power savings as compared to instantaneous QoS constraints since it provides the flexibility to dynamically allocate resources over the fading channel states. We formulate the problem as a stochastic optimization problem whose solution is the design of the downlink beamforming vectors during each time slot. We solve this problem using the approach of Lyapunov optimization and characterize the performance of the proposed algorithm. With this algorithm as the reference, we present two main contributions that incorporate practical design considerations in SCNs. First, we analyze the impact of delays incurred in information exchange between the SCBSs. Second, we impose channel state information (CSI) feedback constraints, and formulate a joint CSI feedback and beamforming strategy. In both cases, we provide performance bounds of the algorithm in terms of satisfying the QoS constraints and the time average power expenditure. Our simulation results show that solving the problem with time average QoS constraints provide greater savings in the transmit power as compared to the instantaneous QoS constraints.
Using interrogative logic to teach classical logic
Venue: arXiv cs.CY 2015
Year: 2015

In the paper I discuss a tool for helping students in their symbolizations of natural language sentences using the formal language of classical first order logic (CFOL). The tool is an extension of Hintikka's concept of (Inquirer's) range of attention in the context of interrogative games. Any given text is reconstructed as the answer to a "big" or principal question obtained through the answers of a series of "small" or operative questions. The tool brings some "narrative flavor" to the symbolization and offers a convenient mold that can be used by students in many different contexts.
Millimeter-wave Gbps Broadband Evolution towards 5G: Fixed Access and Backhaul
Venue: arXiv cs.IT 2015
Year: 2015

As wireless communication evolves towards 5G, both fixed broadband and mobile broadband will play a crucial part in providing the Gbps infrastructure for a connected society. This paper proposes a Millimeter-wave Gbps Broadband (MGB) system as the solution to two critical problems in this evolution: last-mile access for fixed broadband and small cell backhaul for mobile broadband. The key idea is to use spectrum that is already available in the millimeter wave bands for fixed wireless access with optimized dynamic beamforming and massive MIMO infrastructure to achieve high capacity with wide area coverage. This paper explains the MGB concept and describes potential array architectures for realizing the system. Simulations demonstrate that with 500 MHz of bandwidth (at 39 GHz band) and 28 dBm transmission power (55 dBm EIRP), it is possible to provide more than 11 Gbps backhaul capacity for 96 small cells within 1-km radius.
Structure and inference in annotated networks
Venue: arXiv cs.SI 2015
Year: 2015

For many networks of scientific interest we know both the connections of the network and information about the network nodes, such as the age or gender of individuals in a social network, geographic location of nodes in the Internet, or cellular function of nodes in a gene regulatory network. Here we demonstrate how this "metadata" can be used to improve our analysis and understanding of network structure. We focus in particular on the problem of community detection in networks and develop a mathematically principled approach that combines a network and its metadata to detect communities more accurately than can be done with either alone. Crucially, the method does not assume that the metadata are correlated with the communities we are trying to find. Instead the method learns whether a correlation exists and correctly uses or ignores the metadata depending on whether they contain useful information. The learned correlations are also of interest in their own right, allowing us to make predictions about the community membership of nodes whose network connections are unknown. We demonstrate our method on synthetic networks with known structure and on real-world networks, large and small, drawn from social, biological, and technological domains.
Analyzing the activity of a person in a chat by combining network analysis and fuzzy logic
Venue: arXiv cs.SI 2015
Year: 2015

Chat-log data that contains information about sender and receiver of the statements sent around in the chat can be readily turned into a directed temporal multi-network representation. In the resulting network, the activity of a chat member can, for example, be operationalized as his degree (number of distinct interaction partners) or his strength (total number of interactions). However, the data itself contains more information that is not readily representable in the network, e.g., the total number of words used by a member or the reaction time to what the members said. As degree and strength, these values can be seen as a way to operationalize the idea of activity of a chat-log member. This paper deals with the question of how the overall activity of a member can be assessed, given multiple and probably opposing criteria by using a fuzzy operator. We then present a new way of visualizing the results and show how to apply it to the network representation of chat-log data. Finally, we discuss how this approach can be used to deal with other conflicting situations, like the different rankings produced by different centrality indices.
Training artificial neural networks to learn a nondeterministic game
Venue: arXiv cs.LG 2015
Year: 2015

It is well known that artificial neural networks (ANNs) can learn deterministic automata. Learning nondeterministic automata is another matter. This is important because much of the world is nondeterministic, taking the form of unpredictable or probabilistic events that must be acted upon. If ANNs are to engage such phenomena, then they must be able to learn how to deal with nondeterminism. In this project the game of Pong poses a nondeterministic environment. The learner is given an incomplete view of the game state and underlying deterministic physics, resulting in a nondeterministic game. Three models were trained and tested on the game: Mona, Elman, and Numenta's NuPIC.
A de Casteljau Algorithm for Bernstein type Polynomials based on (p,q)-integers
Venue: arXiv cs.GR 2015
Year: 2015

In this paper, a de Casteljau algorithm to compute (p,q)-Bernstein Bezier curves based on (p,q)-integers is introduced. We study the nature of degree elevation and degree reduction for (p,q)-Bezier Bernstein functions. The new curves have some properties similar to q-Bezier curves. Moreover, we construct the corresponding tensor product surfaces over the rectangular domain (u, v) \in [0, 1] \times [0, 1] depending on four parameters. We also study the de Casteljau algorithm and degree evaluation properties of the surfaces for these generalization over the rectangular domain. Furthermore, some fundamental properties for (p,q)-Bernstein Bezier curves are discussed. We get q-Bezier curves and surfaces for (u, v) \in [0, 1] \times [0, 1] when we set the parameter p1 = p2 = 1.
Smart Pilot Assignment for Massive MIMO
Venue: arXiv cs.IT 2015
Year: 2015

A massive multiple-input multiple-output (MIMO) system, which utilizes a large number of antennas at the base station (BS) to serve multiple users, suffers from pilot contamination due to inter-cell interference. A smart pilot assignment (SPA) scheme is proposed in this letter to improve the performance of users with severe pilot contamination. Specifically, by exploiting the large-scale characteristics of fading channels, the BS firstly measures the inter-cell interference of each pilot sequence caused by the users with the same pilot sequence in other adjacent cells. Then, in contrast to the conventional schemes which assign the pilot sequences to the users randomly, the proposed SPA method assigns the pilot sequence with the smallest inter-cell interference to the user having the worst channel quality in a sequential way to improve its performance. Simulation results verify the performance gain of the proposed scheme in typical massive MIMO systems.