OpenRaiser/Intern-Atlas huggingface dataset:
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation
Venue: arXiv cs.CC 2016
Year: 2016

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$, $\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and a proof of $\tilde{O}(K \cdot d)$ length, and $\bullet$ the Verifier tosses $\textrm{poly}(\log(dK|{\mathbb F}|/\varepsilon))$ coins and can check the proof in about $\tilde{O}(K \cdot(n + d) + s)$ time, with probability of error less than $\varepsilon$. For small degree $d$, this "Merlin-Arthur" proof system (a.k.a. MA-proof system) runs in nearly-linear time, and has many applications. For example, we obtain MA-proof systems that run in $c^{n}$ time (for various $c < 2$) for the Permanent, $\#$Circuit-SAT for all sublinear-depth circuits, counting Hamiltonian cycles, and infeasibility of $0$-$1$ linear programs. In general, the value of any polynomial in Valiant's class ${\sf VP}$ can be certified faster than "exhaustive summation" over all possible assignments. These results strongly refute a Merlin-Arthur Strong ETH and Arthur-Merlin Strong ETH posed by Russell Impagliazzo and others. We also give a three-round (AMA) proof system for quantified Boolean formulas running in $2^{2n/3+o(n)}$ time, nearly-linear time MA-proof systems for counting orthogonal vectors in a collection and finding Closest Pairs in the Hamming metric, and a MA-proof system running in $n^{k/2+O(1)}$-time for counting $k$-cliques in graphs. We point to some potential future directions for refuting the Nondeterministic Strong ETH.
A Theoretical Analysis of Two-Stage Recommendation for Cold-Start Collaborative Filtering
Venue: arXiv cs.IR 2016
Year: 2016

In this paper, we present a theoretical framework for tackling the cold-start collaborative filtering problem, where unknown targets (items or users) keep coming to the system, and there is a limited number of resources (users or items) that can be allocated and related to them. The solution requires a trade-off between exploitation and exploration as with the limited recommendation opportunities, we need to, on one hand, allocate the most relevant resources right away, but, on the other hand, it is also necessary to allocate resources that are useful for learning the target's properties in order to recommend more relevant ones in the future. In this paper, we study a simple two-stage recommendation combining a sequential and a batch solution together. We first model the problem with the partially observable Markov decision process (POMDP) and provide an exact solution. Then, through an in-depth analysis over the POMDP value iteration solution, we identify that an exact solution can be abstracted as selecting resources that are not only highly relevant to the target according to the initial-stage information, but also highly correlated, either positively or negatively, with other potential resources for the next stage. With this finding, we propose an approximate solution to ease the intractability of the exact solution. Our initial results on synthetic data and the Movie Lens 100K dataset confirm the performance gains of our theoretical development and analysis.
Scalable Constrained Clustering: A Generalized Spectral Method
Venue: arXiv cs.SI 2016
Year: 2016

We present a simple spectral approach to the well-studied constrained clustering problem. It captures constrained clustering as a generalized eigenvalue problem with graph Laplacians. The algorithm works in nearly-linear time and provides concrete guarantees for the quality of the clusters, at least for the case of 2-way partitioning. In practice this translates to a very fast implementation that consistently outperforms existing spectral approaches both in speed and quality.
Sparsity in Dynamics of Spontaneous Subtle Emotions: Analysis \& Application
Venue: arXiv cs.CV 2016
Year: 2016

Spontaneous subtle emotions are expressed through micro-expressions, which are tiny, sudden and short-lived dynamics of facial muscles; thus poses a great challenge for visual recognition. The abrupt but significant dynamics for the recognition task are temporally sparse while the rest, irrelevant dynamics, are temporally redundant. In this work, we analyze and enforce sparsity constrains to learn significant temporal and spectral structures while eliminate irrelevant facial dynamics of micro-expressions, which would ease the challenge in the visual recognition of spontaneous subtle emotions. The hypothesis is confirmed through experimental results of automatic spontaneous subtle emotion recognition with several sparsity levels on CASME II and SMIC, the only two publicly available spontaneous subtle emotion databases. The overall performances of the automatic subtle emotion recognition are boosted when only significant dynamics are preserved from the original sequences.
Spectral-Efficiency Analysis of Massive MIMO Systems in Centralized and Distributed Schemes
Venue: arXiv cs.IT 2016
Year: 2016

