OpenRaiser/Intern-Atlas huggingface dataset:
Contribution Games in Social Networks
Venue: arXiv cs.GT 2011
Year: 2011

We consider network contribution games, where each agent in a social network has a budget of effort that he can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure the success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize the existence, computational complexity, and quality of equilibrium based on the types of reward functions involved. For example, when all reward functions are concave, we prove that the price of anarchy is at most 2. For convex functions the same only holds under some special but very natural conditions. A special focus of the paper are minimum effort games, where the reward of a relationship depends only on the minimum effort of any of the participants. Finally, we show tight bounds for approximate equilibria and convergence of dynamics in these games.
Group Leaders Optimization Algorithm
Venue: arXiv cs.NE 2011
Year: 2011

We present a new global optimization algorithm in which the influence of the leaders in social groups is used as an inspiration for the evolutionary technique which is designed into a group architecture. To demonstrate the efficiency of the method, a standard suite of single and multidimensional optimization functions along with the energies and the geometric structures of Lennard-Jones clusters are given as well as the application of the algorithm on quantum circuit design problems. We show that as an improvement over previous methods, the algorithm scales as N^2.5 for the Lennard-Jones clusters of N-particles. In addition, an efficient circuit design is shown for two qubit Grover search algorithm which is a quantum algorithm providing quadratic speed-up over the classical counterpart.
Assume-Guarantee Synthesis for Digital Contract Signing
Venue: arXiv cs.LO 2011
Year: 2011

We study the automatic synthesis of fair non-repudiation protocols, a class of fair exchange protocols, used for digital contract signing. First, we show how to specify the objectives of the participating agents and the trusted third party (TTP) as path formulas in LTL and prove that the satisfaction of these objectives imply fairness; a property required of fair exchange protocols. We then show that weak (co-operative) co-synthesis and classical (strictly competitive) co-synthesis fail, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success of assume-guarantee synthesis as follows: (a) any solution of assume-guarantee synthesis is attack-free; no subset of participants can violate the objectives of the other participants; (b) the Asokan-Shoup-Waidner (ASW) certified mail protocol that has known vulnerabilities is not a solution of AGS; (c) the Kremer-Markowitch (KM) non-repudiation protocol is a solution of AGS; and (d) AGS presents a new and symmetric fair non-repudiation protocol that is attack-free. To our knowledge this is the first application of synthesis to fair non-repudiation protocols, and our results show how synthesis can both automatically discover vulnerabilities in protocols and generate correct protocols. The solution to assume-guarantee synthesis can be computed efficiently as the secure equilibrium solution of three-player graph games.
Approximately Optimal Mechanism Design via Differential Privacy
Venue: arXiv cs.GT 2011
Year: 2011

In this paper we study the implementation challenge in an abstract interdependent values model and an arbitrary objective function. We design a mechanism that allows for approximate optimal implementation of insensitive objective functions in ex-post Nash equilibrium. If, furthermore, values are private then the same mechanism is strategy proof. We cast our results onto two specific models: pricing and facility location. The mechanism we design is optimal up to an additive factor of the order of magnitude of one over the square root of the number of agents and involves no utility transfers. Underlying our mechanism is a lottery between two auxiliary mechanisms: with high probability we actuate a mechanism that reduces players' influence on the choice of the social alternative, while choosing the optimal outcome with high probability. This is where the recent notion of differential privacy is employed. With the complementary probability we actuate a mechanism that is typically far from optimal but is incentive compatible. The joint mechanism inherits the desired properties from both.
On two variations of identifying codes
Venue: arXiv cs.DM 2011
Year: 2011

Identifying codes have been introduced in 1998 to model fault-detection in multiprocessor systems. In this paper, we introduce two variations of identifying codes: weak codes and light codes. They correspond to fault-detection by successive rounds. We give exact bounds for those two definitions for the family of cycles.
Query strategy for sequential ontology debugging
Venue: arXiv cs.LO 2011
Year: 2011

