OpenRaiser/Intern-Atlas huggingface dataset:
Bichromatic compatible matchings
Venue: arXiv cs.CG 2013
Year: 2013

For a set $R$ of $n$ red points and a set $B$ of $n$ blue points, a $BR$-matching is a non-crossing geometric perfect matching where each segment has one endpoint in $B$ and one in $R$. Two $BR$-matchings are compatible if their union is also non-crossing. We prove that, for any two distinct $BR$-matchings $M$ and $M'$, there exists a sequence of $BR$-matchings $M = M_1, ..., M_k = M'$ such that $M_{i-1} $ is compatible with $M_i$. This implies the connectivity of the compatible bichromatic matching graph containing one node for each bichromatic matching and an edge joining each pair of compatible matchings, thereby answering the open problem posed by Aichholzer et al. in "Compatible matchings for bichromatic plane straight-line graphs"
Logit Dynamics with Concurrent Updates for Local-Interaction Games
Venue: arXiv cs.GT 2013
Year: 2013

Logit choice dynamics are a family of randomized best response dynamics based on the logit choice function [McFadden, 1974], used for modeling players with limited rationality and knowledge. In this paper we study the all-logit dynamics, where at each time step all players concurrently update their strategies according to the logit choice function. In the well studied one-logit dynamics [Blume, 1993] instead at each step only one randomly chosen player is allowed to update. We study properties of the all-logit dynamics in the context of local interaction games, a class of games that has been used to model complex social phenomena and physical systems. In a local interaction game, players are the vertices of a social graph whose edges are two-player potential games. Each player picks one strategy to be played for all the games she is involved in and the payoff of the player is the sum of the payoffs from each of the games. We prove that local interaction games characterize the class of games for which the all-logit dynamics is reversible. We then compare the stationary behavior of one-logit and all-logit dynamics. Specifically, we look at the expected value of a notable class of observables, that we call decomposable observables. We prove that the difference between the expected values of the observables at stationarity for the two dynamics depends only on the rationality level beta and on the distance of the social graph from a bipartite graph. In particular, if the social graph is bipartite then decomposable observables have the same expected value. Finally, we show that the mixing time of the all-logit dynamics has the same twofold behavior that has been highlighted in the case of the one-logit: for some games it exponentially depends on the rationality level beta, whereas for other games it can be upper bounded by a function independent from beta.
Fundamental Limits of Communications in Interference Networks-Part III: Information Flow in Strong Interference Regime
Venue: arXiv cs.IT 2013
Year: 2013

This third part of the paper is related to the study of information flow in networks with strong interference. First, the two-receiver networks are considered. A unified outer bound for the capacity region of these networks is established. It is shown that this outer bound can be systematically translated into simple capacity outer bounds for special cases such as the two-user Classical Interference Channel (CIC) and the Broadcast Channel with Cognitive Relays (BCCR) with common information. For these channels, special cases are presented where our outer bounds are tight, which yield the exact capacity. More importantly, by using the derived outer bounds, a strong interference regime is identified for the general two-receiver interference networks with any arbitrary topology. This strong interference regime, which is represented by only two conditions, includes all previously known results for simple topologies such as the two-user CIC, the cognitive radio channel, and many others. Then, networks with arbitrary number of receivers are considered. Finding non-trivial strong interference regime for such networks, specifically for the CICs with more than two users, has been one of the open problems in network information theory. In this paper, we will give a solution to this problem. Specifically, a new approach is developed based on which one can obtain strong interference regimes not only for the multi-user CICs but also for any interference network of arbitrary large sizes. For this development, some new technical lemmas are proved which have a central role in the derivations. As a result, this paper establishes the first non-trivial capacity result for the multi-user classical interference channel. A general formula is also presented to derive strong interference conditions for any given network topology.
The K-User Interference Channel: Strong Interference Regime
Venue: arXiv cs.IT 2013
Year: 2013