This paper analyzes the spectral efficiency of massive multiple-input multiple-output (MIMO) systems in both centralized and distributed configurations, referred to as C-MIMO and D-MIMO, respectively. By accounting for real environmental parameters and antenna characteristics, namely, path loss, shadowing effect, multi-path fading and antenna correlation, a novel comprehensive channel model is first proposed in closed-form, which is applicable to both types of MIMO schemes. Then, based on the proposed model, the asymptotic behavior of the spectral efficiency of the MIMO channel under both the centralized and distributed configurations is analyzed and compared in exact forms, by exploiting the theory of very long random vectors. Afterwards, a case study is performed by applying the obtained results into MIMO networks with circular coverage. In such a case, it is attested that for the D-MIMO of cell radius $r_{\mathrm{c}}$ and circular antenna array of radius~$r_{\mathrm{a}}$, the optimal value of~$r_{\mathrm{a}}$ that maximizes the average spectral efficiency is accurately established by $r_{\mathrm{a}}^{\mathrm{opt}}=r_{\mathrm{c}}/1.31$. Monte Carlo simulation results corroborate the developed spectral-efficiency analysis.
Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints
Venue: arXiv cs.PL 2016
Year: 2016

We study the semantic foundation of expressive probabilistic programming languages, that support higher-order functions, continuous distributions, and soft constraints (such as Anglican, Church, and Venture). We define a metalanguage (an idealised version of Anglican) for probabilistic computation with the above features, develop both operational and denotational semantics, and prove soundness, adequacy, and termination. They involve measure theory, stochastic labelled transition systems, and functor categories, but admit intuitive computational readings, one of which views sampled random variables as dynamically allocated read-only variables. We apply our semantics to validate nontrivial equations underlying the correctness of certain compiler optimisations and inference algorithms such as sequential Monte Carlo simulation. The language enables defining probability distributions on higher-order functions, and we study their properties.
Lotka's Inverse Square Law of Scientific Productivity: Its Methods and Statistics
Venue: arXiv cs.DL 2016
Year: 2016

This brief communication analyzes the statistics and methods Lotka used to derive his inverse square law of scientific productivity from the standpoint of modern theory. It finds that he violated the norms of this theory by extremely truncating his data on the right. It also proves that Lotka himself played an important role in establishing the commonly used method of identifying power-law behavior by the R^2 fit to a regression line on a log-log plot that modern theory considers unreliable by basing the derivation of his law on this very method.
Joint Crosstalk-Avoidance and Error-Correction Coding for Parallel Data Buses
Venue: arXiv cs.IT 2016
Year: 2016

Decreasing transistor sizes and lower voltage swings cause two distinct problems for communication in integrated circuits. First, decreasing inter-wire spacing increases interline capacitive coupling, which adversely affects transmission energy and delay. Second, lower voltage swings render the transmission susceptible to various noise sources. Coding can be used to address both these problems. So-called crosstalk-avoidance codes mitigate capacitive coupling, and traditional error-correction codes introduce resilience against channel errors. Unfortunately, crosstalk-avoidance and error-correction codes cannot be combined in a straightforward manner. On the one hand, crosstalk-avoidance encoding followed by error-correction encoding destroys the crosstalk-avoidance property. On the other hand, error-correction encoding followed by crosstalk-avoidance encoding causes the crosstalk-avoidance decoder to fail in the presence of errors. Existing approaches circumvent this difficulty by using additional bus wires to protect the parities generated from the output of the error-correction encoder, and are therefore inefficient. In this work we propose a novel joint crosstalk-avoidance and error-correction coding and decoding scheme that provides higher bus transmission rates compared to existing approaches. Our joint approach carefully embeds the parities such that the crosstalk-avoidance property is preserved. We analyze the rate and minimum distance of the proposed scheme. We also provide a density evolution analysis and predict iterative decoding thresholds for reliable communication under random bus erasures. This density evolution analysis is nonstandard, since the crosstalk-avoidance constraints are inherently nonlinear.
M2M Massive Access in LTE: RACH Performance Evaluation in a Smart City Scenario
Venue: arXiv cs.NI 2016
Year: 2016

Several studies assert that the random access procedure of the Long Term Evolution (LTE) cellular standard may not be effective whenever a massive number of simultaneous connection attempts are performed by terminals, as may happen in a typical Internet of Things or Smart City scenario. Nevertheless, simulation studies in real deployment scenarios are missing because many system-level simulators do not implement the LTE random access procedure in detail. In this paper, we propose a patch for the LTE module of ns-3, one of the most prominent open-source network simulators, to improve the accuracy of the routine that simulates the LTE Random Access Channel (RACH). The patched version of the random access procedure is compared with the default one and the issues arising from massive simultaneous access from mobile terminals in LTE are assessed via a simulation campaign.
Co-evolution of RDF Datasets
Venue: arXiv cs.DB 2016
Year: 2016

