OpenRaiser/Intern-Atlas huggingface dataset:
Interdiction Problems on Planar Graphs
Venue: arXiv cs.DS 2013
Year: 2013

Interdiction problems are leader-follower games in which the leader is allowed to delete a certain number of edges from the graph in order to maximally impede the follower, who is trying to solve an optimization problem on the impeded graph. We introduce approximation algorithms and strong NP-completeness results for interdiction problems on planar graphs. We give a multiplicative $(1 + ε)$-approximation for the maximum matching interdiction problem on weighted planar graphs. The algorithm runs in pseudo-polynomial time for each fixed $ε> 0$. We also show that weighted maximum matching interdiction, budget-constrained flow improvement, directed shortest path interdiction, and minimum perfect matching interdiction are strongly NP-complete on planar graphs. To our knowledge, our budget-constrained flow improvement result is the first planar NP-completeness proof that uses a one-vertex crossing gadget.
A Collapse Theorem for Holographic Algorithms with Matchgates on Domain Size at Most 4
Venue: arXiv cs.CC 2013
Year: 2013

Holographic algorithms with matchgates are a novel approach to design polynomial time computation. It uses Kasteleyn's algorithm for perfect matchings, and more importantly a holographic reduction . The two fundamental parameters of a holographic reduction are the domain size $k$ of the underlying problem, and the basis size $\ell$. A holographic reduction transforms the computation to matchgates by a linear transformation that maps to (a tensor product space of) a linear space of dimension $2^{\ell}$. We prove a sharp basis collapse theorem, that shows that for domain size 3 and 4, all non-trivial holographic reductions have basis size $\ell$ collapse to 1 and 2 respectively. The main proof techniques are Matchgates Identities, and a Group Property of matchgates signatures.
Centralized and Cooperative Transmission of Secure Multiple Unicasts using Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

We introduce a method for securely delivering a set of messages to a group of clients over a broadcast erasure channel where each client is interested in a distinct message. Each client is able to obtain its own message but not the others'. In the proposed method the messages are combined together using a special variant of random linear network coding. Each client is provided with a private set of decoding coefficients to decode its own message. Our method provides security for the transmission sessions against computational brute-force attacks and also weakly security in information theoretic sense. As the broadcast channel is assumed to be erroneous, the missing coded packets should be recovered in some way. We consider two different scenarios. In the first scenario the missing packets are retransmitted by the base station (centralized). In the second scenario the clients cooperate with each other by exchanging packets (decentralized). In both scenarios, network coding techniques are exploited to increase the total throughput. For the case of centralized retransmissions we provide an analytical approximation for the throughput performance of instantly decodable network coded (IDNC) retransmissions as well as numerical experiments. For the decentralized scenario, we propose a new IDNC based retransmission method where its performance is evaluated via simulations and analytical approximation. Application of this method is not limited to our special problem and can be generalized to a new class of problems introduced in this paper as the cooperative index coding problem.
Gateway Switching in Q/V Band Satellite Feeder Links
Venue: arXiv cs.IT 2013
Year: 2013

A main challenge towards realizing the next generation Terabit/s broadband satellite communications (SatCom) is the limited spectrum available in the Ka band. An attractive solution is to move the feeder link to the higher Q/V band, where more spectrum is available. When utilizing the Q/V band, due to heavy rain attenuation, gateway diversity is considered a necessity to ensure the required feeder link availability. Although receive site diversity has been studied in the past for SatCom, there is much less maturity in terms of transmit diversity techniques. In this paper, a modified switch and stay combining scheme is proposed for a Q/V band feeder link, but its performance is also evaluated over an end-to-end satellite link. The proposed scheme is pragmatic and has close to optimal performance with notably lower complexity.
Standard Fingerprint Databases: Manual Minutiae Labeling and Matcher Performance Analyses
Venue: arXiv cs.CV 2013
Year: 2013