This paper gives a solution to one of the long-standing open problems in network information theory: "What is the generalization of the strong interference regime to the K-user interference channel?"
Expectation-Maximization Gaussian-Mixture Approximate Message Passing
Venue: arXiv cs.IT 2013
Year: 2013

When recovering a sparse signal from noisy compressive linear measurements, the distribution of the signal's non-zero coefficients can have a profound effect on recovery mean-squared error (MSE). If this distribution was apriori known, then one could use computationally efficient approximate message passing (AMP) techniques for nearly minimum MSE (MMSE) recovery. In practice, though, the distribution is unknown, motivating the use of robust algorithms like LASSO---which is nearly minimax optimal---at the cost of significantly larger MSE for non-least-favorable distributions. As an alternative, we propose an empirical-Bayesian technique that simultaneously learns the signal distribution while MMSE-recovering the signal---according to the learned distribution---using AMP. In particular, we model the non-zero distribution as a Gaussian mixture, and learn its parameters through expectation maximization, using AMP to implement the expectation step. Numerical experiments on a wide range of signal classes confirm the state-of-the-art performance of our approach, in both reconstruction error and runtime, in the high-dimensional regime, for most (but not all) sensing operators.
Correction to "A Note on Gallager's Capacity Theorem for Waveform Channels"
Venue: arXiv cs.IT 2013
Year: 2013

We correct an alleged contradiction to Gallager's capacity theorem for waveform channels as presented in a poster at the 2012 IEEE International Symposium on Information Theory.
Diamond-Kite Adaptive Quadrilateral Meshing
Venue: arXiv cs.CG 2013
Year: 2013

We describe a family of quadrilateral meshes based on diamonds, rhombi with 60 and 120 degree angles, and kites with 60, 90, and 120 degree angles, that can be adapted to a local size function by local subdivision operations. Our meshes use a number of elements that is within a constant factor of the minimum possible for any mesh of bounded aspect ratio elements, graded by the same local size function, and is invariant under Laplacian smoothing. The vertices of our meshes form the centers of the circles in a pair of dual circle packings. The same vertex placement algorithm but a different mesh topology gives a pair of dual well-centered meshes adapted to the given size function.
Compressed Sensing off the Grid
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of estimating the frequency components of a mixture of s complex sinusoids from a random subset of n regularly spaced samples. Unlike previous work in compressed sensing, the frequencies are not assumed to lie on a grid, but can assume any values in the normalized frequency domain [0,1]. We propose an atomic norm minimization approach to exactly recover the unobserved samples. We reformulate this atomic norm minimization as an exact semidefinite program. Even with this continuous dictionary, we show that most sampling sets of size O(s log s log n) are sufficient to guarantee the exact frequency estimation with high probability, provided the frequencies are well separated. Numerical experiments are performed to illustrate the effectiveness of the proposed method.
Recent advances in bibliometric indexes and the PaperRank problem
Venue: arXiv cs.DL 2013
Year: 2013

Bibliometric indexes are customary used in evaluating the impact of scientific research, even though it is very well known that in different research areas they may range in very different intervals. Sometimes, this is evident even within a single given field of investigation making very difficult (and inaccurate) the assessment of scientific papers. On the other hand, the problem can be recast in the same framework which has allowed to efficiently cope with the ordering of web-pages, i.e., to formulate the PageRank of Google. For this reason, we call such problem the PaperRank problem, here solved by using a similar approach to that employed by PageRank. The obtained solution, which is mathematically grounded, will be used to compare the usual heuristics of the number of citations with a new one here proposed. Some numerical tests show that the new heuristics is much more reliable than the currently used ones, based on the bare number of citations. Moreover, we show that our model improves on recently proposed ones.
Low Rank Approximation and Regression in Input Sparsity Time
Venue: arXiv cs.DS 2013
Year: 2013