Debugging of ontologies is an important prerequisite for their wide-spread application, especially in areas that rely upon everyday users to create and maintain knowledge bases, as in the case of the Semantic Web. Recent approaches use diagnosis methods to identify causes of inconsistent or incoherent ontologies. However, in most debugging scenarios these methods return many alternative diagnoses, thus placing the burden of fault localization on the user. This paper demonstrates how the target diagnosis can be identified by performing a sequence of observations, that is, by querying an oracle about entailments of the target ontology. We exploit a-priori probabilities of typical user errors to formulate information-theoretic concepts for query selection. Our evaluation showed that the proposed method significantly reduces the number of required queries compared to myopic strategies. We experimented with different probability distributions of user errors and different qualities of the a-priori probabilities. Our measurements showed the advantageousness of information-theoretic approach to query selection even in cases where only a rough estimate of the priors is available.
Multiplicatively Repeated Non-Binary LDPC Codes
Venue: arXiv cs.IT 2011
Year: 2011

We propose non-binary LDPC codes concatenated with multiplicative repetition codes. By multiplicatively repeating the (2,3)-regular non-binary LDPC mother code of rate 1/3, we construct rate-compatible codes of lower rates 1/6, 1/9, 1/12,... Surprisingly, such simple low-rate non-binary LDPC codes outperform the best low-rate binary LDPC codes so far. Moreover, we propose the decoding algorithm for the proposed codes, which can be decoded with almost the same computational complexity as that of the mother code.
Formal Proof of a Wave Equation Resolution Scheme: the Method Error
Venue: arXiv cs.LO 2011
Year: 2011

Popular finite difference numerical schemes for the resolution of the one-dimensional acoustic wave equation are well-known to be convergent. We present a comprehensive formalization of the simplest one and formally prove its convergence in Coq. The main difficulties lie in the proper definition of asymptotic behaviors and the implicit way they are handled in the mathematical pen-and-paper proofs. To our knowledge, this is the first time such kind of mathematical proof is machine-checked.
Evaluating Accessible Synchronous CMC Applications
Venue: arXiv cs.HC 2011
Year: 2011

This paper proposes a more comprehensive evaluation methodology to measure the usability and user experience qualities of accessible synchronous computer-mediated communication applications. The methodology goes beyond current practices by evaluating how the interaction between a user and a product influences the user experience of those at the other endpoint of the communication channel. A major contribution is given with the proposal of a user test where one of the participants tries to guess whether the other participant has a disability or not. The proposed test is inspired in the Turing Test, and is a consequence of user requirements elicited from a group of individuals with motor and speech disabilities. These ideas are tested and validated with two examples of synchronous communication applications.
Sidelobe Suppression for Robust Beamformer via The Mixed Norm Constraint
Venue: arXiv cs.IT 2011
Year: 2011

Applying a sparse constraint on the beam pattern has been suggested to suppress the sidelobe of the minimum variance distortionless response (MVDR) beamformer recently. To further improve the performance, we add a mixed norm constraint on the beam pattern. It matches the beam pattern better and encourages dense distribution in mainlobe and sparse distribution in sidelobe. The obtained beamformer has a lower sidelobe level and deeper nulls for interference avoidance than the standard sparse constraint based beamformer. Simulation demonstrates that the SINR gain is considerable for its lower sidelobe level and deeper nulling for interference, while the robustness against the mismatch between the steering angle and the direction of arrival (DOA) of the desired signal, caused by imperfect estimation of DOA, is maintained too.
Sparse Support Recovery with Phase-Only Measurements
Venue: arXiv cs.IT 2011
Year: 2011