Fingerprint verification and identification algorithms based on minutiae features are used in many biometric systems today (e.g., governmental e-ID programs, border control, AFIS, personal authentication for portable devices). Researchers in industry/academia are now able to utilize many publicly available fingerprint databases (e.g., Fingerprint Verification Competition (FVC) & NIST databases) to compare/evaluate their feature extraction and/or matching algorithm performances against those of others. The results from these evaluations are typically utilized by decision makers responsible for implementing the cited biometric systems, in selecting/tuning specific sensors, feature extractors and matchers. In this study, for a subset of the cited public fingerprint databases, we report fingerprint minutiae matching results, which are based on (i) minutiae extracted automatically from fingerprint images, and (ii) minutiae extracted manually by human subjects. By doing so, we are able to (i) quantitatively judge the performance differences between these two cases, (ii) elaborate on performance upper bounds of minutiae matching, utilizing what can be termed as "ground truth" minutiae features, (iii) analyze minutiae matching performance, without coupling it with the minutiae extraction performance beforehand. Further, as we will freely distribute the minutiae templates, originating from this manual labeling study, in a standard minutiae template exchange format (ISO 19794-2), we believe that other researchers in the biometrics community will be able to utilize the associated results & templates to create their own evaluations pertaining to their fingerprint minutiae extractors/matchers.
EURETILE 2010-2012 summary: first three years of activity of the European Reference Tiled Experiment
Venue: arXiv cs.DC 2013
Year: 2013

This is the summary of first three years of activity of the EURETILE FP7 project 247846. EURETILE investigates and implements brain-inspired and fault-tolerant foundational innovations to the system architecture of massively parallel tiled computer architectures and the corresponding programming paradigm. The execution targets are a many-tile HW platform, and a many-tile simulator. A set of SW process - HW tile mapping candidates is generated by the holistic SW tool-chain using a combination of analytic and bio-inspired methods. The Hardware dependent Software is then generated, providing OS services with maximum efficiency/minimal overhead. The many-tile simulator collects profiling data, closing the loop of the SW tool chain. Fine-grain parallelism inside processes is exploited by optimized intra-tile compilation techniques, but the project focus is above the level of the elementary tile. The elementary HW tile is a multi-processor, which includes a fault tolerant Distributed Network Processor (for inter-tile communication) and ASIP accelerators. Furthermore, EURETILE investigates and implements the innovations for equipping the elementary HW tile with high-bandwidth, low-latency brain-like inter-tile communication emulating 3 levels of connection hierarchy, namely neural columns, cortical areas and cortex, and develops a dedicated cortical simulation benchmark: DPSNN-STDP (Distributed Polychronous Spiking Neural Net with synaptic Spiking Time Dependent Plasticity). EURETILE leverages on the multi-tile HW paradigm and SW tool-chain developed by the FET-ACA SHAPES Integrated Project (2006-2009).
Degrees of Freedom of Certain Interference Alignment Schemes with Distributed CSIT
Venue: arXiv cs.IT 2013
Year: 2013

In this work, we consider the use of interference alignment (IA) in a MIMO interference channel (IC) under the assumption that each transmitter (TX) has access to channel state information (CSI) that generally differs from that available to other TXs. This setting is referred to as distributed CSIT. In a setting where CSI accuracy is controlled by a set of power exponents, we show that in the static 3-user MIMO square IC, the number of degrees-of-freedom (DoF) that can be achieved with distributed CSIT is at least equal to the DoF achieved with the worst accuracy taken across the TXs and across the interfering links. We conjecture further that this represents exactly the DoF achieved. This result is in strong contrast with the centralized CSIT configuration usually studied (where all the TXs share the same, possibly imperfect, channel estimate) for which it was shown that the DoF achieved at receiver (RX) i is solely limited by the quality of its own feedback. This shows the critical impact of CSI discrepancies between the TXs, and highlights the price paid by distributed precoding.
Willingness Optimization for Social Group Activity
Venue: arXiv cs.SI 2013
Year: 2013

