OpenRaiser/Intern-Atlas huggingface dataset:
A Unified Framework for Linear-Programming Based Communication Receivers
Venue: arXiv cs.IT 2011
Year: 2011

It is shown that a large class of communication systems which admit a sum-product algorithm (SPA) based receiver also admit a corresponding linear-programming (LP) based receiver. The two receivers have a relationship defined by the local structure of the underlying graphical model, and are inhibited by the same phenomenon, which we call 'pseudoconfigurations'. This concept is a generalization of the concept of 'pseudocodewords' for linear codes. It is proved that the LP receiver has the 'maximum likelihood certificate' property, and that the receiver output is the lowest cost pseudoconfiguration. Equivalence of graph-cover pseudoconfigurations and linear-programming pseudoconfigurations is also proved. A concept of 'system pseudodistance' is defined which generalizes the existing concept of pseudodistance for binary and nonbinary linear codes. It is demonstrated how the LP design technique may be applied to the problem of joint equalization and decoding of coded transmissions over a frequency selective channel, and a simulation-based analysis of the error events of the resulting LP receiver is also provided. For this particular application, the proposed LP receiver is shown to be competitive with other receivers, and to be capable of outperforming turbo equalization in bit and frame error rate performance.
Qualitative Concurrent Stochastic Games with Imperfect Information
Venue: arXiv cs.FL 2011
Year: 2011

We study a model of games that combines concurrency, imperfect information and stochastic aspects. Those are finite states games in which, at each round, the two players choose, simultaneously and independently, an action. Then a successor state is chosen accordingly to some fixed probability distribution depending on the previous state and on the pair of actions chosen by the players. Imperfect information is modeled as follows: both players have an equivalence relation over states and, instead of observing the exact state, they only know to which equivalence class it belongs. Therefore, if two partial plays are indistinguishable by some player, he should behave the same in both of them. We consider reachability (does the play eventually visit a final state?) and Büchi objective (does the play visit infinitely often a final state?). Our main contribution is to prove that the following problem is complete for 2-ExpTime: decide whether the first player has a strategy that ensures her to almost-surely win against any possible strategy of her oponent. We also characterise those strategies needed by the first player to almost-surely win.
Thermodynamics of Information Retrieval
Venue: arXiv cs.IT 2011
Year: 2011

In this work, we suggest a parameterized statistical model (the gamma distribution) for the frequency of word occurrences in long strings of English text and use this model to build a corresponding thermodynamic picture by constructing the partition function. We then use our partition function to compute thermodynamic quantities such as the free energy and the specific heat. In this approach, the parameters of the word frequency model vary from word to word so that each word has a different corresponding thermodynamics and we suggest that differences in the specific heat reflect differences in how the words are used in language, differentiating keywords from common and function words. Finally, we apply our thermodynamic picture to the problem of retrieval of texts based on keywords and suggest some advantages over traditional information retrieval methods.
Exponential decreasing rate of leaked information in universal random privacy amplification
Venue: arXiv cs.IT 2011
Year: 2011

We derive a new upper bound for Eve's information in secret key generation from a common random number without communication. This bound improves on Bennett et al(1995)'s bound based on the Rényi entropy of order 2 because the bound obtained here uses the Rényi entropy of order $1+s$ for $s \in [0,1]$. This bound is applied to a wire-tap channel. Then, we derive an exponential upper bound for Eve's information. Our exponent is compared with Hayashi(2006)'s exponent. For the additive case, the bound obtained here is better. The result is applied to secret key agreement by public discussion.
The Derivational Complexity Induced by the Dependency Pair Method
Venue: arXiv cs.LO 2011
Year: 2011

We study the derivational complexity induced by the dependency pair method, enhanced with standard refinements. We obtain upper bounds on the derivational complexity induced by the dependency pair method in terms of the derivational complexity of the base techniques employed. In particular we show that the derivational complexity induced by the dependency pair method based on some direct technique, possibly refined by argument filtering, the usable rules criterion, or dependency graphs, is primitive recursive in the derivational complexity induced by the direct method. This implies that the derivational complexity induced by a standard application of the dependency pair method based on traditional termination orders like KBO, LPO, and MPO is exactly the same as if those orders were applied as the only termination technique.
Variations on Muchnik's Conditional Complexity Theorem
Venue: arXiv cs.CC 2011
Year: 2011