Sparse support recovery (SSR) is an important part of the compressive sensing (CS). Most of the current SSR methods are with the full information measurements. But in practice the amplitude part of the measurements may be seriously destroyed. The corrupted measurements mismatch the current SSR algorithms, which leads to serious performance degeneration. This paper considers the problem of SSR with only phase information. In the proposed method, the minimization of the l1 norm of the estimated sparse signal enforces sparse distribution, while a nonzero constraint of the uncorrupted random measurements' amplitudes with respect to the reconstructed sparse signal is introduced. Because it only requires the phase components of the measurements in the constraint, it can avoid the performance deterioration by corrupted amplitude components. Simulations demonstrate that the proposed phase-only SSR is superior in the support reconstruction accuracy when the amplitude components of the measurements are contaminated.
Anti-Sampling-Distortion Compressive Wideband Spectrum Sensing for Cognitive Radio
Venue: arXiv cs.IT 2011
Year: 2011

Too high sampling rate is the bottleneck to wideband spectrum sensing for cognitive radio in mobile communication. Compressed sensing (CS) is introduced to transfer the sampling burden. The standard sparse signal recovery of CS does not consider the distortion in the analogue-to-information converter (AIC). To mitigate performance degeneration casued by the mismatch in least square distortionless constraint which doesn't consider the AIC distortion, we define the sparse signal with the sampling distortion as a bounded additive noise, and An anti-sampling-distortion constraint (ASDC) is deduced. Then we combine the \ell1 norm based sparse constraint with the ASDC to get a novel robust sparse signal recovery operator with sampling distortion. Numerical simulations demonstrate that the proposed method outperforms standard sparse wideband spectrum sensing in accuracy, denoising ability, etc.
Cooperative Diversity with Mobile Nodes: Capacity Outage Rate and Duration
Venue: arXiv cs.IT 2011
Year: 2011

The outage probability is an important performance measure for cooperative diversity schemes. However, in mobile environments, the outage probability does not completely describe the behavior of cooperative diversity schemes since the mobility of the involved nodes introduces variations in the channel gains. As a result, the capacity outage events are correlated in time and second-order statistical parameters of the achievable information-theoretic capacity such as the average capacity outage rate (AOR) and the average capacity outage duration (AOD) are required to obtain a more complete description of the properties of cooperative diversity protocols. In this paper, assuming slow Rayleigh fading, we derive exact expressions for the AOR and the AOD of three well-known cooperative diversity protocols: variable-gain amplify-and-forward, decode-and-forward, and selection decode-and-forward relaying. Furthermore, we develop asymptotically tight high signal-to-noise ratio (SNR) approximations, which offer important insights into the influence of various system and channel parameters on the AOR and AOD. In particular, we show that on a double-logarithmic scale, similar to the outage probability, the AOR asymptotically decays with the SNR with a slope that depends on the diversity gain of the cooperative protocol, whereas the AOD asymptotically decays with a slope of -1/2 independent of the diversity gain.
Minimum Variance Multi-Frequency Distortionless Restriction for Digital Wideband Beamformer
Venue: arXiv cs.IT 2011
Year: 2011

This paper proposes a digital amplitude-phase weighting array based a minimum variance multi-frequency distortionless restriction (MVMFDR) to aviod the frequency band signal distortion in digital beamformer and too short time delay line (TDL) requirement in analoge wideband TDL array.
Capacity and Modulations with Peak Power Constraint
Venue: arXiv cs.IT 2011
Year: 2011

A practical communication channel often suffers from constraints on input other than the average power, such as the peak power constraint. In order to compare achievable rates with different constellations as well as the channel capacity under such constraints, it is crucial to take these constraints into consideration properly. In this paper, we propose a direct approach to compare the achievable rates of practical input constellations and the capacity under such constraints. As an example, we study the discrete-time complex-valued additive white Gaussian noise (AWGN) channel and compare the capacity under the peak power constraint with the achievable rates of phase shift keying (PSK) and quadrature amplitude modulation (QAM) input constellations.
Provenance Views for Module Privacy
Venue: arXiv cs.DB 2011
Year: 2011