We design a new distribution over $\poly(r \eps^{-1}) \times n$ matrices $S$ so that for any fixed $n \times d$ matrix $A$ of rank $r$, with probability at least 9/10, $\norm{SAx}_2 = (1 \pm \eps)\norm{Ax}_2$ simultaneously for all $x \in \mathbb{R}^d$. Such a matrix $S$ is called a \emph{subspace embedding}. Furthermore, $SA$ can be computed in $\nnz(A) + \poly(d \eps^{-1})$ time, where $\nnz(A)$ is the number of non-zero entries of $A$. This improves over all previous subspace embeddings, which required at least $Ω(nd \log d)$ time to achieve this property. We call our matrices $S$ \emph{sparse embedding matrices}. Using our sparse embedding matrices, we obtain the fastest known algorithms for $(1+\eps)$-approximation for overconstrained least-squares regression, low-rank approximation, approximating all leverage scores, and $\ell_p$-regression. The leading order term in the time complexity of our algorithms is $O(\nnz(A))$ or $O(\nnz(A)\log n)$. We optimize the low-order $\poly(d/\eps)$ terms in our running times (or for rank-$k$ approximation, the $n*\poly(k/eps)$ term), and show various tradeoffs. For instance, we also use our methods to design new preconditioners that improve the dependence on $\eps$ in least squares regression to $\log 1/\eps$. Finally, we provide preliminary experimental results which suggest that our algorithms are competitive in practice.
Cooperative Regenerating Codes
Venue: arXiv cs.IT 2013
Year: 2013

One of the design objectives in distributed storage system is the minimization of the data traffic during the repair of failed storage nodes. By repairing multiple failures simultaneously and cooperatively, further reduction of repair traffic is made possible. A closed-form expression of the optimal tradeoff between the repair traffic and the amount of storage in each node for cooperative repair is given. We show that the points on the tradeoff curve can be achieved by linear cooperative regenerating codes, with an explicit bound on the required finite field size. The proof relies on a max-flow-min-cut-type theorem for submodular flow from combinatorial optimization. Two families of explicit constructions are given.
Wisdom of the Crowd: Incorporating Social Influence in Recommendation Models
Venue: arXiv cs.IR 2013
Year: 2013

Recommendation systems have received considerable attention recently. However, most research has been focused on improving the performance of collaborative filtering (CF) techniques. Social networks, indispensably, provide us extra information on people's preferences, and should be considered and deployed to improve the quality of recommendations. In this paper, we propose two recommendation models, for individuals and for groups respectively, based on social contagion and social influence network theory. In the recommendation model for individuals, we improve the result of collaborative filtering prediction with social contagion outcome, which simulates the result of information cascade in the decision-making process. In the recommendation model for groups, we apply social influence network theory to take interpersonal influence into account to form a settled pattern of disagreement, and then aggregate opinions of group members. By introducing the concept of susceptibility and interpersonal influence, the settled rating results are flexible, and inclined to members whose ratings are "essential".
Logic of Non-Monotonic Interactive Proofs (Formal Theory of Temporary Knowledge Transfer)
Venue: arXiv cs.LO 2013
Year: 2013

We propose a monotonic logic of internalised non-monotonic or instant interactive proofs (LiiP) and reconstruct an existing monotonic logic of internalised monotonic or persistent interactive proofs (LiP) as a minimal conservative extension of LiiP. Instant interactive proofs effect a fragile epistemic impact in their intended communities of peer reviewers that consists in the impermanent induction of the knowledge of their proof goal by means of the knowledge of the proof with the interpreting reviewer: If my peer reviewer knew my proof then she would at least then (in that instant) know that its proof goal is true. Their impact is fragile and their induction of knowledge impermanent in the sense of being the case possibly only at the instant of learning the proof. This accounts for the important possibility of internalising proofs of statements whose truth value can vary, which, as opposed to invariant statements, cannot have persistent proofs. So instant interactive proofs effect a temporary transfer of certain propositional knowledge (knowable ephemeral facts) via the transmission of certain individual knowledge (knowable non-monotonic proofs) in distributed systems of multiple interacting agents.
Explicit Simplicial Discretization of Distributed-Parameter Port-Hamiltonian Systems
Venue: arXiv cs.SY 2013
Year: 2013