Muchnik's theorem about simple conditional descriptions states that for all strings $a$ and $b$ there exists a short program $p$ transforming $a$ to $b$ that has the least possible length and is simple conditional on $b$. In this paper we present two new proofs of this theorem. The first one is based on the on-line matching algorithm for bipartite graphs. The second one, based on extractors, can be generalized to prove a version of Muchnik's theorem for space-bounded Kolmogorov complexity.
Lower Bounds on Syntactic Logic Expressions for Optimization Problems and Duality using Lagrangian Dual to characterize optimality conditions
Venue: arXiv cs.LO 2011
Year: 2011

We show that simple syntactic expressions such as existential second order (ESO) universal Horn formulae can express NP-hard optimisation problems. There is a significant difference between the expressibilities of decision problems and optimisation problems. This is similar to the difference in computation times for the two classes of problems; for example, a 2SAT Horn formula can be satisfied in polynomial time, whereas the optimisation version in NP-hard. It is known that all polynomially solvable decision problems can be expressed as ESO universal ($Π_1$) Horn sentences in the presence of a successor relation. We show here that, on the other hand, if $P \neq NP$, optimisation problems defy such a characterisation, by demonstrating that even a $Π_0$ (quantifier free) Horn formula is unable to guarantee polynomial time solvability. Finally, by connecting concepts in optimisation duality with those in descriptive complexity, we will show a method by which optimisation problems can be solved by a single call to a "decision" Turing machine, as opposed to multiple calls using a classical binary search setting.
A Walk in Facebook: Uniform Sampling of Users in Online Social Networks
Venue: arXiv cs.SI 2011
Year: 2011

Our goal in this paper is to develop a practical framework for obtaining a uniform sample of users in an online social network (OSN) by crawling its social graph. Such a sample allows to estimate any user property and some topological properties as well. To this end, first, we consider and compare several candidate crawling techniques. Two approaches that can produce approximately uniform samples are the Metropolis-Hasting random walk (MHRW) and a re-weighted random walk (RWRW). Both have pros and cons, which we demonstrate through a comparison to each other as well as to the "ground truth." In contrast, using Breadth-First-Search (BFS) or an unadjusted Random Walk (RW) leads to substantially biased results. Second, and in addition to offline performance assessment, we introduce online formal convergence diagnostics to assess sample quality during the data collection process. We show how these diagnostics can be used to effectively determine when a random walk sample is of adequate size and quality. Third, as a case study, we apply the above methods to Facebook and we collect the first, to the best of our knowledge, representative sample of Facebook users. We make it publicly available and employ it to characterize several key properties of Facebook.
On network coding for sum-networks
Venue: arXiv cs.IT 2011
Year: 2011

A directed acyclic network is considered where all the terminals need to recover the sum of the symbols generated at all the sources. We call such a network a sum-network. It is shown that there exists a solvably (and linear solvably) equivalent sum-network for any multiple-unicast network, and thus for any directed acyclic communication network. It is also shown that there exists a linear solvably equivalent multiple-unicast network for every sum-network. It is shown that for any set of polynomials having integer coefficients, there exists a sum-network which is scalar linear solvable over a finite field F if and only if the polynomials have a common root in F. For any finite or cofinite set of prime numbers, a network is constructed which has a vector linear solution of any length if and only if the characteristic of the alphabet field is in the given set. The insufficiency of linear network coding and unachievability of the network coding capacity are proved for sum-networks by using similar known results for communication networks. Under fractional vector linear network coding, a sum-network and its reverse network are shown to be equivalent. However, under non-linear coding, it is shown that there exists a solvable sum-network whose reverse network is not solvable.
Robust Rate-Adaptive Wireless Communication Using ACK/NAK-Feedback
Venue: arXiv cs.IT 2011
Year: 2011

To combat the detrimental effects of the variability in wireless channels, we consider cross-layer rate adaptation based on limited feedback. In particular, based on limited feedback in the form of link-layer acknowledgements (ACK) and negative acknowledgements (NAK), we maximize the physical-layer transmission rate subject to an upper bound on the expected packet error rate. \textr{We take a robust approach in that we do not assume} any particular prior distribution on the channel state. We first analyze the fundamental limitations of such systems and derive an upper bound on the achievable rate for signaling schemes based on uncoded QAM and random Gaussian ensembles. We show that, for channel estimation based on binary ACK/NAK feedback, it may be preferable to use a separate training sequence at high error rates, rather than to exploit low-error-rate data packets themselves. We also develop an adaptive recursive estimator, which is provably asymptotically optimal and asymptotically efficient.
Knowledge-Based Synthesis of Distributed Systems Using Event Structures
Venue: arXiv cs.LO 2011
Year: 2011

