OpenRaiser/Intern-Atlas huggingface dataset:
Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem
Venue: arXiv cs.CC 2010
Year: 2010

Toda proved in 1989 that the (discrete) polynomial time hierarchy, $\mathbf{PH}$, is contained in the class $\mathbf{P}^{#\mathbf{P}}$, namely the class of languages that can be decided by a Turing machine in polynomial time given access to an oracle with the power to compute a function in the counting complexity class $#\mathbf{P}$. This result which illustrates the power of counting is considered to be a seminal result in computational complexity theory. An analogous result in the complexity theory over the reals (in the sense of Blum-Shub-Smale real machines) has been missing so far. In this paper we formulate and prove a real analogue of Toda's theorem. Unlike Toda's proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry -- namely the problem of deciding sentences in the first order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result might be of independent interest to researchers in algorithmic semi-algebraic geometry.
Power-Controlled Feedback and Training for Two-way MIMO Channels
Venue: arXiv cs.IT 2010
Year: 2010

Most communication systems use some form of feedback, often related to channel state information. The common models used in analyses either assume perfect channel state information at the receiver and/or noiseless state feedback links. However, in practical systems, neither is the channel estimate known perfectly at the receiver and nor is the feedback link perfect. In this paper, we study the achievable diversity multiplexing tradeoff using i.i.d. Gaussian codebooks, considering the errors in training the receiver and the errors in the feedback link for FDD systems, where the forward and the feedback are independent MIMO channels. Our key result is that the maximum diversity order with one-bit of feedback information is identical to systems with more feedback bits. Thus, asymptotically in $\mathsf{SNR}$, more than one bit of feedback does not improve the system performance at constant rates. Furthermore, the one-bit diversity-multiplexing performance is identical to the system which has perfect channel state information at the receiver along with noiseless feedback link. This achievability uses novel concepts of power controlled feedback and training, which naturally surface when we consider imperfect channel estimation and noisy feedback links. In the process of evaluating the proposed training and feedback protocols, we find an asymptotic expression for the joint probability of the $\mathsf{SNR}$ exponents of eigenvalues of the actual channel and the estimated channel which may be of independent interest.
Distributed Lossy Averaging
Venue: arXiv cs.IT 2010
Year: 2010

An information theoretic formulation of the distributed averaging problem previously studied in computer science and control is presented. We assume a network with m nodes each observing a WGN source. The nodes communicate and perform local processing with the goal of computing the average of the sources to within a prescribed mean squared error distortion. The network rate distortion function R^*(D) for a 2-node network with correlated Gaussian sources is established. A general cutset lower bound on R^*(D) is established and shown to be achievable to within a factor of 2 via a centralized protocol over a star network. A lower bound on the network rate distortion function for distributed weighted-sum protocols, which is larger in order than the cutset bound by a factor of log m is established. An upper bound on the network rate distortion function for gossip-base weighted-sum protocols, which is only log log m larger in order than the lower bound for a complete graph network, is established. The results suggest that using distributed protocols results in a factor of log m increase in order relative to centralized protocols.
A historical perspective on developing foundations iInfo(TM) information systems: iConsult(TM) and iEntertain(TM) apps using iDescribers(TM) information integration for iOrgs(TM) information systems
Venue: arXiv cs.DC 2010
Year: 2010

Technology now at hand can integrate all kinds of digital information for individuals, groups, and organizations so their information usefully links together. iInfo(TM) information integration works by making connections including examples like the following: - A statistical connection between "being in a traffic jam" and "driving in downtown Trenton between 5PM and 6PM on a weekday." - A terminological connection between "MSR" and "Microsoft Research." - A causal connection between "joining a group" and "being a member of the group." - A syntactic connection between "a pin dropped" and "a dropped pin." - A biological connection between "a dolphin" and "a mammal". - A demographic connection between "undocumented residents of California" and "7% of the population of California." - A geographical connection between "Leeds" and "England." - A temporal connection between "turning on a computer" and "joining an on-line discussion." By making these connections, iInfo offers tremendous value for individuals, families, groups, and organizations in making more effective use of information technology. In practice, integrated information is invariably pervasively inconsistent. Therefore iInfo must be able to make connections even in the face of inconsistency. The business of iInfo is not to make difficult decisions like deciding the ultimate truth or probability of propositions. Instead it provides means for processing information and carefully recording its provenance including arguments (including arguments about arguments) for and against propositions that is used by iConsult(TM) and iEntertain(TM) apps in iOrgs(TM) Information Systems. A historical perspective on the above questions is highly pertinent to the current quest to develop foundations for privacy-friendly client-cloud computing.
A formal calculus on the Riordan near algebra
Venue: arXiv cs.SC 2010
Year: 2010

The Riordan group is the semi-direct product of a multiplicative group of invertible series and a group, under substitution, of non units. The Riordan near algebra, as introduced in this paper, is the Cartesian product of the algebra of formal power series and its principal ideal of non units, equipped with a product that extends the multiplication of the Riordan group. The later is naturally embedded as a subgroup of units into the former. In this paper, we prove the existence of a formal calculus on the Riordan algebra. This formal calculus plays a role similar to those of holomorphic calculi in the Banach or Fréchet algebras setting, but without the constraint of a radius of convergence. Using this calculus, we define \emph{en passant} a notion of generalized powers in the Riordan group.
On the Growth Rate of the Weight Distribution of Irregular Doubly-Generalized LDPC Codes
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, an expression for the asymptotic growth rate of the number of small linear-weight codewords of irregular doubly-generalized LDPC (D-GLDPC) codes is derived. The expression is compact and generalizes existing results for LDPC and generalized LDPC (GLDPC) codes. Ensembles with check or variable node minimum distance greater than 2 are shown to be have good growth rate behavior, while for other ensembles a fundamental parameter is identified which discriminates between an asymptotically small and an asymptotically large expected number of small linear-weight codewords. Also, in the latter case it is shown that the growth rate depends only on the check and variable nodes with minimum distance 2. An important connection between this new result and the stability condition of D-GLDPC codes over the BEC is highlighted. Such a connection, previously observed for LDPC and GLDPC codes, is now extended to the case of D-GLDPC codes. Finally, it is shown that the analysis may be extended to include the growth rate of the stopping set size distribution of irregular D-GLDPC codes.
Combinatorial Deformations of Algebras: Twisting and Perturbations
Venue: arXiv cs.SC 2010
Year: 2010

The framework used to prove the multiplicative law deformation of the algebra of Feynman-Bender diagrams is a \textit{twisted shifted dual law} (in fact, twice). We give here a clear interpretation of its two parameters. The crossing parameter is a deformation of the tensor structure whereas the superposition parameters is a perturbation of the shuffle coproduct of Hoffman type which, in turn, can be interpreted as the diagonal restriction of a superproduct. Here, we systematically detail these constructions.
The Perfect Binary One-Error-Correcting Codes of Length 15: Part II--Properties
Venue: arXiv cs.IT 2010
Year: 2010

A complete classification of the perfect binary one-error-correcting codes of length 15 as well as their extensions of length 16 was recently carried out in [P. R. J. Östergård and O. Pottonen, "The perfect binary one-error-correcting codes of length 15: Part I--Classification," IEEE Trans. Inform. Theory vol. 55, pp. 4657--4660, 2009]. In the current accompanying work, the classified codes are studied in great detail, and their main properties are tabulated. The results include the fact that 33 of the 80 Steiner triple systems of order 15 occur in such codes. Further understanding is gained on full-rank codes via switching, as it turns out that all but two full-rank codes can be obtained through a series of such transformations from the Hamming code. Other topics studied include (non)systematic codes, embedded one-error-correcting codes, and defining sets of codes. A classification of certain mixed perfect codes is also obtained.
Boosting the Accuracy of Differentially-Private Histograms Through Consistency
Venue: arXiv cs.DB 2010
Year: 2010

We show that it is possible to significantly improve the accuracy of a general class of histogram queries while satisfying differential privacy. Our approach carefully chooses a set of queries to evaluate, and then exploits consistency constraints that should hold over the noisy output. In a post-processing phase, we compute the consistent input most likely to have produced the noisy output. The final output is differentially-private and consistent, but in addition, it is often much more accurate. We show, both theoretically and experimentally, that these techniques can be used for estimating the degree sequence of a graph very precisely, and for computing a histogram that can support arbitrary range queries accurately.
Fully-Functional Static and Dynamic Succinct Trees
Venue: arXiv cs.DS 2010
Year: 2010

We propose new succinct representations of ordinal trees, which have been studied extensively. It is known that any $n$-node static tree can be represented in $2n + o(n)$ bits and a number of operations on the tree can be supported in constant time under the word-RAM model. However the data structures are complicated and difficult to dynamize. We propose a simple and flexible data structure, called the range min-max tree, that reduces the large number of relevant tree operations considered in the literature to a few primitives that are carried out in constant time on sufficiently small trees. The result is extended to trees of arbitrary size, achieving $2n + O(n /\polylog(n))$ bits of space. The redundancy is significantly lower than any previous proposal. Our data structure builds on the range min-max tree to achieve $2n+O(n/\log n)$ bits of space and $O(\log n)$ time for all the operations. We also propose an improved data structure using $2n+O(n\log\log n/\log n)$ bits and improving the time to the optimal $O(\log n/\log \log n)$ for most operations. Furthermore, we support sophisticated operations that allow attaching and detaching whole subtrees, in time $\Order(\log^{1+ε} n / \log\log n)$. Our techniques are of independent interest. One allows representing dynamic bitmaps and sequences supporting rank/select and indels, within zero-order entropy bounds and optimal time $O(\log n / \log\log n)$ for all operations on bitmaps and polylog-sized alphabets, and $O(\log n \log σ/ (\log\log n)^2)$ on larger alphabet sizes $σ$. This improves upon the best existing bounds for entropy-bounded storage of dynamic sequences, compressed full-text self-indexes, and compressed-space construction of the Burrows-Wheeler transform.
Protection against link errors and failures using network coding
Venue: arXiv cs.IT 2010
Year: 2010

We propose a network-coding based scheme to protect multiple bidirectional unicast connections against adversarial errors and failures in a network. The network consists of a set of bidirectional primary path connections that carry the uncoded traffic. The end nodes of the bidirectional connections are connected by a set of shared protection paths that provide the redundancy required for protection. Such protection strategies are employed in the domain of optical networks for recovery from failures. In this work we consider the problem of simultaneous protection against adversarial errors and failures. Suppose that n_e paths are corrupted by the omniscient adversary. Under our proposed protocol, the errors can be corrected at all the end nodes with 4n_e protection paths. More generally, if there are n_e adversarial errors and n_f failures, 4n_e + 2n_f protection paths are sufficient. The number of protection paths only depends on the number of errors and failures being protected against and is independent of the number of unicast connections.
A statistical learning approach to color demosaicing
Venue: arXiv cs.CV 2010
Year: 2010

A statistical learning/inference framework for color demosaicing is presented. We start with simplistic assumptions about color constancy, and recast color demosaicing as a blind linear inverse problem: color parameterizes the unknown kernel, while brightness takes on the role of a latent variable. An expectation-maximization algorithm naturally suggests itself for the estimation of them both. Then, as we gradually broaden the family of hypothesis where color is learned, we let our demosaicing behave adaptively, in a manner that reflects our prior knowledge about the statistics of color images. We show that we can incorporate realistic, learned priors without essentially changing the complexity of the simple expectation-maximization algorithm we started with.
Deficiency Zero Petri Nets and Product Form
Venue: arXiv cs.DM 2010
Year: 2010

Consider a Markovian Petri net with race policy. The marking process has a "product form" stationary distribution if the probability of viewing a given marking can be decomposed as the product over places of terms depending only on the local marking. First we observe that the Deficiency Zero Theorem of Feinberg, developped for chemical reaction networks, provides a structural and simple sufficient condition for the existence of a product form. In view of this, we study the classical subclass of free-choice nets. Roughly, we show that the only such Petri nets having a product form are the state machines which can alternatively be viewed as Jackson networks.
Coloring the square of the Cartesian product of two cycles
Venue: arXiv cs.DM 2010
Year: 2010

The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ in such a way that distinct vertices with distance at most two in $G$ are joined by an edge. We study the chromatic number of the square of the Cartesian product $C_m\Box C_n$ of two cycles and show that the value of this parameter is at most 7 except when $m=n=3$, in which case the value is 9, and when $m=n=4$ or $m=3$ and $n=5$, in which case the value is 8. Moreover, we conjecture that whenever $G=C_m\Box C_n$, the chromatic number of $G^2$ equals $\lceil mn/α(G^2) \rceil$, where $α(G^2)$ denotes the size of a maximal independent set in $G^2$.
On the effectiveness of a binless entropy estimator for generalised entropic forms
Venue: arXiv cs.IT 2010
Year: 2010

In this manuscript we discuss the effectiveness of the Kozachenko-Leonenko entropy estimator when generalised to cope with entropic forms customarily applied to study systems evincing asymptotic scale invariance and dependence (either linear or non-linear type). We show that when the variables are independently and identically distributed the estimator is only valuable along the whole domain if the data follow the uniform distribution, whereas for other distributions the estimator is only effectual in the limit of the Boltzmann-Gibbs-Shanon entropic form. We also analyse the influence of the dependence (linear and non-linear) between variables on the accuracy of the estimator between variables. As expected in the last case the estimator looses efficiency for the Boltzmann-Gibbs-Shanon entropic form as well.
Norms and Commitment for iOrgs(TM) Information Systems: Direct Logic(TM) and Participatory Grounding Checking
Venue: arXiv cs.MA 2010
Year: 2010

The fundamental assumption of the Event Calculus is overly simplistic when it comes to organizations in which time-varying properties have to be actively maintained and managed in order to continue to hold and termination by another action is not required for a property to no longer hold. I.e., if active measures are not taken then things will go haywire by default. Similarly extension and revision is required for Grounding Checking properties of systems based on a set of ground inferences. Previously Model Checking as been performed using the model of nondeterministic automata based on states determined by time-points. These nondeterministic automata are not suitable for iOrgs, which are highly structured and operate asynchronously with only loosely bounded nondeterminism. iOrgs Information Systems have been developed as a technology in which organizations have people that are tightly integrated with information technology that enables them to function organizationally. iOrgs formalize existing practices to provide a framework for addressing issues of authority, accountability, scalability, and robustness using methods that are analogous to human organizations. In general -iOrgs are a natural extension Web Services, which are the standard for distributed computing and software application interoperability in large-scale Organizational Computing. -iOrgs are structured by Organizational Commitment that is a special case of Physical Commitment that is defined to be information pledged. iOrgs norms are used to illustrate the following: -Even a very simple microtheory for normative reasoning can engender inconsistency In practice, it is impossible to verify the consistency of a theory for a practical domain. -Improved Safety in Reasoning. It is not safe to use classical logic and probability theory in practical reasoning.
Entropy Message Passing
Venue: arXiv cs.LG 2010
Year: 2010

The paper proposes a new message passing algorithm for cycle-free factor graphs. The proposed "entropy message passing" (EMP) algorithm may be viewed as sum-product message passing over the entropy semiring, which has previously appeared in automata theory. The primary use of EMP is to compute the entropy of a model. However, EMP can also be used to compute expressions that appear in expectation maximization and in gradient descent algorithms.
A Deterministic Equivalent for the Analysis of Correlated MIMO Multiple Access Channels
Venue: arXiv cs.IT 2010
Year: 2010

In this article, novel deterministic equivalents for the Stieltjes transform and the Shannon transform of a class of large dimensional random matrices are provided. These results are used to characterise the ergodic rate region of multiple antenna multiple access channels, when each point-to-point propagation channel is modelled according to the Kronecker model. Specifically, an approximation of all rates achieved within the ergodic rate region is derived and an approximation of the linear precoders that achieve the boundary of the rate region as well as an iterative water-filling algorithm to obtain these precoders are provided. An original feature of this work is that the proposed deterministic equivalents are proved valid even for strong correlation patterns at both communication sides. The above results are validated by Monte Carlo simulations.
Diversity-Multiplexing Tradeoff for the Multiple-Antenna Wire-tap Channel
Venue: arXiv cs.IT 2010
Year: 2010

In this paper the fading multiple antenna (MIMO) wire-tap channel is investigated under short term power constraints. The secret diversity gain and the secret multiplexing gain are defined. Using these definitions, the secret diversitymultiplexing tradeoff (DMT) is calculated analytically for no transmitter side channel state information (CSI) and for full CSI. When there is no CSI at the transmitter, under the assumption of Gaussian codebooks, it is shown that the eavesdropper steals both transmitter and receiver antennas, and the secret DMT depends on the remaining degrees of freedom. When CSI is available at the transmitter (CSIT), the eavesdropper steals only transmitter antennas. This dependence on the availability of CSI is unlike the DMT results without secrecy constraints, where the DMT remains the same for no CSI and full CSI at the transmitter under short term power constraints. A zero-forcing type scheme is shown to achieve the secret DMT when CSIT is available.
Self-Improving Algorithms
Venue: arXiv cs.DS 2010
Year: 2010

We investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an unknown input distribution D. We assume here that D is of product type. More precisely, suppose that we need to process a sequence I_1, I_2, ... of inputs I = (x_1, x_2, ..., x_n) of some fixed length n, where each x_i is drawn independently from some arbitrary, unknown distribution D_i. The goal is to design an algorithm for these inputs so that eventually the expected running time will be optimal for the input distribution D = D_1 * D_2 * ... * D_n. We give such self-improving algorithms for two problems: (i) sorting a sequence of numbers and (ii) computing the Delaunay triangulation of a planar point set. Both algorithms achieve optimal expected limiting complexity. The algorithms begin with a training phase during which they collect information about the input distribution, followed by a stationary regime in which the algorithms settle to their optimized incarnations.
Cutting a Convex Polyhedron Out of a Sphere
Venue: arXiv cs.CG 2010
Year: 2010

Given a convex polyhedron $P$ of $n$ vertices inside a sphere $Q$, we give an $O(n^3)$-time algorithm that cuts $P$ out of $Q$ by using guillotine cuts and has cutting cost $O((\log n)^2)$ times the optimal.