Simplicial Dirac structures as finite analogues of the canonical Stokes-Dirac structure, capturing the topological laws of the system, are defined on simplicial manifolds in terms of primal and dual cochains related by the coboundary operators. These finite-dimensional Dirac structures offer a framework for the formulation of standard input-output finite-dimensional port-Hamiltonian systems that emulate the behavior of distributed-parameter port-Hamiltonian systems. This paper elaborates on the matrix representations of simplicial Dirac structures and the resulting port-Hamiltonian systems on simplicial manifolds. Employing these representations, we consider the existence of structural invariants and demonstrate how they pertain to the energy shaping of port-Hamiltonian systems on simplicial manifolds.
Constrained Fault-Tolerant Resource Allocation
Venue: arXiv cs.DS 2013
Year: 2013

In the Constrained Fault-Tolerant Resource Allocation (FTRA) problem, we are given a set of sites containing facilities as resources, and a set of clients accessing these resources. Specifically, each site i is allowed to open at most R_i facilities with cost f_i for each opened facility. Each client j requires an allocation of r_j open facilities and connecting j to any facility at site i incurs a connection cost c_ij. The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation (FTRA_{\infty}) [18] and the classical Fault-Tolerant Facility Location (FTFL) [13] problems: for every site i, FTRA_{\infty} does not have the constraint R_i, whereas FTFL sets R_i=1. These problems are said to be uniform if all r_j's are the same, and general otherwise. For the general metric FTRA, we first give an LP-rounding algorithm achieving the approximation ratio of 4. Then we show the problem reduces to FTFL, implying the ratio of 1.7245 from [3]. For the uniform FTRA, we provide a 1.52-approximation primal-dual algorithm in O(n^4) time, where n is the total number of sites and clients. We also consider the Constrained Fault-Tolerant k-Resource Allocation (k-FTRA) problem where additionally the total number of facilities can be opened across all sites is bounded by k. For the uniform k-FTRA, we give the first constant-factor approximation algorithm with a factor of 4. Note that the above results carry over to FTRA_{\infty} and k-FTRA_{\infty}.
Estimation in Phase-Shift and Forward Wireless Sensor Networks
Venue: arXiv cs.IT 2013
Year: 2013

We consider a network of single-antenna sensors that observe an unknown deterministic parameter. Each sensor applies a phase shift to the observation and the sensors simultaneously transmit the result to a multi-antenna fusion center (FC). Based on its knowledge of the wireless channel to the sensors, the FC calculates values for the phase factors that minimize the variance of the parameter estimate, and feeds this information back to the sensors. The use of a phase-shift-only transmission scheme provides a simplified analog implementation at the sensor, and also leads to a simpler algorithm design and performance analysis. We propose two algorithms for this problem, a numerical solution based on a relaxed semidefinite programming problem, and a closed-form solution based on the analytic constant modulus algorithm. Both approaches are shown to provide performance close to the theoretical bound. We derive asymptotic performance analyses for cases involving large numbers of sensors or large numbers of FC antennas, and we also study the impact of phase errors at the sensor transmitters. Finally, we consider the sensor selection problem, in which only a subset of the sensors is chosen to send their observations to the FC.
Subdivision Shell Elements with Anisotropic Growth
Venue: arXiv cs.NA 2013
Year: 2013

A thin shell finite element approach based on Loop's subdivision surfaces is proposed, capable of dealing with large deformations and anisotropic growth. To this end, the Kirchhoff-Love theory of thin shells is derived and extended to allow for arbitrary in-plane growth. The simplicity and computational efficiency of the subdivision thin shell elements is outstanding, which is demonstrated on a few standard loading benchmarks. With this powerful tool at hand, we demonstrate the broad range of possible applications by numerical solution of several growth scenarios, ranging from the uniform growth of a sphere, to boundary instabilities induced by large anisotropic growth. Finally, it is shown that the problem of a slowly and uniformly growing sheet confined in a fixed hollow sphere is equivalent to the inverse process where a sheet of fixed size is slowly crumpled in a shrinking hollow sphere in the frictionless, quasi-static, elastic limit.
Expressive Completeness of Metric Temporal Logic
Venue: arXiv cs.LO 2013
Year: 2013