Scientific workflow systems increasingly store provenance information about the module executions used to produce a data item, as well as the parameter settings and intermediate data items passed between module executions. However, authors/owners of workflows may wish to keep some of this information confidential. In particular, a module may be proprietary, and users should not be able to infer its behavior by seeing mappings between all data inputs and outputs. The problem we address in this paper is the following: Given a workflow, abstractly modeled by a relation R, a privacy requirement Γand costs associated with data. The owner of the workflow decides which data (attributes) to hide, and provides the user with a view R' which is the projection of R over attributes which have not been hidden. The goal is to minimize the cost of hidden data while guaranteeing that individual modules are Γ-private. We call this the "secureview" problem. We formally define the problem, study its complexity, and offer algorithmic solutions.
Anti-measurement Matrix Uncertainty Sparse Signal Recovery for Compressive Sensing
Venue: arXiv cs.IT 2011
Year: 2011

Compressive sensing (CS) is a technique for estimating a sparse signal from the random measurements and the measurement matrix. Traditional sparse signal recovery methods have seriously degeneration with the measurement matrix uncertainty (MMU). Here the MMU is modeled as a bounded additive error. An anti-uncertainty constraint in the form of a mixed L2 and L1 norm is deduced from the sparse signal model with MMU. Then we combine the sparse constraint with the anti-uncertainty constraint to get an anti-uncertainty sparse signal recovery operator. Numerical simulations demonstrate that the proposed operator has a better reconstructing performance with the MMU than traditional methods.
Symbolic dynamics
Venue: arXiv cs.FL 2011
Year: 2011

This chapter presents some of the links between automata theory and symbolic dynamics. The emphasis is on two particular points. The first one is the interplay between some particular classes of automata, such as local automata and results on embeddings of shifts of finite type. The second one is the connection between syntactic semigroups and the classification of sofic shifts up to conjugacy.
On Communication over Unknown Sparse Frequency-Selective Block-Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers the problem of reliable communication over discrete-time channels whose impulse responses have length $L$ and exactly $S\leq L$ non-zero coefficients, and whose support and coefficients remain fixed over blocks of $N>L$ channel uses but change independently from block to block. Here, it is assumed that the channel's support and coefficient realizations are both unknown, although their statistics are known. Assuming Gaussian non-zero-coefficients and noise, and focusing on the high-SNR regime, it is first shown that the ergodic noncoherent channel capacity has pre-log factor $1-\frac{S}{N}$ for any $L$. It is then shown that, to communicate with arbitrarily small error probability at rates in accordance with the capacity pre-log factor, it suffices to use pilot-aided orthogonal frequency-division multiplexing (OFDM) with $S$ pilots per fading block, in conjunction with an appropriate noncoherent decoder. Since the achievability result is proven using a noncoherent decoder whose complexity grows exponentially in the number of fading blocks $K$, a simpler decoder, based on $S+1$ pilots, is also proposed. Its $ε$-achievable rate is shown to have pre-log factor equal to $1-\frac{S+1}{N}$ with the previously considered channel, while its achievable rate is shown to have pre-log factor $1-\frac{S+1}{N}$ when the support of the block-fading channel remains fixed over time.
Opportunistic Interference Mitigation Achieves Optimal Degrees-of-Freedom in Wireless Multi-cell Uplink Networks
Venue: arXiv cs.IT 2011
Year: 2011

We introduce an opportunistic interference mitigation (OIM) protocol, where a user scheduling strategy is utilized in $K$-cell uplink networks with time-invariant channel coefficients and base stations (BSs) having $M$ antennas. Each BS opportunistically selects a set of users who generate the minimum interference to the other BSs. Two OIM protocols are shown according to the number $S$ of simultaneously transmitting users per cell: opportunistic interference nulling (OIN) and opportunistic interference alignment (OIA). Then, their performance is analyzed in terms of degrees-of-freedom (DoFs). As our main result, it is shown that $KM$ DoFs are achievable under the OIN protocol with $M$ selected users per cell, if the total number $N$ of users in a cell scales at least as $\text{SNR}^{(K-1)M}$. Similarly, it turns out that the OIA scheme with $S$($<M$) selected users achieves $KS$ DoFs, if $N$ scales faster than $\text{SNR}^{(K-1)S}$. These results indicate that there exists a trade-off between the achievable DoFs and the minimum required $N$. By deriving the corresponding upper bound on the DoFs, it is shown that the OIN scheme is DoF optimal. Finally, numerical evaluation, a two-step scheduling method, and the extension to multi-carrier scenarios are shown.
Bounded Search Tree Algorithms for Parameterized Cograph Deletion: Efficient Branching Rules by Exploiting Structures of Special Graph Classes
Venue: arXiv cs.DM 2011
Year: 2011