To produce a program guaranteed to satisfy a given specification one can synthesize it from a formal constructive proof that a computation satisfying that specification exists. This process is particularly effective if the specifications are written in a high-level language that makes it easy for designers to specify their goals. We consider a high-level specification language that results from adding knowledge to a fragment of Nuprl specifically tailored for specifying distributed protocols, called event theory. We then show how high-level knowledge-based programs can be synthesized from the knowledge-based specifications using a proof development system such as Nuprl. Methods of Halpern and Zuck then apply to convert these knowledge-based protocols to ordinary protocols. These methods can be expressed as heuristic transformation tactics in Nuprl.
The Complexity of Approximating Bounded-Degree Boolean \sharp CSP
Venue: arXiv cs.CC 2011
Year: 2011

The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum allowed degree is large enough (at least 6) we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of {0}, {1} and binary implication. Otherwise, there is no FPRAS unless NP=RP. For lower degree bounds, additional cases arise, where the complexity is related to the complexity of approximately counting independent sets in hypergraphs.
Fault Identification via Non-parametric Belief Propagation
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of identifying a pattern of faults from a set of noisy linear measurements. Unfortunately, maximum a posteriori probability estimation of the fault pattern is computationally intractable. To solve the fault identification problem, we propose a non-parametric belief propagation approach. We show empirically that our belief propagation solver is more accurate than recent state-of-the-art algorithms including interior point methods and semidefinite programming. Our superior performance is explained by the fact that we take into account both the binary nature of the individual faults and the sparsity of the fault pattern arising from their rarity.
The Degrees of Freedom Regions of MIMO Broadcast, Interference, and Cognitive Radio Channels with No CSIT
Venue: arXiv cs.IT 2011
Year: 2011

The degrees of freedom (DoF) regions are characterized for the multiple-input multiple-output (MIMO) broadcast channel (BC), interference channels (IC) (including X and multi-hop interference channels) and the cognitive radio channel (CRC), when there is perfect and no channel state information at the receivers and the transmitter(s) (CSIR and CSIT), respectively. For the K-user MIMO BC, the exact characterization of the DoF region is obtained, which shows that a simple time-division-based transmission scheme is DoF-region optimal. Using the techniques developed for the MIMO BC, the corresponding problems for the two-user MIMO IC and the CRC are addressed. For both of these channels, inner and outer bounds to the DoF region are obtained and are seen to coincide for a vast majority of the relative numbers of antennas at the four terminals, thereby characterizing DoF regions for all but a few cases. Finally, the DoF regions of the $K$-user MIMO IC, the CRC, and X networks are derived for certain classes of these networks, including the one where all transmitters have an equal number of antennas and so do all receivers. The results of this paper are derived for distributions of fading channel matrices and additive noises that are more general than those considered in other simultaneous related works. The DoF regions with and without CSIT are compared and conditions on the relative numbers of antennas at the terminals under which a lack of CSIT does, or does not, result in the loss of DoF are identified, thereby providing, on the one hand, simple and robust communication schemes that don't require CSIT but have the same DoF performance as their previously found CSIT counterparts, and on the other hand, identifying situations where CSI feedback to transmitters would provide gains that are significant enough that even the DoF performance could be improved.
The Knapsack Problem with Neighbour Constraints
Venue: arXiv cs.DS 2011
Year: 2011

We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. In the all-neighbours knapsack problem, an item can be selected only if all its neighbours are also selected. We give approximation algorithms and hardness results when the nodes have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected.
3-Receiver Broadcast Channels with Common and Confidential Messages
Venue: arXiv cs.IT 2011
Year: 2011

This paper establishes inner bounds on the secrecy capacity regions for the general 3-receiver broadcast channel with one common and one confidential message sets. We consider two setups. The first is when the confidential message is to be sent to two receivers and kept secret from the third receiver. Achievability is established using indirect decoding, Wyner wiretap channel coding, and the new idea of generating secrecy from a publicly available superposition codebook. The inner bound is shown to be tight for a class of reversely degraded broadcast channels and when both legitimate receivers are less noisy than the third receiver. The second setup investigated in this paper is when the confidential message is to be sent to one receiver and kept secret from the other two receivers. Achievability in this case follows from Wyner wiretap channel coding and indirect decoding. This inner bound is also shown to be tight for several special cases.
Compression-based investigation of the dynamical properties of cellular automata and other systems
Venue: arXiv cs.CC 2011
Year: 2011

