OpenRaiser/Intern-Atlas huggingface dataset:
Testing hereditary properties of ordered graphs and matrices
Venue: arXiv cs.DS 2017
Year: 2017

We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries. We also explain how the proof can be adapted to show that any hereditary property of $2$-dimensional matrices over a finite alphabet (where row and column order is not ignored) is strongly testable. The first result generalizes the result of Alon and Shapira [FOCS'05, SICOMP'08], who showed that any hereditary graph property (without vertex order) is strongly testable. The second result answers and generalizes a conjecture of Alon, Fischer and Newman [SICOMP'07] concerning testing of matrix properties. The testability is proved by establishing a removal lemma for vertex-ordered graphs. It states that for any finite or infinite family $\mathcal{F}$ of forbidden vertex-ordered graphs, and any $ε> 0$, there exist $δ> 0$ and $k$ so that any vertex-ordered graph which is $ε$-far from being $\mathcal{F}$-free contains at least $δn^{|F|}$ copies of some $F\in\mathcal{F}$ (with the correct vertex order) where $|F|\leq k$. The proof bridges the gap between techniques related to the regularity lemma, used in the long chain of papers investigating graph testing, and string testing techniques. Along the way we develop a Ramsey-type lemma for $k$-partite graphs with "undesirable" edges, stating that one can find a Ramsey-type structure in such a graph, in which the density of the undesirable edges is not much higher than the density of those edges in the graph.
A Trolling Hierarchy in Social Media and A Conditional Random Field For Trolling Detection
Venue: arXiv cs.CL 2017
Year: 2017

An-ever increasing number of social media websites, electronic newspapers and Internet forums allow visitors to leave comments for others to read and interact. This exchange is not free from participants with malicious intentions, which do not contribute with the written conversation. Among different communities users adopt strategies to handle such users. In this paper we present a comprehensive categorization of the trolling phenomena resource, inspired by politeness research and propose a model that jointly predicts four crucial aspects of trolling: intention, interpretation, intention disclosure and response strategy. Finally, we present a new annotated dataset containing excerpts of conversations involving trolls and the interactions with other users that we hope will be a useful resource for the research community.
Approximation Algorithms for Barrier Sweep Coverage
Venue: arXiv cs.DC 2017
Year: 2017

Time-varying coverage, namely sweep coverage is a recent development in the area of wireless sensor networks, where a small number of mobile sensors sweep or monitor comparatively large number of locations periodically. In this article we study barrier sweep coverage with mobile sensors where the barrier is considered as a finite length continuous curve on a plane. The coverage at every point on the curve is time-variant. We propose an optimal solution for sweep coverage of a finite length continuous curve. Usually energy source of a mobile sensor is battery with limited power, so energy restricted sweep coverage is a challenging problem for long running applications. We propose an energy restricted sweep coverage problem where every mobile sensors must visit an energy source frequently to recharge or replace its battery. We propose a $\frac{13}{3}$-approximation algorithm for this problem. The proposed algorithm for multiple curves achieves the best possible approximation factor 2 for a special case. We propose a 5-approximation algorithm for the general problem. As an application of the barrier sweep coverage problem for a set of line segments, we formulate a data gathering problem. In this problem a set of mobile sensors is arbitrarily monitoring the line segments one for each. A set of data mules periodically collects the monitoring data from the set of mobile sensors. We prove that finding the minimum number of data mules to collect data periodically from every mobile sensor is NP-hard and propose a 3-approximation algorithm to solve it.
Phase limitations of Zames-Falb multipliers
Venue: arXiv cs.SY 2017
Year: 2017

Phase limitations of both continuous-time and discrete-time Zames-Falb multipliers and their relation with the Kalman conjecture are analysed. A phase limitation for continuous-time multipliers given by Megretski is generalised and its applicability is clarified; its relation to the Kalman conjecture is illustrated with a classical example from the literature. It is demonstrated that there exist fourth-order plants where the existence of a suitable Zames-Falb multiplier can be discarded and for which simulations show unstable behavior. A novel phase-limitation for discrete-time Zames-Falb multipliers is developed. Its application is demonstrated with a second-order counterexample to the Kalman conjecture. Finally, the discrete-time limitation is used to show that there can be no direct counterpart of the off-axis circle criterion in the discrete-time domain.
On the Linearity of Semantic Change: Investigating Meaning Variation via Dynamic Graph Models
Venue: arXiv cs.CL 2017
Year: 2017

We consider two graph models of semantic change. The first is a time-series model that relates embedding vectors from one time period to embedding vectors of previous time periods. In the second, we construct one graph for each word: nodes in this graph correspond to time points and edge weights to the similarity of the word's meaning across two time points. We apply our two models to corpora across three different languages. We find that semantic change is linear in two senses. Firstly, today's embedding vectors (= meaning) of words can be derived as linear combinations of embedding vectors of their neighbors in previous time periods. Secondly, self-similarity of words decays linearly in time. We consider both findings as new laws/hypotheses of semantic change.
Motion Saliency Based Automatic Delineation of Glottis Contour in High-speed Digital Images
Venue: arXiv cs.CV 2017
Year: 2017

In recent years, high-speed videoendoscopy (HSV) has significantly aided the diagnosis of voice pathologies and furthered the understanding the voice production in recent years. As the first step of these studies, automatic segmentation of glottal images till presents a major challenge for this technique. In this paper, we propose an improved Saliency Network that automatically delineates the contour of the glottis from HSV image sequences. Our proposed additional saliency measure, Motion Saliency (MS), improves upon the original Saliency Network by using the velocities of defined edges. In our results and analysis, we demonstrate the effectiveness of our approach and discuss its potential applications for computer-aided assessment of voice pathologies and understanding voice production.
Achievable Rates of Buffer-Aided Full-Duplex Gaussian Relay Channels
Venue: arXiv cs.IT 2017
Year: 2017

We derive closed-form expressions for the achievable rates of a buffer-aided full-duplex (FD) multiple-input multiple-output (MIMO) Gaussian relay channel. The FD relay still suffers from residual self-interference (RSI) after the application of self-interference mitigation techniques. We investigate both cases of a slow-RSI channel where the RSI is fixed over the entire codeword, and a fast-RSI channel where the RSI changes from one symbol duration to another within the codeword. We show that the RSI can be completely eliminated in the slow-RSI case when the FD relay is equipped with a buffer while the fast RSI cannot be eliminated. For the fixed-rate data transmission scenario, we derive the optimal transmission strategy that should be adopted by the source node and relay node to maximize the system throughput. We verify our analytical findings through simulations.
Mixed Graphical Models for Causal Analysis of Multi-modal Variables
Venue: arXiv cs.AI 2017
Year: 2017

Graphical causal models are an important tool for knowledge discovery because they can represent both the causal relations between variables and the multivariate probability distributions over the data. Once learned, causal graphs can be used for classification, feature selection and hypothesis generation, while revealing the underlying causal network structure and thus allowing for arbitrary likelihood queries over the data. However, current algorithms for learning sparse directed graphs are generally designed to handle only one type of data (continuous-only or discrete-only), which limits their applicability to a large class of multi-modal biological datasets that include mixed type variables. To address this issue, we developed new methods that modify and combine existing methods for finding undirected graphs with methods for finding directed graphs. These hybrid methods are not only faster, but also perform better than the directed graph estimation methods alone for a variety of parameter settings and data set sizes. Here, we describe a new conditional independence test for learning directed graphs over mixed data types and we compare performances of different graph learning strategies on synthetic data.
A Secure Key Agreement Protocol for Dynamic Group
Venue: arXiv cs.CR 2017
Year: 2017

To accomplish secure group communication, it is essential to share a unique cryptographic key among group members. The underlying challenges to group key agreement are scalability, efficiency, and security. In a dynamic group environment, the rekeying process is more frequent; therefore, it is more crucial to design an efficient group key agreement protocol. Moreover, with the emergence of various group-based services, it is becoming common for several multicast groups to coexist in the same network. These multicast groups may have several shared users; a join or leave request by a single user can trigger regeneration of multiple group keys. Under the given circumstances the rekeying process becomes a challenging task. In this work, we propose a novel methodology for group key agreement which exploits the state vectors of group members. The state vector is a set of randomly generated nonce instances which determine the logical link between group members and which empowers the group member to generate multiple cryptographic keys independently. Using local knowledge of a secret nonce, each member can generate and share a large number of secure keys, indicating that SGRS inherently provides a considerable amount of secure subgroup multicast communication using subgroup multicasting keys derived from local state vectors. The resulting protocol is secure and efficient in terms of both communication and computation.
Evolving a Vector Space with any Generating Set
Venue: arXiv cs.LG 2017
Year: 2017

In Valiant's model of evolution, a class of representations is evolvable iff a polynomial-time process of random mutations guided by selection converges with high probability to a representation as $ε$-close as desired from the optimal one, for any required $ε>0$. Several previous positive results exist that can be related to evolving a vector space, but each former result imposes disproportionate representations or restrictions on (re)initialisations, distributions, performance functions and/or the mutator. In this paper, we show that all it takes to evolve a normed vector space is merely a set that generates the space. Furthermore, it takes only $\tilde{O}(1/ε^2)$ steps and it is essentially stable, agnostic and handles target drifts that rival some proven in fairly restricted settings. Our algorithm can be viewed as a close relative to a popular fifty-years old gradient-free optimization method for which little is still known from the convergence standpoint: Nelder-Mead simplex method.
Formal approaches to a definition of agents
Venue: arXiv cs.AI 2017
Year: 2017

This thesis contributes to the formalisation of the notion of an agent within the class of finite multivariate Markov chains. Agents are seen as entities that act, perceive, and are goal-directed. We present a new measure that can be used to identify entities (called $ι$-entities), some general requirements for entities in multivariate Markov chains, as well as formal definitions of actions and perceptions suitable for such entities. The intuition behind $ι$-entities is that entities are spatiotemporal patterns for which every part makes every other part more probable. The measure, complete local integration (CLI), is formally investigated in general Bayesian networks. It is based on the specific local integration (SLI) which is measured with respect to a partition. CLI is the minimum value of SLI over all partitions. We prove that $ι$-entities are blocks in specific partitions of the global trajectory. These partitions are the finest partitions that achieve a given SLI value. We also establish the transformation behaviour of SLI under permutations of nodes in the network. We go on to present three conditions on general definitions of entities. These are not fulfilled by sets of random variables i.e.\ the perception-action loop, which is often used to model agents, is too restrictive. We propose that any general entity definition should in effect specify a subset (called an an entity-set) of the set of all spatiotemporal patterns of a given multivariate Markov chain. The set of $ι$-entities is such a set. Importantly the perception-action loop also induces an entity-set. We then propose formal definitions of actions and perceptions for arbitrary entity-sets. These specialise to standard notions in case of the perception-action loop entity-set. Finally we look at some very simple examples.
CanvoX: High-resolution VR Painting in Large Volumetric Canvas
Venue: arXiv cs.GR 2017
Year: 2017

With virtual reality, digital painting on 2D canvases is now being extended to 3D spaces. Tilt Brush and Oculus Quill are widely accepted among artists as tools that pave the way to a new form of art - 3D emmersive painting. Current 3D painting systems are only a start, emitting textured triangular geometries. In this paper, we advance this new art of 3D painting to 3D volumetric painting that enables an artist to draw a huge scene with full control of spatial color fields. Inspired by the fact that 2D paintings often use vast space to paint background and small but detailed space for foreground, we claim that supporting a large canvas in varying detail is essential for 3D painting. In order to help artists focus and audiences to navigate the large canvas space, we provide small artist-defined areas, called rooms, that serve as beacons for artist-suggested scales, spaces, locations for intended appreciation view of the painting. Artists and audiences can easily transport themselves between different rooms. Technically, our canvas is represented as an array of deep octrees of depth 24 or higher, built on CPU for volume painting and on GPU for volume rendering using accurate ray casting. In CPU side, we design an efficient iterative algorithm to refine or coarsen octree, as a result of volumetric painting strokes, at highly interactive rates, and update the corresponding GPU textures. Then we use GPU-based ray casting algorithms to render the volumetric painting result. We explore precision issues stemming from ray-casting the octree of high depth, and provide a new analysis and verification. From our experimental results as well as the positive feedback from the participating artists, we strongly believe that our new 3D volume painting system can open up a new possibility for VR-driven digital art medium to professional artists as well as to novice users.
Efficient, Single Hop Time Synchronization Protocol For Randomly Connected WSNs
Venue: arXiv cs.NI 2017
Year: 2017

This paper develops a fast, accurate and energy-efficient time synchronization protocol in wireless sensor networks that operate in harsh environments. The suggested protocol concept is based on an electrical physical metaphor. The protocol treats the nodes times as the states of an unconditionally stable discrete dynamical system that uses only single hop communication. The system can terminate at a low number of message exchanges while still in the transient phase. It can yield high quality time estimates with accuracies that are fractions of the clock at which node communication takes place. The synchronizer is developed and its capabilities are demonstrated by simulation and physical experiments on the MICA-Z wireless sensor network
Flags of almost affine codes
Venue: arXiv cs.IT 2017
Year: 2017

We describe a two-party wire-tap channel of type II in the framework of almost affine codes. Its cryptological performance is related to some relative profiles of a pair of almost affine codes. These profiles are analogues of relative generalized Hamming weights in the linear case.
Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in $O(\log^3 n)$ Worst Case Update Time
Venue: arXiv cs.DS 2017
Year: 2017

We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains, however, a polynomial gap between the best known worst case update time and the best known amortised update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein [ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic data structure with approximation ratio $(3/2+ε)$ and worst case update time $O(m^{1/4}/ε^2)$, where $m$ is the number of edges in the graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure with approximation ratio $(1+ε)$ and worst case update time $O(\sqrt{m}/ε^2)$. No known randomised data structure beats the worst case update times of these two results. In contrast, the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio $O(1)$ and amortised update time $O(\log^2 n)$, where $n$ is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS 2011] and Solomon [FOCS 2016], leading to a randomised date structure with approximation ratio $2$ and amortised update time $O(1)$. We bridge the polynomial gap between the worst case and amortised update times for this problem, without using any randomisation. We present a deterministic data structure with approximation ratio $(2+ε)$ and worst case update time $O(\log^3 n)$, for all sufficiently small constants $ε$.
SemEval 2017 Task 10: ScienceIE - Extracting Keyphrases and Relations from Scientific Publications
Venue: arXiv cs.CL 2017
Year: 2017

We describe the SemEval task of extracting keyphrases and relations between them from scientific documents, which is crucial for understanding which publications describe which processes, tasks and materials. Although this was a new task, we had a total of 26 submissions across 3 evaluation scenarios. We expect the task and the findings reported in this paper to be relevant for researchers working on understanding scientific content, as well as the broader knowledge base population and information extraction communities.
Pay Attention to Those Sets! Learning Quantification from Images
Venue: arXiv cs.CL 2017
Year: 2017

Major advances have recently been made in merging language and vision representations. But most tasks considered so far have confined themselves to the processing of objects and lexicalised relations amongst objects (content words). We know, however, that humans (even pre-school children) can abstract over raw data to perform certain types of higher-level reasoning, expressed in natural language by function words. A case in point is given by their ability to learn quantifiers, i.e. expressions like 'few', 'some' and 'all'. From formal semantics and cognitive linguistics, we know that quantifiers are relations over sets which, as a simplification, we can see as proportions. For instance, in 'most fish are red', most encodes the proportion of fish which are red fish. In this paper, we study how well current language and vision strategies model such relations. We show that state-of-the-art attention mechanisms coupled with a traditional linguistic formalisation of quantifiers gives best performance on the task. Additionally, we provide insights on the role of 'gist' representations in quantification. A 'logical' strategy to tackle the task would be to first obtain a numerosity estimation for the two involved sets and then compare their cardinalities. We however argue that precisely identifying the composition of the sets is not only beyond current state-of-the-art models but perhaps even detrimental to a task that is most efficiently performed by refining the approximate numerosity estimator of the system.
Characterizing Product Lifecycle in Online Marketing: Sales, Trust, Revenue, and Competition Modeling
Venue: arXiv cs.SI 2017
Year: 2017

Recent researches have seen an upsurge in the analysis of consumer reviews. Although, several dimensions have been explored, less is known on the temporal dynamics of events that happen over the lifecycle of online products. What are the dominant sales patterns? How are they affected by review count, rating, helpfulness and sentiment? How is trust characterized and what are its effects on sales and revenue? What happens during a market competition? When does a takeover/recovery happen and by what percentage do sales increase on a takeover? This work aims to answer these fundamental research questions based on a sales time-series analysis of reviews of over 1 million products from Amazon.com. We discover novel temporal patterns of sales and interesting correlations of sales with the ratings. We find that trust and helpfulness are important for higher revenue. Based on the analyses, we propose a model to forecast sales that significantly outperforms other baselines. We then explore the phenomena of market competition. Particularly, we characterize different factors that govern survival/death of a product under competition and a model for competition forecast. Experimental results on large-scale reviews demonstrate the effectiveness of the proposed approaches.
ROSA: R Optimizations with Static Analysis
Venue: arXiv cs.PL 2017
Year: 2017

R is a popular language and programming environment for data scientists. It is increasingly co-packaged with both relational and Hadoop-based data platforms and can often be the most dominant computational component in data analytics pipelines. Recent work has highlighted inefficiencies in executing R programs, both in terms of execution time and memory requirements, which in practice limit the size of data that can be analyzed by R. This paper presents ROSA, a static analysis framework to improve the performance and space efficiency of R programs. ROSA analyzes input programs to determine program properties such as reaching definitions, live variables, aliased variables, and types of variables. These inferred properties enable program transformations such as C++ code translation, strength reduction, vectorization, code motion, in addition to interpretive optimizations such as avoiding redundant object copies and performing in-place evaluations. An empirical evaluation shows substantial reductions by ROSA in execution time and memory consumption over both CRAN R and Microsoft R Open.
Constant Modulus Beamforming via Convex Optimization
Venue: arXiv cs.IT 2017
Year: 2017

We present novel convex-optimization-based solutions to the problem of blind beamforming of constant modulus signals, and to the related problem of linearly constrained blind beamforming of constant modulus signals. These solutions ensure global optimality and are parameter free, namely, do not contain any tuneable parameters and do not require any a-priori parameter settings. The performance of these solutions, as demonstrated by simulated data, is superior to existing methods.