Many fixed-parameter tractable algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingly complex case analysis. We introduce a novel and general search strategy that branches on the forbidden subgraphs of a graph class relaxation. By using the class of $P_4$-sparse graphs as the relaxed graph class, we obtain efficient bounded search tree algorithms for several parameterized deletion problems. We give the first non-trivial bounded search tree algorithms for the cograph edge-deletion problem and the trivially perfect edge-deletion problems. For the cograph vertex deletion problem, a refined analysis of the runtime of our simple bounded search algorithm gives a faster exponential factor than those algorithms designed with the help of complicated case distinctions and non-trivial running time analysis [21] and computer-aided branching rules [11].
Tree-width of hypergraphs and surface duality
Venue: arXiv cs.DM 2011
Year: 2011

In Graph Minors III, Robertson and Seymour write: "It seems that the tree-width of a planar graph and the tree-width of its geometric dual are approximately equal - indeed, we have convinced ourselves that they differ by at most one". They never gave a proof of this. In this paper, we prove a generalisation of this statement to embedding of hypergraphs on general surfaces, and we prove that our bound is tight.
Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix
Venue: arXiv cs.CC 2011
Year: 2011

Given a matrix $A \in \mathbb{R}^{m \times n}$ ($n$ vectors in $m$ dimensions), and a positive integer $k < n$, we consider the problem of selecting $k$ column vectors from $A$ such that the volume of the parallelepiped they define is maximum over all possible choices. We prove that there exists $δ<1$ and $c>0$ such that this problem is not approximable within $2^{-ck}$ for $k = δn$, unless $P=NP$.
Quotient Complexity of Bifix-, Factor-, and Subword-Free Regular Languages
Venue: arXiv cs.FL 2011
Year: 2011

A language L is prefix-free if, whenever words u and v are in L and u is a prefix of v, then u=v. Suffix-, factor-, and subword-free languages are defined similarly, where "subword" means "subsequence". A language is bifix-free if it is both prefix- and suffix-free. We study the quotient complexity, more commonly known as state complexity, of operations in the classes of bifix-, factor-, and subword-free regular languages. We find tight upper bounds on the quotient complexity of intersection, union, difference, symmetric difference, concatenation, star, and reversal in these three classes of languages.
On Marton's Inner Bound for the General Broadcast Channel
Venue: arXiv cs.IT 2011
Year: 2011

We establish several new results on Marton's coding scheme and its corresponding inner bound on the capacity region of the general broadcast channel. We show that unlike the Gaussian case, Marton's coding scheme without superposition coding is not optimal in general even for a degraded broadcast channel with no common message. We then establish properties of Marton's inner bound that help restrict the search space for computing the sum-rate. Next, we show that the inner bound is optimal along certain directions. Finally, we propose a coding scheme that may lead to a larger inner bound.
From Pathwidth to Connected Pathwidth
Venue: arXiv cs.DM 2011
Year: 2011

It is proven that the connected pathwidth of any graph $G$ is at most $2\cdot\pw(G)+1$, where $\pw(G)$ is the pathwidth of $G$. The method is constructive, i.e. it yields an efficient algorithm that for a given path decomposition of width $k$ computes a connected path decomposition of width at most $2k+1$. The running time of the algorithm is $O(dk^2)$, where $d$ is the number of `bags' in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality $\csn(G)\leq 2\sn(G)+3$, where $\csn(G)$ and $\sn(G)$ are the connected search number and the search number of $G$. Moreover, the algorithm presented in this work can be used to convert a given search strategy using $k$ searchers into a (monotone) connected one using $2k+3$ searchers and starting at an arbitrary homebase.