OpenRaiser/Intern-Atlas huggingface dataset:
Structural Resolution: a Framework for Coinductive Proof Search and Proof Construction in Horn Clause Logic
Venue: arXiv cs.LO 2017
Year: 2017

Logic programming (LP) is a programming language based on first-order Horn clause logic that uses SLD-resolution as a semi-decision procedure. Finite SLD-computations are inductively sound and complete with respect to least Herbrand models of logic programs. Dually, the corecursive approach to SLD-resolution views infinite SLD-computations as successively approximating infinite terms contained in programs' greatest complete Herbrand models. State-of-the-art algorithms implementing corecursion in LP are based on loop detection. However, such algorithms support inference of logical entailment only for rational terms, and they do not account for the important property of productivity in infinite SLD-computations. Loop detection thus lags behind coinductive methods in interactive theorem proving (ITP) and term-rewriting systems (TRS). Structural resolution is a newly proposed alternative to SLD-resolution that makes it possible to define and semi-decide a notion of productivity appropriate to LP. In this paper, we prove soundness of structural resolution relative to Herbrand model semantics for productive inductive, coinductive, and mixed inductive-coinductive logic programs. We introduce two algorithms that support coinductive proof search for infinite productive terms. One algorithm combines the method of loop detection with productive structural resolution, thus guaranteeing productivity of coinductive proofs for infinite rational terms. The other allows to make lazy sound observations of fragments of infinite irrational productive terms. This puts coinductive methods in LP on par with productivity-based observational approaches to coinduction in ITP and TRS.
Parameterized Extension Complexity of Independent Set and Related Problems
Venue: arXiv cs.CC 2017
Year: 2017

Let $G$ be a graph on $n$ vertices and $\mathrm{STAB}_k(G)$ be the convex hull of characteristic vectors of its independent sets of size at most $k$. We study extension complexity of $\mathrm{STAB}_k(G)$ with respect to a fixed parameter $k$ (analogously to, e.g., parameterized computational complexity of problems). We show that for graphs $G$ from a class of bounded expansion it holds that $\mathrm{xc}(\mathrm{STAB}_k(G))\leqslant \mathcal{O}(f(k)\cdot n)$ where the function $f$ depends only on the class. This result can be extended in a simple way to a wide range of similarly defined graph polytopes. In case of general graphs we show that there is {\em no function $f$} such that, for all values of the parameter $k$ and for all graphs on $n$ vertices, the extension complexity of $\mathrm{STAB}_k(G)$ is at most $f(k)\cdot n^{\mathcal{O}(1)}.$ While such results are not surprising since it is known that optimizing over $\mathrm{STAB}_k(G)$ is $FPT$ for graphs of bounded expansion and $W[1]$-hard in general, they are also not trivial and in both cases stronger than the corresponding computational complexity results.
On the Degrees of Freedom of the Symmetric Multi-Relay MIMO Y Channel
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we study the degrees of freedom (DoF) of the symmetric multi-relay multiple-input multiple-output (MIMO) Y channel, where three user nodes, each with M antennas, communicate via K geographically separated relay nodes, each with N antennas. For this model, we establish a general DoF achievability framework based on linear precoding and post-processing methods. The framework poses a nonlinear problem with respect to user precoders and post-processors, as well as relay precoders. To solve this problem, we adopt an uplink-downlink asymmetric strategy, where the user precoders are designed for signal alignment and the user post-processors are used for interference neutralization. With the user precoder and post-processor designs fixed as such, the original problem then reduces to a problem of relay precoder design. To address the solvability of the system, we propose a general method for solving matrix equations. This method is also useful to the DoF analysis of many other multiway relay networks. Together with the techniques of antenna disablement and symbol extension, an achievable DoF of the symmetric multi-relay MIMO Y channel is derived for an arbitrary setup of (K, M, N). We show that, for K >= 2, the optimal DoF is achieved for M/N in [0, max{sqrt(3K)/3,1}) and [(3K+sqrt(9K^2-12K))/6,infinity). We also show that the uplink-downlink asymmetric design proposed in this paper considerably outperforms the conventional approach based on uplink-downlink symmetry.
Density Evolution for Deterministic Generalized Product Codes on the Binary Erasure Channel at High Rates
Venue: arXiv cs.IT 2017
Year: 2017

