OpenRaiser/Intern-Atlas huggingface dataset:
Joint In-Band Backhauling and Interference Mitigation in 5G Heterogeneous Networks
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we study the problem of joint inband backhauling and interference mitigation in 5G heterogeneous networks (HetNets) in which a massive multiple-input multipleoutput (MIMO) macro cell base station equipped with a large number of antennas, overlaid with self-backhauled small cells is assumed. This problem is cast as a network utility maximization subject to wireless backhaul constraints. Due to the non-tractability of the problem, we first resort to random matrix theory to get a closed-form expression of the achievable rate and transmit power in the asymptotic regime, i.e., as the number of antennas and users grows large. Subsequently, leveraging the framework of stochastic optimization, the problem is decoupled into dynamic scheduling of macro cell users and backhaul provisioning of small cells as a function of interference and backhaul links. Via simulations, we evaluate the performance gains of our proposed framework under different network architectures and low/high frequency bands. Our proposed HetNet method achieves the achievable average UE throughput of 1.7 Gbps as well as ensures 1 Gbps cell-edge UE throughput when serving 200 UEs per km2 at 28 GHz with 1 GHz bandwidth. In ultra-dense network, the UE throughput at 28 GHz achieves 62x gain as compared to 2.4 GHz.
Horn Fragments of the Halpern-Shoham Interval Temporal Logic (Technical Report)
Venue: arXiv cs.LO 2017
Year: 2017

We investigate the satisfiability problem for Horn fragments of the Halpern-Shoham interval temporal logic depending on the type (box or diamond) of the interval modal operators, the type of the underlying linear order (discrete or dense), and the type of semantics for the interval relations (reflexive or irreflexive). For example, we show that satisfiability of Horn formulas with diamonds is undecidable for any type of linear orders and semantics. On the contrary, satisfiability of Horn formulas with boxes is tractable over both discrete and dense orders under the reflexive semantics and over dense orders under the irreflexive semantics, but becomes undecidable over discrete orders under the irreflexive semantics. Satisfiability of binary Horn formulas with both boxes and diamonds is always undecidable under the irreflexive semantics.
Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection
Venue: arXiv cs.DS 2017
Year: 2017

We revisit the classic problem of estimating the degree distribution moments of an undirected graph. Consider an undirected graph $G=(V,E)$ with $n$ vertices, and define (for $s > 0$) $μ_s = \frac{1}{n}\cdot\sum_{v \in V} d^s_v$. Our aim is to estimate $μ_s$ within a multiplicative error of $(1+ε)$ (for a given approximation parameter $ε>0$) in sublinear time. We consider the sparse graph model that allows access to: uniform random vertices, queries for the degree of any vertex, and queries for a neighbor of any vertex. For the case of $s=1$ (the average degree), $\widetilde{O}(\sqrt{n})$ queries suffice for any constant $ε$ (Feige, SICOMP 06 and Goldreich-Ron, RSA 08). Gonen-Ron-Shavitt (SIDMA 11) extended this result to all integral $s > 0$, by designing an algorithms that performs $\widetilde{O}(n^{1-1/(s+1)})$ queries. We design a new, significantly simpler algorithm for this problem. In the worst-case, it exactly matches the bounds of Gonen-Ron-Shavitt, and has a much simpler proof. More importantly, the running time of this algorithm is connected to the degeneracy of $G$. This is (essentially) the maximum density of an induced subgraph. For the family of graphs with degeneracy at most $α$, it has a query complexity of $\widetilde{O}\left(\frac{n^{1-1/s}}{μ^{1/s}_s} \Big(α^{1/s} + \min\{α,μ^{1/s}_s\}\Big)\right) = \widetilde{O}(n^{1-1/s}α/μ^{1/s}_s)$. Thus, for the class of bounded degeneracy graphs (which includes all minor closed families and preferential attachment graphs), we can estimate the average degree in $\widetilde{O}(1)$ queries, and can estimate the variance of the degree distribution in $\widetilde{O}(\sqrt{n})$ queries. This is a major improvement over the previous worst-case bounds. Our key insight is in designing an estimator for $μ_s$ that has low variance when $G$ does not have large dense subgraphs.
Epipolar Geometry Based On Line Similarity
Venue: arXiv cs.CV 2017
Year: 2017