Linking Data initiatives have fostered the publication of large number of RDF datasets in the Linked Open Data (LOD) cloud, as well as the development of query processing infrastructures to access these data in a federated fashion. However, different experimental studies have shown that availability of LOD datasets cannot be always ensured, being RDF data replication required for envisioning reliable federated query frameworks. Albeit enhancing data availability, RDF data replication requires synchronization and conflict resolution when replicas and source datasets are allowed to change data over time, i.e., co-evolution management needs to be provided to ensure consistency. In this paper, we tackle the problem of RDF data co-evolution and devise an approach for conflict resolution during co-evolution of RDF datasets. Our proposed approach is property-oriented and allows for exploiting semantics about RDF properties during co-evolution management. The quality of our approach is empirically evaluated in different scenarios on the DBpedia-live dataset. Experimental results suggest that proposed proposed techniques have a positive impact on the quality of data in source datasets and replicas.
Towards Programmable Network Dynamics: A Chemistry-Inspired Abstraction for Hardware Design
Venue: arXiv cs.ET 2016
Year: 2016

Chemical algorithms are statistical algorithms described and represented as chemical reaction networks. They are particularly attractive for traffic shaping and general control of network dynamics; they are analytically tractable, they reinforce a strict state-to-dynamics relationship, they have configurable stability properties, and they are directly implemented in state-space using a high-level (graphical) representation. In this paper, we present a direct implementation of chemical algorithms on FPGA hardware. Besides substantially improving performance, we have achieved hardware-level programmability and re-configurability of these algorithms at runtime (not interrupting servicing) and in realtime (with sub-second latency). This opens an interesting perspective for expanding the currently limited scope of software defined networking and network virtualisation solutions, to include programmable control of network dynamics.
Optimal Composition Ordering Problems for Piecewise Linear Functions
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we introduce maximum composition ordering problems. The input is $n$ real functions $f_1,\dots,f_n:\mathbb{R}\to\mathbb{R}$ and a constant $c\in\mathbb{R}$. We consider two settings: total and partial compositions. The maximum total composition ordering problem is to compute a permutation $σ:[n]\to[n]$ which maximizes $f_{σ(n)}\circ f_{σ(n-1)}\circ\dots\circ f_{σ(1)}(c)$, where $[n]=\{1,\dots,n\}$. The maximum partial composition ordering problem is to compute a permutation $σ:[n]\to[n]$ and a nonnegative integer $k~(0\le k\le n)$ which maximize $f_{σ(k)}\circ f_{σ(k-1)}\circ\dots\circ f_{σ(1)}(c)$. We propose $O(n\log n)$ time algorithms for the maximum total and partial composition ordering problems for monotone linear functions $f_i$, which generalize linear deterioration and shortening models for the time-dependent scheduling problem. We also show that the maximum partial composition ordering problem can be solved in polynomial time if $f_i$ is of form $\max\{a_ix+b_i,c_i\}$ for some constants $a_i\,(\ge 0)$, $b_i$ and $c_i$. We finally prove that there exists no constant-factor approximation algorithm for the problems, even if $f_i$'s are monotone, piecewise linear functions with at most two pieces, unless P=NP.
A Deterministic Algorithm for Pliable Index Coding
Venue: arXiv cs.IT 2016
Year: 2016

Pliable index coding considers a server with m messages, and n clients where each has as side information a subset of the messages. We seek to minimize the number of transmissions the server should make, so that each client receives (any) one message she does not already have. Previous work has shown that the server can achieve this using O(\log^2(n)) transmissions and needs at least Ω(log(n)) transmissions in the worst case, but finding a code of optimal length is NP-hard. In this paper, we propose a deterministic algorithm that we prove achieves this upper bound, that is, in an order almost as the worst-case optimal code length. We also establish a connection between the pliable index coding problem and the minrank problem over a family of mixed matrices.
Information Decomposition on Structured Space
Venue: arXiv cs.IT 2016
Year: 2016

We build information geometry for a partially ordered set of variables and define the orthogonal decomposition of information theoretic quantities. The natural connection between information geometry and order theory leads to efficient decomposition algorithms. This generalization of Amari's seminal work on hierarchical decomposition of probability distributions on event combinations enables us to analyze high-order statistical interactions arising in neuroscience, biology, and machine learning.
Constructions of Snake-in-the-Box Codes under $\ell_{\infty}$-metric for Rank Modulation
Venue: arXiv cs.IT 2016
Year: 2016

In the rank modulation scheme, Gray codes are very useful in the realization of flash memories. For a Gray code in this scheme, two adjacent codewords are obtained by using one "push-to-the-top" operation. Moreover, snake-in-the-box codes under the $\ell_{\infty}$-metric are Gray codes, which can be capable of detecting one $\ell_{\infty}$-error. In this paper, we give two constructions of $\ell_{\infty}$-snakes. On the one hand, inspired by Yehezkeally and Schwartz's construction, we present a new construction of the $\ell_{\infty}$-snake. The length of this $\ell_{\infty}$-snake is longer than the length of the $\ell_{\infty}$-snake constructed by Yehezkeally and Schwartz. On the other hand, we also give another construction of $\ell_{\infty}$-snakes by using $\mathcal{K}$-snakes and obtain the longer $\ell_{\infty}$-snakes than the previously known ones.
Emotional Interaction between Artificial Companion Agents and the Elderly
Venue: arXiv cs.CY 2016
Year: 2016

