OpenRaiser/Intern-Atlas huggingface dataset:
Cores of Cooperative Games in Information Theory
Venue: arXiv cs.IT 2008
Year: 2008

Cores of cooperative games are ubiquitous in information theory, and arise most frequently in the characterization of fundamental limits in various scenarios involving multiple users. Examples include classical settings in network information theory such as Slepian-Wolf source coding and multiple access channels, classical settings in statistics such as robust hypothesis testing, and new settings at the intersection of networking and statistics such as distributed estimation problems for sensor networks. Cooperative game theory allows one to understand aspects of all of these problems from a fresh and unifying perspective that treats users as players in a game, sometimes leading to new insights. At the heart of these analyses are fundamental dualities that have been long studied in the context of cooperative games; for information theoretic purposes, these are dualities between information inequalities on the one hand and properties of rate, capacity or other resource allocation regions on the other.
Minimizing the stabbing number of matchings, trees, and triangulations
Venue: arXiv cs.CG 2008
Year: 2008

The (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. This paper deals with finding perfect matchings, spanning trees, or triangulations of minimum stabbing number for a given set of points. The complexity of these problems has been a long-standing open question; in fact, it is one of the original 30 outstanding open problems in computational geometry on the list by Demaine, Mitchell, and O'Rourke. The answer we provide is negative for a number of minimum stabbing problems by showing them NP-hard by means of a general proof technique. It implies non-trivial lower bounds on the approximability. On the positive side we propose a cut-based integer programming formulation for minimizing the stabbing number of matchings and spanning trees. We obtain lower bounds (in polynomial time) from the corresponding linear programming relaxations, and show that an optimal fractional solution always contains an edge of at least constant weight. This result constitutes a crucial step towards a constant-factor approximation via an iterated rounding scheme. In computational experiments we demonstrate that our approach allows for actually solving problems with up to several hundred points optimally or near-optimally.
No-cloning principal can alone provide security
Venue: arXiv cs.IT 2008
Year: 2008

Existing quantum key distribution schemes need the support of classical authentication scheme to ensure security. This is a conceptual drawback of quantum cryptography. It is pointed out that quantum cryptosystem does not need any support of classical cryptosystem to ensure security. No-cloning principal can alone provide security in communication. Even no-cloning principle itself can help to authenticate each bit of information. It implies that quantum password need not to be a secret password.
Approximability of Integer Programming with Generalised Constraints
Venue: arXiv cs.CC 2008
Year: 2008

We study a family of problems, called \prob{Maximum Solution}, where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject to a set of constraints. When the domain is Boolean (i.e. restricted to $\{0,1\}$), the maximum solution problem is identical to the well-studied \prob{Max Ones} problem, and the approximability is completely understood for all restrictions on the underlying constraints [Khanna et al., SIAM J. Comput., 30 (2001), pp. 1863-1920]. We continue this line of research by considering domains containing more than two elements. We present two main results: a complete classification for the approximability of all maximal constraint languages over domains of cardinality at most 4, and a complete classification of the approximability of the problem when the set of allowed constraints contains all permutation constraints. Under the assumption that a conjecture due to Szczepara holds, we give a complete classification for all maximal constraint languages. These classes of languages are well-studied in universal algebra and computer science; they have, for instance, been considered in connection with machine learning and constraint satisfaction. Our results are proved by using algebraic results from clone theory and the results indicates that this approach is very powerful for classifying the approximability of certain optimisation problems.
The Gaussian Multiple Access Wire-Tap Channel
Venue: arXiv cs.IT 2008
Year: 2008

We consider the Gaussian Multiple Access Wire-Tap Channel (GMAC-WT). In this scenario, multiple users communicate with an intended receiver in the presence of an intelligent and informed wire-tapper who receives a degraded version of the signal at the receiver. We define suitable security measures for this multi-access environment. Using codebooks generated randomly according to a Gaussian distribution, achievable secrecy rate regions are identified using superposition coding and TDMA coding schemes. An upper bound for the secrecy sum-rate is derived, and our coding schemes are shown to achieve the sum capacity. Numerical results showing the new rate region are presented and compared with the capacity region of the Gaussian Multiple-Access Channel (GMAC) with no secrecy constraints, quantifying the price paid for secrecy.
Key Distillation and the Secret-Bit Fraction
Venue: arXiv cs.CR 2008
Year: 2008

We consider distillation of secret bits from partially secret noisy correlations P_ABE, shared between two honest parties and an eavesdropper. The most studied distillation scenario consists of joint operations on a large number of copies of the distribution (P_ABE)^N, assisted with public communication. Here we consider distillation with only one copy of the distribution, and instead of rates, the 'quality' of the distilled secret bits is optimized, where the 'quality' is quantified by the secret-bit fraction of the result. The secret-bit fraction of a binary distribution is the proportion which constitutes a secret bit between Alice and Bob. With local operations and public communication the maximal extractable secret-bit fraction from a distribution P_ABE is found, and is denoted by Lambda[P_ABE]. This quantity is shown to be nonincreasing under local operations and public communication, and nondecreasing under eavesdropper's local operations: it is a secrecy monotone. It is shown that if Lambda[P_ABE]>1/2 then P_ABE is distillable, thus providing a sufficient condition for distillability. A simple expression for Lambda[P_ABE] is found when the eavesdropper is decoupled, and when the honest parties' information is binary and the local operations are reversible. Intriguingly, for general distributions the (optimal) operation requires local degradation of the data.
Interactive Hatching and Stippling by Example
Venue: arXiv cs.GR 2008
Year: 2008

We describe a system that lets a designer interactively draw patterns of strokes in the picture plane, then guide the synthesis of similar patterns over new picture regions. Synthesis is based on an initial user-assisted analysis phase in which the system recognizes distinct types of strokes (hatching and stippling) and organizes them according to perceptual grouping criteria. The synthesized strokes are produced by combining properties (eg. length, orientation, parallelism, proximity) of the stroke groups extracted from the input examples. We illustrate our technique with a drawing application that allows the control of attributes and scale-dependent reproduction of the synthesized patterns.
How Hard Is Bribery in Elections?
Venue: arXiv cs.GT 2008
Year: 2008

We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by a certain amount of bribing voters a specified candidate can be made the election's winner? We study this problem for election systems as varied as scoring protocols and Dodgson voting, and in a variety of settings regarding homogeneous-vs.-nonhomogeneous electorate bribability, bounded-size-vs.-arbitrary-sized candidate sets, weighted-vs.-unweighted voters, and succinct-vs.-nonsuccinct input specification. We obtain both polynomial-time bribery algorithms and proofs of the intractability of bribery, and indeed our results show that the complexity of bribery is extremely sensitive to the setting. For example, we find settings in which bribery is NP-complete but manipulation (by voters) is in P, and we find settings in which bribing weighted voters is NP-complete but bribing voters with individual bribe thresholds is in P. For the broad class of elections (including plurality, Borda, k-approval, and veto) known as scoring protocols, we prove a dichotomy result for bribery of weighted voters: We find a simple-to-evaluate condition that classifies every case as either NP-complete or in P.
LTL with the Freeze Quantifier and Register Automata
Venue: arXiv cs.LO 2008
Year: 2008

A data word is a sequence of pairs of a letter from a finite alphabet and an element from an infinite set, where the latter can only be compared for equality. To reason about data words, linear temporal logic is extended by the freeze quantifier, which stores the element at the current word position into a register, for equality comparisons deeper in the formula. By translations from the logic to alternating automata with registers and then to faulty counter automata whose counters may erroneously increase at any time, and from faulty and error-free counter automata to the logic, we obtain a complete complexity table for logical fragments defined by varying the set of temporal operators and the number of registers. In particular, the logic with future-time operators and 1 register is decidable but not primitive recursive over finite data words. Adding past-time operators or 1 more register, or switching to infinite data words, cause undecidability.
A Simple Converse of Burnashev's Reliability
Venue: arXiv cs.IT 2008
Year: 2008

In a remarkable paper published in 1976, Burnashev determined the reliability function of variable-length block codes over discrete memoryless channels with feedback. Subsequently, an alternative achievability proof was obtained by Yamamoto and Itoh via a particularly simple and instructive scheme. Their idea is to alternate between a communication and a confirmation phase until the receiver detects the codeword used by the sender to acknowledge that the message is correct. We provide a converse that parallels the Yamamoto-Itoh achievability construction. Besides being simpler than the original, the proposed converse suggests that a communication and a confirmation phase are implicit in any scheme for which the probability of error decreases with the largest possible exponent. The proposed converse also makes it intuitively clear why the terms that appear in Burnashev's exponent are necessary.
Proportional Fairness in Multi-channel Multi-rate Wireless Networks-Part I: The Case of Deterministic Channels
Venue: arXiv cs.NI 2008
Year: 2008

This is Part I of a two-part paper series that studies the use of the proportional fairness (PF) utility function as the basis for capacity allocation and scheduling in multi-channel multi-rate wireless networks. The contributions of Part I are threefold. (i) First, we lay down the theoretical foundation for PF. Specifically, we present the fundamental properties and physical/economic interpretation of PF. We show by general mathematical arguments that PF leads to equal airtime allocation to users for the single-channel case; and equal equivalent airtime allocation to users for the multi-channel case, where the equivalent airtime enjoyed by a user is a weighted sum of the airtimes enjoyed by the user on all channels, with the weight of a channel being the price or value of that channel. We also establish the Pareto efficiency of PF solutions. (ii) Second, we derive characteristics of PF solutions that are useful for the construction of PF-optimization algorithms. We present several PF-optimization algorithms, including a fast algorithm that is amenable to parallel implementation. (iii) Third, we study the use of PF utility for capacity allocation in large-scale WiFi networks consisting of many adjacent wireless LANs. We find that the PF solution simultaneously achieves higher system throughput, better fairness, and lower outage probability with respect to the default solution given by today's 802.11 commercial products. Part II of this paper series extends our investigation to the time-varying-channel case in which the data rates enjoyed by users over the channels vary dynamically over time
Approximation of the Two-Part MDL Code
Venue: arXiv cs.LG 2008
Year: 2008

Approximation of the optimal two-part MDL code for given data, through successive monotonically length-decreasing two-part MDL codes, has the following properties: (i) computation of each step may take arbitrarily long; (ii) we may not know when we reach the optimum, or whether we will reach the optimum at all; (iii) the sequence of models generated may not monotonically improve the goodness of fit; but (iv) the model associated with the optimum has (almost) the best goodness of fit. To express the practically interesting goodness of fit of individual models for individual data sets we have to rely on Kolmogorov complexity.
Distributed Detection in Sensor Networks with Limited Range Sensors
Venue: arXiv cs.IT 2008
Year: 2008

We consider a multi-object detection problem over a sensor network (SNET) with limited range sensors. This problem complements the widely considered decentralized detection problem where all sensors observe the same object. While the necessity for global collaboration is clear in the decentralized detection problem, the benefits of collaboration with limited range sensors is unclear and has not been widely explored. In this paper we develop a distributed detection approach based on recent development of the false discovery rate (FDR). We first extend the FDR procedure and develop a transformation that exploits complete or partial knowledge of either the observed distributions at each sensor or the ensemble (mixture) distribution across all sensors. We then show that this transformation applies to multi-dimensional observations, thus extending FDR to multi-dimensional settings. We also extend FDR theory to cases where distributions under both null and positive hypotheses are uncertain. We then propose a robust distributed algorithm to perform detection. We further demonstrate scalability to large SNETs by showing that the upper bound on the communication complexity scales linearly with the number of sensors that are in the vicinity of objects and is independent of the total number of sensors. Finally, we deal with situations where the sensing model may be uncertain and establish robustness of our techniques to such uncertainties.
The Bedwyr system for model checking over syntactic expressions
Venue: arXiv cs.LO 2008
Year: 2008

Bedwyr is a generalization of logic programming that allows model checking directly on syntactic expressions possibly containing bindings. This system, written in OCaml, is a direct implementation of two recent advances in the theory of proof search. The first is centered on the fact that both finite success and finite failure can be captured in the sequent calculus by incorporating inference rules for definitions that allow fixed points to be explored. As a result, proof search in such a sequent calculus can capture simple model checking problems as well as may and must behavior in operational semantics. The second is that higher-order abstract syntax is directly supported using term-level $λ$-binders and the $\nabla$ quantifier. These features allow reasoning directly on expressions containing bound variables.
Succinct Sampling on Streams
Venue: arXiv cs.DS 2008
Year: 2008

A streaming model is one where data items arrive over long period of time, either one item at a time or in bursts. Typical tasks include computing various statistics over a sliding window of some fixed time-horizon. What makes the streaming model interesting is that as the time progresses, old items expire and new ones arrive. One of the simplest and central tasks in this model is sampling. That is, the task of maintaining up to $k$ uniformly distributed items from a current time-window as old items expire and new ones arrive. We call sampling algorithms {\bf succinct} if they use provably optimal (up to constant factors) {\bf worst-case} memory to maintain $k$ items (either with or without replacement). We stress that in many applications structures that have {\em expected} succinct representation as the time progresses are not sufficient, as small probability events eventually happen with probability 1. Thus, in this paper we ask the following question: are Succinct Sampling on Streams (or $S^3$-algorithms)possible, and if so for what models? Perhaps somewhat surprisingly, we show that $S^3$-algorithms are possible for {\em all} variants of the problem mentioned above, i.e. both with and without replacement and both for one-at-a-time and bursty arrival models. Finally, we use $S^3$ algorithms to solve various problems in sliding windows model, including frequency moments, counting triangles, entropy and density estimations. For these problems we present \emph{first} solutions with provable worst-case memory guarantees.
Distributed Power Allocation with Rate Constraints in Gaussian Parallel Interference Channels
Venue: arXiv cs.IT 2008
Year: 2008

This paper considers the minimization of transmit power in Gaussian parallel interference channels, subject to a rate constraint for each user. To derive decentralized solutions that do not require any cooperation among the users, we formulate this power control problem as a (generalized) Nash equilibrium game. We obtain sufficient conditions that guarantee the existence and nonemptiness of the solution set to our problem. Then, to compute the solutions of the game, we propose two distributed algorithms based on the single user waterfilling solution: The \emph{sequential} and the \emph{simultaneous} iterative waterfilling algorithms, wherein the users update their own strategies sequentially and simultaneously, respectively. We derive a unified set of sufficient conditions that guarantee the uniqueness of the solution and global convergence of both algorithms. Our results are applicable to all practical distributed multipoint-to-multipoint interference systems, either wired or wireless, where a quality of service in terms of information rate must be guaranteed for each link.
Interroger un corpus par le sens
Venue: arXiv cs.CL 2008
Year: 2008

In textual knowledge management, statistical methods prevail. Nonetheless, some difficulties cannot be overcome by these methodologies. I propose a symbolic approach using a complete textual analysis to identify which analysis level can improve the the answers provided by a system. The approach identifies word senses and relation between words and generates as many rephrasings as possible. Using synonyms and derivative, the system provides new utterances without changing the original meaning of the sentences. Such a way, an information can be retrieved whatever the question or answer's wording may be.
Coding for Errors and Erasures in Random Network Coding
Venue: arXiv cs.IT 2008
Year: 2008

The problem of error-control in random linear network coding is considered. A ``noncoherent'' or ``channel oblivious'' model is assumed where neither transmitter nor receiver is assumed to have knowledge of the channel transfer characteristic. Motivated by the property that linear network coding is vector-space preserving, information transmission is modelled as the injection into the network of a basis for a vector space $V$ and the collection by the receiver of a basis for a vector space $U$. A metric on the projective geometry associated with the packet space is introduced, and it is shown that a minimum distance decoder for this metric achieves correct decoding if the dimension of the space $V \cap U$ is sufficiently large. If the dimension of each codeword is restricted to a fixed integer, the code forms a subset of a finite-field Grassmannian, or, equivalently, a subset of the vertices of the corresponding Grassmann graph. Sphere-packing and sphere-covering bounds as well as a generalization of the Singleton bound are provided for such codes. Finally, a Reed-Solomon-like code construction, related to Gabidulin's construction of maximum rank-distance codes, is described and a Sudan-style ``list-1'' minimum distance decoding algorithm is provided.
New List Decoding Algorithms for Reed-Solomon and BCH Codes
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we devise a rational curve fitting algorithm and apply it to the list decoding of Reed-Solomon and BCH codes. The proposed list decoding algorithms exhibit the following significant properties. 1 The algorithm corrects up to $n(1-\sqrt{1-D})$ errors for a (generalized) $(n, k, d=n-k+1)$ Reed-Solomon code, which matches the Johnson bound, where $D\eqdef \frac{d}{n}$ denotes the normalized minimum distance. In comparison with the Guruswami-Sudan algorithm, which exhibits the same list correction capability, the former requires multiplicity, which dictates the algorithmic complexity, $O(n(1-\sqrt{1-D}))$, whereas the latter requires multiplicity $O(n^2(1-D))$. With the up-to-date most efficient implementation, the former has complexity $O(n^{6}(1-\sqrt{1-D})^{7/2})$, whereas the latter has complexity $O(n^{10}(1-D)^4)$. 2. With the multiplicity set to one, the derivative list correction capability precisely sits in between the conventional hard-decision decoding and the optimal list decoding. Moreover, the number of candidate codewords is upper bounded by a constant for a fixed code rate and thus, the derivative algorithm exhibits quadratic complexity $O(n^2)$. 3. By utilizing the unique properties of the Berlekamp algorithm, the algorithm corrects up to $\frac{n}{2}(1-\sqrt{1-2D})$ errors for a narrow-sense $(n, k, d)$ binary BCH code, which matches the Johnson bound for binary codes. The algorithmic complexity is $O(n^{6}(1-\sqrt{1-2D})^7)$.
Optimal Cache-Oblivious Mesh Layouts
Venue: arXiv cs.DS 2009
Year: 2009

A mesh is a graph that divides physical space into regularly-shaped regions. Meshes computations form the basis of many applications, e.g. finite-element methods, image rendering, and collision detection. In one important mesh primitive, called a mesh update, each mesh vertex stores a value and repeatedly updates this value based on the values stored in all neighboring vertices. The performance of a mesh update depends on the layout of the mesh in memory. This paper shows how to find a memory layout that guarantees that the mesh update has asymptotically optimal memory performance for any set of memory parameters. Such a memory layout is called cache-oblivious. Formally, for a $d$-dimensional mesh $G$, block size $B$, and cache size $M$ (where $M=Ω(B^d)$), the mesh update of $G$ uses $O(1+|G|/B)$ memory transfers. The paper also shows how the mesh-update performance degrades for smaller caches, where $M=o(B^d)$. The paper then gives two algorithms for finding cache-oblivious mesh layouts. The first layout algorithm runs in time $O(|G|\log^2|G|)$ both in expectation and with high probability on a RAM. It uses $O(1+|G|\log^2(|G|/M)/B)$ memory transfers in expectation and $O(1+(|G|/B)(\log^2(|G|/M) + \log|G|))$ memory transfers with high probability in the cache-oblivious and disk-access machine (DAM) models. The layout is obtained by finding a fully balanced decomposition tree of $G$ and then performing an in-order traversal of the leaves of the tree. The second algorithm runs faster by almost a $\log|G|/\log\log|G|$ factor in all three memory models, both in expectation and with high probability. The layout obtained by finding a relax-balanced decomposition tree of $G$ and then performing an in-order traversal of the leaves of the tree.