Studies show that a person is willing to join a social group activity if the activity is interesting, and if some close friends also join the activity as companions. The literature has demonstrated that the interests of a person and the social tightness among friends can be effectively derived and mined from social networking websites. However, even with the above two kinds of information widely available, social group activities still need to be coordinated manually, and the process is tedious and time-consuming for users, especially for a large social group activity, due to complications of social connectivity and the diversity of possible interests among friends. To address the above important need, this paper proposes to automatically select and recommend potential attendees of a social group activity, which could be very useful for social networking websites as a value-added service. We first formulate a new problem, named Willingness mAximization for Social grOup (WASO). This paper points out that the solution obtained by a greedy algorithm is likely to be trapped in a local optimal solution. Thus, we design a new randomized algorithm to effectively and efficiently solve the problem. Given the available computational budgets, the proposed algorithm is able to optimally allocate the resources and find a solution with an approximation ratio. We implement the proposed algorithm in Facebook, and the user study demonstrates that social groups obtained by the proposed algorithm significantly outperform the solutions manually configured by users.
Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
Venue: arXiv cs.DM 2013
Year: 2013

A nonconstructive proof can be used to prove the existence of an object with some properties without providing an explicit example of such an object. A special case is a probabilistic proof where we show that an object with required properties appears with some positive probability in some random process. Can we use such arguments to prove the existence of a computable infinite object? Sometimes yes: following [8], we show how the notion of a layerwise computable mapping can be used to prove a computable version of Lovász local lemma. (A survey of Moser-Tardos proof is included to make the paper self-contained.)
High Level Pattern Classification via Tourist Walks in Networks
Venue: arXiv cs.AI 2013
Year: 2013

Complex networks refer to large-scale graphs with nontrivial connection patterns. The salient and interesting features that the complex network study offer in comparison to graph theory are the emphasis on the dynamical properties of the networks and the ability of inherently uncovering pattern formation of the vertices. In this paper, we present a hybrid data classification technique combining a low level and a high level classifier. The low level term can be equipped with any traditional classification techniques, which realize the classification task considering only physical features (e.g., geometrical or statistical features) of the input data. On the other hand, the high level term has the ability of detecting data patterns with semantic meanings. In this way, the classification is realized by means of the extraction of the underlying network's features constructed from the input data. As a result, the high level classification process measures the compliance of the test instances with the pattern formation of the training data. Out of various high level perspectives that can be utilized to capture semantic meaning, we utilize the dynamical features that are generated from a tourist walker in a networked environment. Specifically, a weighted combination of transient and cycle lengths generated by the tourist walk is employed for that end. Interestingly, our study shows that the proposed technique is able to further improve the already optimized performance of traditional classification techniques.
Suffix Tree of Alignment: An Efficient Index for Similar Data
Venue: arXiv cs.DS 2013
Year: 2013

We consider an index data structure for similar strings. The generalized suffix tree can be a solution for this. The generalized suffix tree of two strings $A$ and $B$ is a compacted trie representing all suffixes in $A$ and $B$. It has $|A|+|B|$ leaves and can be constructed in $O(|A|+|B|)$ time. However, if the two strings are similar, the generalized suffix tree is not efficient because it does not exploit the similarity which is usually represented as an alignment of $A$ and $B$. In this paper we propose a space/time-efficient suffix tree of alignment which wisely exploits the similarity in an alignment. Our suffix tree for an alignment of $A$ and $B$ has $|A| + l_d + l_1$ leaves where $l_d$ is the sum of the lengths of all parts of $B$ different from $A$ and $l_1$ is the sum of the lengths of some common parts of $A$ and $B$. We did not compromise the pattern search to reduce the space. Our suffix tree can be searched for a pattern $P$ in $O(|P|+occ)$ time where $occ$ is the number of occurrences of $P$ in $A$ and $B$. We also present an efficient algorithm to construct the suffix tree of alignment. When the suffix tree is constructed from scratch, the algorithm requires $O(|A| + l_d + l_1 + l_2)$ time where $l_2$ is the sum of the lengths of other common substrings of $A$ and $B$. When the suffix tree of $A$ is already given, it requires $O(l_d + l_1 + l_2)$ time.
The solution to the challenge in "Time-Reversible Random Number Generators" by Wm. G. Hoover and Carol G. Hoover
Venue: arXiv cs.DM 2013
Year: 2013