Generalized product codes (GPCs) are extensions of product codes (PCs) where code symbols are protected by two component codes but not necessarily arranged in a rectangular array. We consider a deterministic construction of GPCs (as opposed to randomized code ensembles) and analyze the asymptotic performance over the binary erasure channel under iterative decoding. Our code construction encompasses several classes of GPCs previously proposed in the literature, such as irregular PCs, block-wise braided codes, and staircase codes. It is assumed that the component codes can correct a fixed number of erasures and that the length of each component code tends to infinity. We show that this setup is equivalent to studying the behavior of a peeling algorithm applied to a sparse inhomogeneous random graph. Using a convergence result for these graphs, we derive the density evolution equations that characterize the asymptotic decoding performance. As an application, we discuss the design of irregular GPCs employing a mixture of component codes with different erasure-correcting capabilities.
A Stochastic Geometry Approach to Asynchronous Aloha Full-Duplex Networks
Venue: arXiv cs.NI 2017
Year: 2017

In-band full-duplex is emerging as a promising solution to enhance throughput in wireless networks. Allowing nodes to simultaneously send and receive data over the same bandwidth can potentially double the system capacity, and a good degree of maturity has been reached for physical layer design, with practical demonstrations in simple topologies. However, the true potential of full-duplex at a system level is yet to be fully understood. In this paper, we introduce an analytical framework based on stochastic geometry that captures the behaviour of large full-duplex networks implementing an asynchronous random access policy based on Aloha. Via exact expressions we discuss the key tradeoffs that characterise these systems, exploring among the rest the role of transmission duration, imperfect self-interference cancellation and fraction of full-duplex nodes in the network. We also provide protocol design principles, and our comparison with slotted systems sheds light on the performance loss induced by the lack of synchronism.
Variance Reduction for Distributed Stochastic Gradient Descent
Venue: arXiv cs.LG 2017
Year: 2017

Variance reduction (VR) methods boost the performance of stochastic gradient descent (SGD) by enabling the use of larger, constant stepsizes and preserving linear convergence rates. However, current variance reduced SGD methods require either high memory usage or an exact gradient computation (using the entire dataset) at the end of each epoch. This limits the use of VR methods in practical distributed settings. In this paper, we propose a variance reduction method, called VR-lite, that does not require full gradient computations or extra storage. We explore distributed synchronous and asynchronous variants that are scalable and remain stable with low communication frequency. We empirically compare both the sequential and distributed algorithms to state-of-the-art stochastic optimization methods, and find that our proposed algorithms perform favorably to other stochastic methods.
Approximate Range Counting Revisited
Venue: arXiv cs.CG 2017
Year: 2017

We study range-searching for colored objects, where one has to count (approximately) the number of colors present in a query range. The problems studied mostly involve orthogonal range-searching in two and three dimensions, and the dual setting of rectangle stabbing by points. We present optimal and near-optimal solutions for these problems. Most of the results are obtained via reductions to the approximate uncolored version, and improved data-structures for them. An additional contribution of this work is the introduction of nested shallow cuttings.
Social Media Image Analysis for Public Health
Venue: arXiv cs.SI 2017
Year: 2017

Several projects have shown the feasibility to use textual social media data to track public health concerns, such as temporal influenza patterns or geographical obesity patterns. In this paper, we look at whether geo-tagged images from Instagram also provide a viable data source. Especially for "lifestyle" diseases, such as obesity, drinking or smoking, images of social gatherings could provide information that is not necessarily shared in, say, tweets. In this study, we explore whether (i) tags provided by the users and (ii) annotations obtained via automatic image tagging are indeed valuable for studying public health. We find that both user-provided and machine-generated tags provide information that can be used to infer a county's health statistics. Whereas for most statistics user-provided tags are better features, for predicting excessive drinking machine-generated tags such as "liquid" and "glass" yield better models. This hints at the potential of using machine-generated tags to study substance abuse.
Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs
Venue: arXiv cs.DS 2017
Year: 2017

A graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign $-$ if and only if its endpoints are in different parts. The Edwards-Erdös bound states that every graph with $n$ vertices and $m$ edges has a balanced subgraph with at least $\frac{m}{2}+\frac{n-1}{4}$ edges. In the Signed Max Cut Above Tight Lower Bound (Signed Max Cut ATLB) problem, given a signed graph $G$ and a parameter $k$, the question is whether $G$ has a balanced subgraph with at least $\frac{m}{2}+\frac{n-1}{4}+\frac{k}{4}$ edges. This problem generalizes Max Cut Above Tight Lower Bound, for which a kernel with $O(k^5)$ vertices was given by Crowston et al. [ICALP 2012, Algorithmica 2015]. Crowston et al. [TCS 2013] improved this result by providing a kernel with $O(k^3)$ vertices for the more general Signed Max Cut ATLB problem. In this article we are interested in improving the size of the kernels for Signed Max Cut ATLB on restricted graph classes for which the problem remains hard. For two integers $r,\ell \geq 0$, a graph $G$ is an $(r,\ell)$-graph if $V(G)$ can be partitioned into $r$ independent sets and $\ell$ cliques. Building on the techniques of Crowston et al. [TCS 2013], we provide a kernel with $O(k^2)$ vertices on $(r,\ell)$-graphs for any fixed $r,\ell \geq 0$, and a simple linear kernel on subclasses of split graphs for which we prove that the problem is still NP-hard.
Improved Bounds for 3SUM, $k$-SUM, and Linear Degeneracy
Venue: arXiv cs.DS 2017
Year: 2017