Artificial companion agents are defined as hardware or software entities designed to provide companionship to a person. The senior population are facing a special demand for companionship. Artificial companion agents have been demonstrated to be useful in therapy, offering emotional companionship and facilitating socialization. However, there is lack of empirical studies on what the artificial agents should do and how they can communicate with human beings better. To address these functional research problems, we attempt to establish a model to guide artificial companion designers to meet the emotional needs of the elderly through fulfilling absent roles in their social interactions. We call this model the Role Fulfilling Model. This model aims to use role as a key concept to analyse the demands from the elderly for functionalities from an emotional perspective in artificial companion agent designs and technologies. To evaluate the effectiveness of this model, we proposed a serious game platform named Happily Aging in Place. This game will help us to involve a large scale of senior users through crowdsourcing to test our model and hypothesis. To improve the emotional communication between artificial companion agents and users, This book draft addresses an important but largely overlooked aspect of affective computing: how to enable companion agents to express mixed emotions with facial expressions? And furthermore, for different users, do individual heterogeneity affects the perception of the same facial expressions? Some preliminary results about gender differences have been found. The perception of facial expressions between different age groups or cultural backgrounds will be held in future study.
Towards a General Software Engineering Methodology for the Internet of Things
Venue: arXiv cs.SE 2016
Year: 2016

As research in the Internet of Thing area progresses, and a multitude of proposals exist to solve a variety of problems, the need for a general principled software engineering approach for the systematic development of IoT systems and applications arises. In this paper, by synthesizing form the state of the art in the area, we attempt at framing the key concepts and abstractions that revolve around the design and development of IoT systems and applications, and draft a software engineering methodology centered on these abstractions.
Asymptotic Optimality of Massive MIMO Systems Using Densely Spaced Transmit Antennas
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a deterministic physical model of massive multiple-input multiple-output (MIMO) systems with uniform linear antenna arrays. It is known that the maximum spatial degrees of freedom is achieved by spacing antenna elements at half the carrier wavelength. The purpose of this paper is to investigate the impacts of spacing antennas more densely than the critical separation. The achievable rates of MIMO systems are evaluated in the large-system limit, where the lengths of transmit and receive antenna arrays tend to infinity with the antenna separations kept constant. The main results are twofold: One is that, under a mild assumption of channel instances, spacing antennas densely cannot improve the capacity of MIMO systems normalized by the spatial degrees of freedom. The other is that the normalized achievable rate of quadrature phase-shift keying converges to the normalized capacity achieved by optimal Gaussian signaling, as the transmit antenna separation tends to zero after taking the large-system limit. The latter result is based on mathematical similarity between MIMO transmission and faster-than-Nyquist signaling in signal space representations.
A New Converse Bound for Coded Caching
Venue: arXiv cs.IT 2016
Year: 2016

An information-theoretic lower bound is developed for the caching system studied by Maddah-Ali and Niesen. By comparing the proposed lower bound with the decentralized coded caching scheme of Maddah-Ali and Niesen, the optimal memory--rate tradeoff is characterized to within a multiplicative gap of $4.7$ for the worst case, improving the previous analytical gap of $12$. Furthermore, for the case when users' requests follow the uniform distribution, the multiplicative gap is tightened to $4.7$, improving the previous analytical gap of $72$. As an independent result of interest, for the single-user average case in which the user requests multiple files, it is proved that caching the most requested files is optimal.
A Confidence-Based Approach for Balancing Fairness and Accuracy
Venue: arXiv cs.LG 2016
Year: 2016

We study three classical machine learning algorithms in the context of algorithmic fairness: adaptive boosting, support vector machines, and logistic regression. Our goal is to maintain the high accuracy of these learning algorithms while reducing the degree to which they discriminate against individuals because of their membership in a protected group. Our first contribution is a method for achieving fairness by shifting the decision boundary for the protected group. The method is based on the theory of margins for boosting. Our method performs comparably to or outperforms previous algorithms in the fairness literature in terms of accuracy and low discrimination, while simultaneously allowing for a fast and transparent quantification of the trade-off between bias and error. Our second contribution addresses the shortcomings of the bias-error trade-off studied in most of the algorithmic fairness literature. We demonstrate that even hopelessly naive modifications of a biased algorithm, which cannot be reasonably said to be fair, can still achieve low bias and high accuracy. To help to distinguish between these naive algorithms and more sensible algorithms we propose a new measure of fairness, called resilience to random bias (RRB). We demonstrate that RRB distinguishes well between our naive and sensible fairness algorithms. RRB together with bias and accuracy provides a more complete picture of the fairness of an algorithm.