I provide the algorithm that solves the challenge proposed by Wm. G. Hoover and Carol G. Hoover in their recent paper "Time-Reversible Random Number Generators", arXiv:1305.0961, with an explanation on how to derive it analytically.
Mathematical Modeling of Product Rating: Sufficiency, Misbehavior and Aggregation Rules
Venue: arXiv cs.IR 2013
Year: 2013

Many web services like eBay, Tripadvisor, Epinions, etc, provide historical product ratings so that users can evaluate the quality of products. Product ratings are important since they affect how well a product will be adopted by the market. The challenge is that we only have {\em "partial information"} on these ratings: Each user provides ratings to only a "{\em small subset of products}". Under this partial information setting, we explore a number of fundamental questions: What is the "{\em minimum number of ratings}" a product needs so one can make a reliable evaluation of its quality? How users' {\em misbehavior} (such as {\em cheating}) in product rating may affect the evaluation result? To answer these questions, we present a formal mathematical model of product evaluation based on partial information. We derive theoretical bounds on the minimum number of ratings needed to produce a reliable indicator of a product's quality. We also extend our model to accommodate users' misbehavior in product rating. We carry out experiments using both synthetic and real-world data (from TripAdvisor, Amazon and eBay) to validate our model, and also show that using the "majority rating rule" to aggregate product ratings, it produces more reliable and robust product evaluation results than the "average rating rule".
An Improved Three-Weight Message-Passing Algorithm
Venue: arXiv cs.AI 2013
Year: 2013

We describe how the powerful "Divide and Concur" algorithm for constraint satisfaction can be derived as a special case of a message-passing version of the Alternating Direction Method of Multipliers (ADMM) algorithm for convex optimization, and introduce an improved message-passing algorithm based on ADMM/DC by introducing three distinct weights for messages, with "certain" and "no opinion" weights, as well as the standard weight used in ADMM/DC. The "certain" messages allow our improved algorithm to implement constraint propagation as a special case, while the "no opinion" messages speed convergence for some problems by making the algorithm focus only on active constraints. We describe how our three-weight version of ADMM/DC can give greatly improved performance for non-convex problems such as circle packing and solving large Sudoku puzzles, while retaining the exact performance of ADMM for convex problems. We also describe the advantages of our algorithm compared to other message-passing algorithms based upon belief propagation.
Almost-commuting matrices are almost jointly diagonalizable
Venue: arXiv cs.NA 2013
Year: 2013

We study the relation between approximate joint diagonalization of self-adjoint matrices and the norm of their commutator, and show that almost commuting self-adjoint matrices are almost jointly diagonalizable by a unitary matrix.
MAP-REDUCE Runtime Enforcement of Information Flow Policies
Venue: arXiv cs.CR 2013
Year: 2013

We propose a flexible framework that can be easily customized to enforce a large variety of information flow properties. Our framework combines the ideas of secure multi-execution and map-reduce computations. The information flow property of choice can be obtained by simply changes to a map (or reduce) program that control parallel executions. We present the architecture of the enforcement mechanism and its customizations for non-interference (NI) (from Devriese and Piessens) and some properties proposed by Mantel, such as removal of inputs (RI) and deletion of inputs (DI), and demonstrate formally soundness and precision of enforcement for these properties.
Optimality of Orthogonal Access for One-dimensional Convex Cellular Networks
Venue: arXiv cs.IT 2013
Year: 2013