A method for studying the qualitative dynamical properties of abstract computing machines based on the approximation of their program-size complexity using a general lossless compression algorithm is presented. It is shown that the compression-based approach classifies cellular automata (CA) into clusters according to their heuristic behavior, with these clusters showing a correspondence with Wolfram's main classes of CA behavior. A compression based method to estimate a characteristic exponent to detect phase transitions and measure the resiliency or sensitivity of a system to its initial conditions is also proposed. A conjecture regarding the capability of a system to reach computational universality related to the values of this phase transition coefficient is formulated. These ideas constitute a compression-based framework for investigating the dynamical properties of cellular automata and other systems.
A Geometric Approach to Solve Fuzzy Linear Systems
Venue: arXiv cs.NA 2011
Year: 2011

In this paper, linear systems with a crisp real coefficient matrix and with a vector of fuzzy triangular numbers on the right-hand side are studied. A new method, which is based on the geometric representations of linear transformations, is proposed to find solutions. The method uses the fact that a vector of fuzzy triangular numbers forms a rectangular prism in n-dimensional space and that the image of a parallelepiped is also a parallelepiped under a linear transformation. The suggested method clarifies why in general case different approaches do not generate solutions as fuzzy numbers. It is geometrically proved that if the coefficient matrix is a generalized permutation matrix, then the solution of a fuzzy linear system (FLS) is a vector of fuzzy numbers irrespective of the vector on the right-hand side. The most important difference between this and previous papers on FLS is that the solution is sought as a fuzzy set of vectors (with real components) rather than a vector of fuzzy numbers. Each vector in the solution set solves the given FLS with a certain possibility. The suggested method can also be applied in the case when the right-hand side is a vector of fuzzy numbers in parametric form. However, in this case, -cuts of the solution can not be determined by geometric similarity and additional computations are needed.
Interactive Privacy via the Median Mechanism
Venue: arXiv cs.CR 2011
Year: 2011

We define a new interactive differentially private mechanism -- the median mechanism -- for answering arbitrary predicate queries that arrive online. Relative to fixed accuracy and privacy constraints, this mechanism can answer exponentially more queries than the previously best known interactive privacy mechanism (the Laplace mechanism, which independently perturbs each query result). Our guarantee is almost the best possible, even for non-interactive privacy mechanisms. Conceptually, the median mechanism is the first privacy mechanism capable of identifying and exploiting correlations among queries in an interactive setting. We also give an efficient implementation of the median mechanism, with running time polynomial in the number of queries, the database size, and the domain size. This efficient implementation guarantees privacy for all input databases, and accurate query results for almost all input databases. The dependence of the privacy on the number of queries in this mechanism improves over that of the best previously known efficient mechanism by a super-polynomial factor, even in the non-interactive setting.
On Bregman Distances and Divergences of Probability Measures
Venue: arXiv cs.IT 2011
Year: 2011

The paper introduces scaled Bregman distances of probability distributions which admit non-uniform contributions of observed events. They are introduced in a general form covering not only the distances of discrete and continuous stochastic observations, but also the distances of random processes and signals. It is shown that the scaled Bregman distances extend not only the classical ones studied in the previous literature, but also the information divergence and the related wider class of convex divergences of probability measures. An information processing theorem is established too, but only in the sense of invariance w.r.t. statistically sufficient transformations and not in the sense of universal monotonicity. Pathological situations where coding can increase the classical Bregman distance are illustrated by a concrete example. In addition to the classical areas of application of the Bregman distances and convex divergences such as recognition, classification, learning and evaluation of proximity of various features and signals, the paper mentions a new application in 3D-exploratory data analysis. Explicit expressions for the scaled Bregman distances are obtained in general exponential families, with concrete applications in the binomial, Poisson and Rayleigh families, and in the families of exponential processes such as the Poisson and diffusion processes including the classical examples of the Wiener process and geometric Brownian motion.
On game psychology: an experiment on the chess board/screen, should you always "do your best", and why the programs with prescribed weaknesses cannot be our good friends?
Venue: arXiv cs.AI 2011
Year: 2011

It is noted that some unusual moves against a strong chess program greatly weaken its ability to see the serious targets of the game, and its whole level of play... It is suggested to create programs with different weaknesses in order to analyze similar human behavior. Finally, a new version of chess, "Chess Corrida" is suggested.