Metric Temporal Logic (MTL) is a generalisation of Linear Temporal Logic in which the Until and Since modalities are annotated with intervals that express metric constraints. A seminal result of Hirshfeld and Rabinovich shows that over the reals, first-order logic with binary order relation < and unary function +1 is strictly more expressive than MTL with integer constants. Indeed they prove that no temporal logic whose modalities are definable by formulas of bounded quantifier depth can be expressively complete for FO(<,+1). In this paper we show the surprising result that if we allow unary functions +q, (q rational), in first-order logic and correspondingly allow rational constants in MTL, then the two logics have the same expressive power. This gives the first generalisation of Kamp's theorem on the expressive completeness of LTL for FO(<) to the quantitative setting. The proof of this result involves a generalisation of Gabbay's notion of separation.
On the Eigenvalues of Certain Matrices Over $\mathbb{Z}_m$
Venue: arXiv cs.DM 2013
Year: 2013

Let $m,n>1$ be integers and $\mathbb{P}_{n,m}$ be the point set of the projective $(n-1)$-space (defined by [2]) over the ring $\mathbb{Z}_m$of integers modulo $m$. Let $A_{n,m}=(a_{uv})$ be the matrix with rows and columns being labeled by elements of $\mathbb{P}_{n,m}$, where $a_{uv}=1$ if the inner product $< u,v >=0$ and $a_{uv}=0$ otherwise. Let $B_{n,m}=A_{n,m}A_{n,m}^t$. The eigenvalues of $B_{n,m}$ have been studied by [1, 2, 3], where their applications in the study of expanders and locally decodable codes were described. In this paper, we completely determine the eigenvalues of $B_{n,m}$ for general integers $m$ and $n$.
One-bit compressed sensing with non-Gaussian measurements
Venue: arXiv cs.IT 2013
Year: 2013

In one-bit compressed sensing, previous results state that sparse signals may be robustly recovered when the measurements are taken using Gaussian random vectors. In contrast to standard compressed sensing, these results are not extendable to natural non-Gaussian distributions without further assumptions, as can be demonstrated by simple counter-examples. We show that approximately sparse signals that are not extremely sparse can be accurately reconstructed from single-bit measurements sampled according to a sub-gaussian distribution, and the reconstruction comes as the solution to a convex program.
A History of Cluster Analysis Using the Classification Society's Bibliography Over Four Decades
Venue: arXiv cs.DL 2013
Year: 2013

The Classification Literature Automated Search Service, an annual bibliography based on citation of one or more of a set of around 80 book or journal publications, ran from 1972 to 2012. We analyze here the years 1994 to 2011. The Classification Society's Service, as it was termed, has been produced by the Classification Society. In earlier decades it was distributed as a diskette or CD with the Journal of Classification. Among our findings are the following: an enormous increase in scholarly production post approximately 2000; a very major increase in quantity, coupled with work in different disciplines, from approximately 2004; and a major shift also from cluster analysis in earlier times having mathematics and psychology as disciplines of the journals published in, and affiliations of authors, contrasted with, in more recent times, a "centre of gravity" in management and engineering.
Provenance for SPARQL queries
Venue: arXiv cs.DB 2013
Year: 2013

Determining trust of data available in the Semantic Web is fundamental for applications and users, in particular for linked open data obtained from SPARQL endpoints. There exist several proposals in the literature to annotate SPARQL query results with values from abstract models, adapting the seminal works on provenance for annotated relational databases. We provide an approach capable of providing provenance information for a large and significant fragment of SPARQL 1.1, including for the first time the major non-monotonic constructs under multiset semantics. The approach is based on the translation of SPARQL into relational queries over annotated relations with values of the most general m-semiring, and in this way also refuting a claim in the literature that the OPTIONAL construct of SPARQL cannot be captured appropriately with the known abstract models.