It is known that epipolar geometry can be computed from three epipolar line correspondences but this computation is rarely used in practice since there are no simple methods to find corresponding lines. Instead, methods for finding corresponding points are widely used. This paper proposes a similarity measure between lines that indicates whether two lines are corresponding epipolar lines and enables finding epipolar line correspondences as needed for the computation of epipolar geometry. A similarity measure between two lines, suitable for video sequences of a dynamic scene, has been previously described. This paper suggests a stereo matching similarity measure suitable for images. It is based on the quality of stereo matching between the two lines, as corresponding epipolar lines yield a good stereo correspondence. Instead of an exhaustive search over all possible pairs of lines, the search space is substantially reduced when two corresponding point pairs are given. We validate the proposed method using real-world images and compare it to state-of-the-art methods. We found this method to be more accurate by a factor of five compared to the standard method using seven corresponding points and comparable to the 8-points algorithm.
Joint DOA and Frequency Estimation with Sub-Nyquist Sampling
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, to jointly estimate the frequency and the direction-of-arrival(DOA) of the narrowband far-field signals, a novel array receiver architecture is presented by the concept of the sub-Nyquist sampling techniques. In particular, our contribution is threefold. i) First, we propose a time-space union signal reception model for receiving array signals, where the sub-Nyquist sampling techniques and arbitrary array geometries are employed to decrease the time-domain sampling rate and improve the DOA estimation accuracy. A better joint estimation is obtained in the higher time-space union space. ii) Second, two joint estimation algorithms are proposed for the receiving model. One is based on a trilinear decomposition from the third-order tensor theory and the other is based on subspace decomposition. iii) Third, we derive the corresponding Cramér\text{-}Rao Bound (CRB) for frequency and DOA estimates. In the case of the branch number of our architecture is equal to the reduction factor of the sampling rate, it is observed that the CRB is robust in terms of the number of signals, while the CRB based on the Nyquist sampling scheme will increase with respect to the number of signals. In addition, the new steer vectors of the union time-space model are completely uncorrelated under the limited number of sensors, which improves the estimation performance. Furthermore, the simulation results demonstrate that our estimates via the receiver architecture associated with the proposed algorithms closely match the CRB according to the noise levels, the branch number and the source number as well.
Better Strategyproof Mechanisms without Payments or Prior --- An Analytic Approach
Venue: arXiv cs.GT 2017
Year: 2017

We revisit the problem of designing strategyproof mechanisms for allocating divisible items among two agents who have linear utilities, where payments are disallowed and there is no prior information on the agents' preferences. The objective is to design strategyproof mechanisms which are competitive against the most efficient (but not strategyproof) mechanism. For the case with two items: (1) We provide a set of sufficient conditions for strategyproofness. (2) We use an analytic approach to derive strategyproof mechanisms which are more competitive than all prior strategyproof mechanisms. (3) We improve the linear-program-based proof of Guo and Conitzer to show new upper bounds on competitive ratios. (4) We provide the first "mathematical" upper bound proof. For the cases with any number of items: (1) We build on the Partial Allocation mechanisms introduced by Cole et al. to design a strategyproof mechanism which is 0.67776-competitive, breaking the 2/3 barrier. (2) We propose a new subclass of strategyproof mechanisms called Dynamical-Increasing-Price mechanisms, where each agent purchases the items using virtual money, and the prices of the items depend on other agents' preferences.
Triplet Probabilistic Embedding for Face Verification and Clustering
Venue: arXiv cs.CV 2017
Year: 2017

Despite significant progress made over the past twenty five years, unconstrained face verification remains a challenging problem. This paper proposes an approach that couples a deep CNN-based approach with a low-dimensional discriminative embedding learned using triplet probability constraints to solve the unconstrained face verification problem. Aside from yielding performance improvements, this embedding provides significant advantages in terms of memory and for post-processing operations like subject specific clustering. Experiments on the challenging IJB-A dataset show that the proposed algorithm performs comparably or better than the state of the art methods in verification and identification metrics, while requiring much less training data and training time. The superior performance of the proposed method on the CFP dataset shows that the representation learned by our deep CNN is robust to extreme pose variation. Furthermore, we demonstrate the robustness of the deep features to challenges including age, pose, blur and clutter by performing simple clustering experiments on both IJB-A and LFW datasets.
Easy to Win, Hard to Master: Optimal Strategies in Parity Games with Costs
Venue: arXiv cs.LO 2017
Year: 2017