It is shown that a greedy orthogonal access scheme achieves the sum degrees of freedom of all one-dimensional (all nodes placed along a straight line) convex cellular networks (where cells are convex regions) when no channel knowledge is available at the transmitters except the knowledge of the network topology. In general, optimality of orthogonal access holds neither for two-dimensional convex cellular networks nor for one-dimensional non-convex cellular networks, thus revealing a fundamental limitation that exists only when both one-dimensional and convex properties are simultaneously enforced, as is common in canonical information theoretic models for studying cellular networks. The result also establishes the capacity of the corresponding class of index coding problems.
Repairing and Inpainting Damaged Images using Diffusion Tensor
Venue: arXiv cs.CV 2013
Year: 2013

Removing or repairing the imperfections of a digital images or videos is a very active and attractive field of research belonging to the image inpainting technique. This later has a wide range of applications, such as removing scratches in old photographic image, removing text and logos or creating cartoon and artistic effects. In this paper, we propose an efficient method to repair a damaged image based on a non linear diffusion tensor. The idea is to track perfectly the local geometry of the damaged image and allowing diffusion only in the isophotes curves direction. To illustrate the effective performance of our method, we present some experimental results on test and real photographic color images
Asymptotic Coverage Probability and Rate in Massive MIMO Networks
Venue: arXiv cs.IT 2013
Year: 2013

Massive multiple-input multiple-output (MIMO) is a transmission technique for cellular systems that uses many antennas to support not-as-many users. Thus far, the performance of massive MIMO has only been examined in finite cellular networks. In this letter, we analyze its performance in random cellular networks with Poisson distributed base station locations. Specifically, we provide analytical expressions for the asymptotic coverage probability and rate in both downlink and uplink when each base station has a large number of antennas. The results show that, though limited by pilot contamination, massive MIMO can provide significantly higher asymptotic data rate per user than the single-antenna network.
Loss Rate Based Fountain Codes for Data Transfer
Venue: arXiv cs.NI 2013
Year: 2013

Fountain codes are becoming increasingly important for data transferring over dedicated high-speed long-distance network. However, the encoding and decoding complexity of traditional fountain codes such as LT and Raptor codes are still high. In this paper, a new fountain codes named LRF (Loss Rate Based Fountain) codes for data transfer is proposed. In order to improve the performance of encoding and decoding efficiency and decrease the number of redundant encoding symbols, an innovative degree distribution instead of robust soliton degree distribution in LT (Luby Transfer) codes is proposed. In LRF codes, the degree of encoding symbol is decided by loss rate property, and the window size is extended dynamic. Simulations result using LRF codes show that the proposed method has better performance in term of encoding ratio, degree ratio, encoding and decoding efficiency with respect to LT and Raptor codes.
Shape Reconstruction and Recognition with Isolated Non-directional Cues
Venue: arXiv cs.CV 2013
Year: 2013

The paper investigates a hypothesis that our visual system groups visual cues based on how they form a surface, or more specifically triangulation derived from the visual cues. To test our hypothesis, we compare shape recognition with three different representations of visual cues: a set of isolated dots delineating the outline of the shape, a set of triangles obtained from Delaunay triangulation of the set of dots, and a subset of Delaunay triangles excluding those outside of the shape. Each participant was assigned to one particular representation type and increased the number of dots (and consequentially triangles) until the underlying shape could be identified. We compare the average number of dots needed for identification among three types of representations. Our hypothesis predicts that the results from the three representations will be similar. However, they show statistically significant differences. The paper also presents triangulation based algorithms for reconstruction and recognition of a shape from a set of isolated dots. Experiments showed that the algorithms were more effective and perceptually agreeable than similar contour based ones. From these experiments, we conclude that triangulation does affect our shape recognition. However, the surface based approach presents a number of computational advantages over the contour based one and should be studied further.