Given a set of $n$ real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Grønlund and Pettie [FOCS'14], a simple $Θ(n^2)$-time deterministic algorithm for this problem was conjectured to be optimal. Over the years many algorithmic problems have been shown to be reducible from the 3SUM problem or its variants, including the more generalized forms of the problem, such as $k$-SUM and $k$-variate linear degeneracy testing ($k$-LDT). The conjectured hardness of these problems have become extremely popular for basing conditional lower bounds for numerous algorithmic problems in P. In this paper, we show that the randomized $4$-linear decision tree complexity of 3SUM is $O(n^{3/2})$, and that the randomized $(2k-2)$-linear decision tree complexity of $k$-SUM and $k$-LDT is $O(n^{k/2})$, for any odd $k\ge 3$. These bounds improve (albeit randomized) the corresponding $O(n^{3/2}\sqrt{\log n})$ and $O(n^{k/2}\sqrt{\log n})$ decision tree bounds obtained by Grønlund and Pettie. Our technique includes a specialized randomized variant of fractional cascading data structure. Additionally, we give another deterministic algorithm for 3SUM that runs in $O(n^2 \log\log n / \log n )$ time. The latter bound matches a recent independent bound by Freund [Algorithmica 2017], but our algorithm is somewhat simpler, due to a better use of word-RAM model.
Fast Operations on Linearized Polynomials and their Applications in Coding Theory
Venue: arXiv cs.SC 2017
Year: 2017

This paper considers fast algorithms for operations on linearized polynomials. We propose a new multiplication algorithm for skew polynomials (a generalization of linearized polynomials) which has sub-quadratic complexity in the polynomial degree $s$, independent of the underlying field extension degree~$m$. We show that our multiplication algorithm is faster than all known ones when $s \leq m$. Using a result by Caruso and Le Borgne (2017), this immediately implies a sub-quadratic division algorithm for linearized polynomials for arbitrary polynomial degree $s$. Also, we propose algorithms with sub-quadratic complexity for the $q$-transform, multi-point evaluation, computing minimal subspace polynomials, and interpolation, whose implementations were at least quadratic before. Using the new fast algorithm for the $q$-transform, we show how matrix multiplication over a finite field can be implemented by multiplying linearized polynomials of degrees at most $s=m$ if an elliptic normal basis of extension degree $m$ exists, providing a lower bound on the cost of the latter problem. Finally, it is shown how the new fast operations on linearized polynomials lead to the first error and erasure decoding algorithm for Gabidulin codes with sub-quadratic complexity.
A Sharp Condition for Exact Support Recovery of with Orthogonal Matching Pursuit
Venue: arXiv cs.IT 2017
Year: 2017

Support recovery of sparse signals from noisy measurements with orthogonal matching pursuit (OMP) has been extensively studied. In this paper, we show that for any $K$-sparse signal $\x$, if a sensing matrix $\A$ satisfies the restricted isometry property (RIP) with restricted isometry constant (RIC) $δ_{K+1} < 1/\sqrt {K+1}$, then under some constraints on the minimum magnitude of nonzero elements of $\x$, OMP exactly recovers the support of $\x$ from its measurements $\y=\A\x+\v$ in $K$ iterations, where $\v$ is a noise vector that is $\ell_2$ or $\ell_{\infty}$ bounded. This sufficient condition is sharp in terms of $δ_{K+1}$ since for any given positive integer $K$ and any $1/\sqrt{K+1}\leq δ<1$, there always exists a matrix $\A$ satisfying the RIP with $δ_{K+1}=δ$ for which OMP fails to recover a $K$-sparse signal $\x$ in $K$ iterations. Also, our constraints on the minimum magnitude of nonzero elements of $\x$ are weaker than existing ones. Moreover, we propose worst-case necessary conditions for the exact support recovery of $\x$, characterized by the minimum magnitude of the nonzero elements of $\x$.
Unified Description for Network Information Hiding Methods
Venue: arXiv cs.CR 2017
Year: 2017

Until now hiding methods in network steganography have been described in arbitrary ways, making them difficult to compare. For instance, some publications describe classical channel characteristics, such as robustness and bandwidth, while others describe the embedding of hidden information. We introduce the first unified description of hiding methods in network steganography. Our description method is based on a comprehensive analysis of the existing publications in the domain. When our description method is applied by the research community, future publications will be easier to categorize, compare and extend. Our method can also serve as a basis to evaluate the novelty of hiding methods proposed in the future.
Selecting the top-quality item through crowd scoring
Venue: arXiv cs.HC 2017
Year: 2017

We investigate crowdsourcing algorithms for finding the top-quality item within a large collection of objects with unknown intrinsic quality values. This is an important problem with many relevant applications, for example in networked recommendation systems. The core of the algorithms is that objects are distributed to crowd workers, who return a noisy and biased evaluation. All received evaluations are then combined, to identify the top-quality object. We first present a simple probabilistic model for the system under investigation. Then, we devise and study a class of efficient adaptive algorithms to assign in an effective way objects to workers. We compare the performance of several algorithms, which correspond to different choices of the design parameters/metrics. In the simulations we show that some of the algorithms achieve near optimal performance for a suitable setting of the system parameters.
Dynamic Transmit Covariance Design in MIMO Fading Systems With Unknown Channel Distributions and Inaccurate Channel State Information
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers dynamic transmit covariance design in point-to-point MIMO fading systems with unknown channel state distributions and inaccurate channel state information subject to both long term and short term power constraints. First, the case of instantaneous but possibly inaccurate channel state information at the transmitter (CSIT) is treated. By extending the drift-plus-penalty technique, a dynamic transmit covariance policy is developed and is shown to approach optimality with an $O(δ)$ gap, where $δ$ is the inaccuracy measure of CSIT, regardless of the channel state distribution and without requiring knowledge of this distribution. Next, the case of delayed and inaccurate channel state information is considered. The optimal transmit covariance solution that maximizes the ergodic capacity is fundamentally different in this case, and a different online algorithm based on convex projections is developed. The proposed algorithm for this delayed-CSIT case also has an $O(δ)$ optimality gap, where $δ$ is again the inaccuracy measure of CSIT.
Secret Key Generation with Limited Interaction
Venue: arXiv cs.IT 2017
Year: 2017

A basic two-terminal secret key generation model is considered, where the interactive communication rate between the terminals may be limited, and in particular may not be enough to achieve the maximum key rate. We first prove a multi-letter characterization of the key-communication rate region (where the number of auxiliary random variables depend on the number of rounds of the communication), and then provide an equivalent but simpler characterization in terms of concave envelopes in the case of unlimited number of rounds. Two extreme cases are given special attention. First, in the regime of very low communication rates, the \emph{key bits per interaction bit} (KBIB) is expressed with a new "symmetric strong data processing constant", which has a concave envelope characterization analogous to that of the conventional strong data processing constant. The symmetric strong data processing constant can be upper bounded by the supremum of the maximal correlation coefficient over a set of distributions, which allows us to determine the KBIB for binary symmetric sources, and conclude, in particular, that the interactive scheme is not more efficient than the one-way scheme at least in the low communication-rate regime. Second, a new characterization of the \emph{minimum interaction rate needed for achieving the maximum key rate} (MIMK) is given, and we resolve a conjecture by Tyagi regarding the MIMK for (possibly nonsymmetric) binary sources. We also propose a new conjecture for binary symmetric sources that the interactive scheme is not more efficient than the one-way scheme at any communication rate.
Space-Time Representation of People Based on 3D Skeletal Data: A Review
Venue: arXiv cs.CV 2017
Year: 2017

Spatiotemporal human representation based on 3D visual perception data is a rapidly growing research area. Based on the information sources, these representations can be broadly categorized into two groups based on RGB-D information or 3D skeleton data. Recently, skeleton-based human representations have been intensively studied and kept attracting an increasing attention, due to their robustness to variations of viewpoint, human body scale and motion speed as well as the realtime, online performance. This paper presents a comprehensive survey of existing space-time representations of people based on 3D skeletal data, and provides an informative categorization and analysis of these methods from the perspectives, including information modality, representation encoding, structure and transition, and feature engineering. We also provide a brief overview of skeleton acquisition devices and construction methods, enlist a number of public benchmark datasets with skeleton data, and discuss potential future research directions.
Fractal social organization as a foundation to pervasive social computing services
Venue: arXiv cs.CY 2017
Year: 2017

Pervasive social computing is a promising approach that promises to empower both the individual and the whole and thus candidates itself as a foundation to the "smarter" social organizations that our new turbulent and resource-scarce worlds so urgently requires. In this contribution we first identify those that we consider as the major requirements to be fulfilled in order to realize an effective pervasive social computing infrastructure. We then conjecture that our service-oriented community and fractal social organization fulfill those requirements and therefore constitute an effective strategy to design pervasive social computing infrastructures. In order to motivate our conjecture, in this paper we discuss a model of social translucence and discuss fractal social organization as a referral service empowering a social system's parts and whole.
Complexity of choosability with a small palette of colors
Venue: arXiv cs.DM 2017
Year: 2017

A graph is $\ell$-choosable if, for any choice of lists of $\ell$ colors for each vertex, there is a list coloring, which is a coloring where each vertex receives a color from its list. We study complexity issues of choosability of graphs when the number $k$ of colors is limited. We get results which differ surprisingly from the usual case where $k$ is implicit and which extend known results for the usual case. We also exhibit some classes of graphs (defined by structural properties of their blocks) which are choosable.
Argumentation Mining in User-Generated Web Discourse
Venue: arXiv cs.CL 2017
Year: 2017

The goal of argumentation mining, an evolving research field in computational linguistics, is to design methods capable of analyzing people's argumentation. In this article, we go beyond the state of the art in several ways. (i) We deal with actual Web data and take up the challenges given by the variety of registers, multiple domains, and unrestricted noisy user-generated Web discourse. (ii) We bridge the gap between normative argumentation theories and argumentation phenomena encountered in actual data by adapting an argumentation model tested in an extensive annotation study. (iii) We create a new gold standard corpus (90k tokens in 340 documents) and experiment with several machine learning methods to identify argument components. We offer the data, source codes, and annotation guidelines to the community under free licenses. Our findings show that argumentation mining in user-generated Web discourse is a feasible but challenging task.