The winning condition of a parity game with costs requires an arbitrary, but fixed bound on the cost incurred between occurrences of odd colors and the next occurrence of a larger even one. Such games quantitatively extend parity games while retaining most of their attractive properties, i.e, determining the winner is in NP and co-NP and one player has positional winning strategies. We show that the characteristics of parity games with costs are vastly different when asking for strategies realizing the minimal such bound: The solution problem becomes PSPACE-complete and exponential memory is both necessary in general and always sufficient. Thus, solving and playing parity games with costs optimally is harder than just winning them. Moreover, we show that the tradeoff between the memory size and the realized bound is gradual in general. All these results hold true for both a unary and binary encoding of costs. Moreover, we investigate Streett games with costs. Here, playing optimally is as hard as winning, both in terms of complexity and memory.
Privacy, Discovery, and Authentication for the Internet of Things
Venue: arXiv cs.CR 2017
Year: 2017

Automatic service discovery is essential to realizing the full potential of the Internet of Things (IoT). While discovery protocols like Multicast DNS, Apple AirDrop, and Bluetooth Low Energy have gained widespread adoption across both IoT and mobile devices, most of these protocols do not offer any form of privacy control for the service, and often leak sensitive information such as service type, device hostname, device owner's identity, and more in the clear. To address the need for better privacy in both the IoT and the mobile landscape, we develop two protocols for private service discovery and private mutual authentication. Our protocols provide private and authentic service advertisements, zero round-trip (0-RTT) mutual authentication, and are provably secure in the Canetti-Krawczyk key-exchange model. In contrast to alternatives, our protocols are lightweight and require minimal modification to existing key-exchange protocols. We integrate our protocols into an existing open-source distributed applications framework, and provide benchmarks on multiple hardware platforms: Intel Edisons, Raspberry Pis, smartphones, laptops, and desktops. Finally, we discuss some privacy limitations of the Apple AirDrop protocol (a peer-to-peer file sharing mechanism) and show how to improve the privacy of Apple AirDrop using our private mutual authentication protocol.
A Review of Co-saliency Detection Technique: Fundamentals, Applications, and Challenges
Venue: arXiv cs.CV 2017
Year: 2017

Co-saliency detection is a newly emerging and rapidly growing research area in computer vision community. As a novel branch of visual saliency, co-saliency detection refers to the discovery of common and salient foregrounds from two or more relevant images, and can be widely used in many computer vision tasks. The existing co-saliency detection algorithms mainly consist of three components: extracting effective features to represent the image regions, exploring the informative cues or factors to characterize co-saliency, and designing effective computational frameworks to formulate co-saliency. Although numerous methods have been developed, the literature is still lacking a deep review and evaluation of co-saliency detection techniques. In this paper, we aim at providing a comprehensive review of the fundamentals, challenges, and applications of co-saliency detection. Specifically, we provide an overview of some related computer vision works, review the history of co-saliency detection, summarize and categorize the major algorithms in this research area, discuss some open issues in this area, present the potential applications of co-saliency detection, and finally point out some unsolved challenges and promising future works. We expect this review to be beneficial to both fresh and senior researchers in this field, and give insights to researchers in other related areas regarding the utility of co-saliency detection algorithms.
The Manne et al. self-stabilizing 2/3-approximation matching algorithm is sub-exponential
Venue: arXiv cs.DC 2017
Year: 2017

Manne et al. designed the first algorithm computing a maximal matching that is a 2/3 -approximation of the maximum matching in $O(^2n)$ moves. However, the complexity tightness was not proved. In this paper, we exhibit a sub-exponential execution of this matching algorithm.
Closed-form, robust and accurate multi-frequency phase unwrapping: frequency design and algorithm
Venue: arXiv cs.IT 2017
Year: 2017

A closed-form algorithm, named "concerto", is proposed for phase-based distance estimation in multi-frequency phase unwrapping (MFPU) system. The concerto method consists of three coherent estimation stages,i.e., initial modified BW estimation, residual error estimation and LS estimation , each of which has a closed-form expression and cooperates closely with each other like a concerto. Due to a specially designed frequency pattern, concerto is reliable, accurate, and computationally simple. Meanwhile, measurement frequency selection is an easier task. Performance comparisons with beat wavelength (BW), excess fractions (EF) and Chinese remainder theorem (CRT) method confirm that our method outperforms these methods both in accuracy and reliability and can asymptotically achieve the Cramer-Rao bound (CRB).
Adaptive Candidate Generation for Scalable Edge-discovery Tasks on Data Graphs
Venue: arXiv cs.AI 2017
Year: 2017

Several `edge-discovery' applications over graph-based data models are known to have worst-case quadratic time complexity in the nodes, even if the discovered edges are sparse. One example is the generic link discovery problem between two graphs, which has invited research interest in several communities. Specific versions of this problem include link prediction in social networks, ontology alignment between metadata-rich RDF data, approximate joins, and entity resolution between instance-rich data. As large datasets continue to proliferate, reducing quadratic complexity to make the task practical is an important research problem. Within the entity resolution community, the problem is commonly referred to as blocking. A particular class of learnable blocking schemes is known as Disjunctive Normal Form (DNF) blocking schemes, and has emerged as state-of-the art for homogeneous (i.e. same-schema) tabular data. Despite the promise of these schemes, a formalism or learning framework has not been developed for them when input data instances are generic, attributed graphs possessing both node and edge heterogeneity. With such a development, the complexity-reducing scope of DNF schemes becomes applicable to a variety of problems, including entity resolution and type alignment between heterogeneous graphs, and link prediction in networks represented as attributed graphs. This paper presents a graph-theoretic formalism for DNF schemes, and investigates their learnability in an optimization framework. We also briefly describe an empirical case study encapsulating some of the principles in this paper.
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
Venue: arXiv cs.CC 2017
Year: 2017

For an $n$-variate order-$d$ tensor $A$, define $ A_{\max} := \sup_{\| x \|_2 = 1} \langle A , x^{\otimes d} \rangle$ to be the maximum value taken by the tensor on the unit sphere. It is known that for a random tensor with i.i.d $\pm 1$ entries, $A_{\max} \lesssim \sqrt{n\cdot d\cdot\log d}$ w.h.p. We study the problem of efficiently certifying upper bounds on $A_{\max}$ via the natural relaxation from the Sum of Squares (SoS) hierarchy. Our results include: - When $A$ is a random order-$q$ tensor, we prove that $q$ levels of SoS certifies an upper bound $B$ on $A_{\max}$ that satisfies \[ B ~~~~\leq~~ A_{\max} \cdot \biggl(\frac{n}{q^{\,1-o(1)}}\biggr)^{q/4-1/2} \quad \text{w.h.p.} \] Our upper bound improves a result of Montanari and Richard (NIPS 2014) when $q$ is large. - We show the above bound is the best possible up to lower order terms, namely the optimum of the level-$q$ SoS relaxation is at least \[ A_{\max} \cdot \biggl(\frac{n}{q^{\,1+o(1)}}\biggr)^{q/4-1/2} \ . \] - When $A$ is a random order-$d$ tensor, we prove that $q$ levels of SoS certifies an upper bound $B$ on $A_{\max}$ that satisfies \[ B ~~\leq ~~ A_{\max} \cdot \biggl(\frac{\widetilde{O}(n)}{q}\biggr)^{d/4 - 1/2} \quad \text{w.h.p.} \] For growing $q$, this improves upon the bound certified by constant levels of SoS. This answers in part, a question posed by Hopkins, Shi, and Steurer (COLT 2015), who established the tight characterization for constant levels of SoS.
Do logarithmic proximity measures outperform plain ones in graph clustering?
Venue: arXiv cs.LG 2017
Year: 2017

We consider a number of graph kernels and proximity measures including commute time kernel, regularized Laplacian kernel, heat kernel, exponential diffusion kernel (also called "communicability"), etc., and the corresponding distances as applied to clustering nodes in random graphs and several well-known datasets. The model of generating random graphs involves edge probabilities for the pairs of nodes that belong to the same class or different predefined classes of nodes. It turns out that in most cases, logarithmic measures (i.e., measures resulting after taking logarithm of the proximities) perform better while distinguishing underlying classes than the "plain" measures. A comparison in terms of reject curves of inter-class and intra-class distances confirms this conclusion. A similar conclusion can be made for several well-known datasets. A possible origin of this effect is that most kernels have a multiplicative nature, while the nature of distances used in cluster algorithms is an additive one (cf. the triangle inequality). The logarithmic transformation is a tool to transform the first nature to the second one. Moreover, some distances corresponding to the logarithmic measures possess a meaningful cutpoint additivity property. In our experiments, the leader is usually the logarithmic Communicability measure. However, we indicate some more complicated cases in which other measures, typically, Communicability and plain Walk, can be the winners.
Organic Primitives: Synthesis and Design of pH-Reactive Materials using Molecular I/O for Sensing, Actuation, and Interaction
Venue: arXiv cs.HC 2017
Year: 2017

In this paper we present Organic Primitives, an enabling toolbox that expands upon the library of input-output devices in HCI and facilitates the design of interactions with organic, fluid-based systems. We formulated color, odor and shape changing material primitives which act as sensor-actuators that convert pH signals into human-readable outputs. Food-grade organic molecules anthocyanin, vanillin, and chitosan were employed as dopants to synthesize materials which output a spectrum of colors, degrees of shape deformation, and switch between odorous and non-odorous states. We evaluated the individual output properties of our sensor-actuators to assess the rate, range, and reversibility of the changes as a function of pH 2-10. We present a design space with techniques for enhancing the functionality of the material primitives, and offer passive and computational methods for controlling the material interfaces. Finally, we explore applications enabled by Organic Primitives under four contexts: environmental, cosmetic, edible, and interspecies.
Enhancing semantic expressivity in the cultural heritage domain: exposing the Zeri Photo Archive as Linked Open Data
Venue: arXiv cs.DL 2017
Year: 2017

Describing cultural heritage objects from the perspective of Linked Open Data (LOD) is not a trivial task. The process often requires not only choosing pertinent ontologies, but also developing new models that preserve the most information and express the semantic power of cultural heritage data. Indeed, data managed in archives, libraries and museums are complex objects themselves, which require a deep reflection on even non-conventional conceptual models. Starting from these considerations, this paper describes a research project: to expose the vastness of one of the most important collections of European cultural heritage, the Zeri Photo Archive, as Linked Open Data. We describe here the steps we undertook to this end: firstly, we developed two ad hoc ontologies for describing all the issues not completely covered by existent models (the F Entry and the OA Entry Ontology); then we mapped into RDF the descriptive elements used in the current Zeri Photo Archive catalog, converting into CIDOC-CRM and into the two new aforementioned models the source data based on the Italian content standards Scheda F (Photography Entry, in English) and Scheda OA (Work of Art Entry, in English); and finally, we created an RDF dataset of the output of the mapping that could show a result capable of demonstrating the complexity of our scenario.
Zero-Error Capacity of $P$-ary Shift Channels and FIFO Queues
Venue: arXiv cs.IT 2017
Year: 2017

The objects of study of this paper are communication channels in which the dominant type of noise are symbol shifts, the main motivating examples being timing and bit-shift channels. Two channel models are introduced and their zero-error capacities and zero-error-detection capacities determined by explicit constructions of optimal codes. Model A can be informally described as follows: 1) The information is stored in an $ n $-cell register, where each cell is either empty or contains a particle of one of $ P $ possible types, and 2) due to the imperfections of the device each of the particles may be shifted several cells away from its original position over time. Model B is an abstraction of a single-server queue: 1) The transmitter sends packets from a $ P $-ary alphabet through a queuing system with an infinite buffer and a First-In-First-Out (FIFO) service procedure, and 2) each packet is being processed by the server for a random number of time slots. More general models including additional types of noise that the particles/packets can experience are also studied, as are the continuous-time versions of these problems.