OpenRaiser/Intern-Atlas huggingface dataset:
Minimax Robust Quickest Change Detection
Venue: arXiv cs.IT 2010
Year: 2010

The popular criteria of optimality for quickest change detection procedures are the Lorden criterion, the Shiryaev-Roberts-Pollak criterion, and the Bayesian criterion. In this paper a robust version of these quickest change detection problems is considered when the pre-change and post-change distributions are not known exactly but belong to known uncertainty classes of distributions. For uncertainty classes that satisfy a specific condition, it is shown that one can identify least favorable distributions (LFDs) from the uncertainty classes, such that the detection rule designed for the LFDs is optimal for the robust problem in a minimax sense. The condition is similar to that required for the identification of LFDs for the robust hypothesis testing problem originally studied by Huber. An upper bound on the delay incurred by the robust test is also obtained in the asymptotic setting under the Lorden criterion of optimality. This bound quantifies the delay penalty incurred to guarantee robustness. When the LFDs can be identified, the proposed test is easier to implement than the CUSUM test based on the Generalized Likelihood Ratio (GLR) statistic which is a popular approach for such robust change detection problems. The proposed test is also shown to give better performance than the GLR test in simulations for some parameter values.
Tile Packing Tomography is NP-hard
Venue: arXiv cs.CC 2010
Year: 2010

Discrete tomography deals with reconstructing finite spatial objects from lower dimensional projections and has applications for example in timetable design. In this paper we consider the problem of reconstructing a tile packing from its row and column projections. It consists of disjoint copies of a fixed tile, all contained in some rectangular grid. The projections tell how many cells are covered by a tile in each row and column. How difficult is it to construct a tile packing satisfying given projections? It was known to be solvable by a greedy algorithm for bars (tiles of width or height 1), and NP-hardness results were known for some specific tiles. This paper shows that the problem is NP-hard whenever the tile is not a bar.
Model Selection: Two Fundamental Measures of Coherence and Their Algorithmic Significance
Venue: arXiv cs.IT 2010
Year: 2010

The problem of model selection arises in a number of contexts, such as compressed sensing, subset selection in linear regression, estimation of structures in graphical models, and signal denoising. This paper generalizes the notion of \emph{incoherence} in the existing literature on model selection and introduces two fundamental measures of coherence---termed as the worst-case coherence and the average coherence---among the columns of a design matrix. In particular, it utilizes these two measures of coherence to provide an in-depth analysis of a simple one-step thresholding (OST) algorithm for model selection. One of the key insights offered by the ensuing analysis is that OST is feasible for model selection as long as the design matrix obeys an easily verifiable property. In addition, the paper also characterizes the model-selection performance of OST in terms of the worst-case coherence, μ, and establishes that OST performs near-optimally in the low signal-to-noise ratio regime for N x C design matrices with μ= O(N^{-1/2}). Finally, in contrast to some of the existing literature on model selection, the analysis in the paper is nonasymptotic in nature, it does not require knowledge of the true model order, it is applicable to generic (random or deterministic) design matrices, and it neither requires submatrices of the design matrix to have full rank, nor does it assume a statistical prior on the values of the nonzero entries of the data vector.
Towards a Dichotomy for the Possible Winner Problem in Elections Based on Scoring Rules
Venue: arXiv cs.CC 2010
Year: 2010

To make a joint decision, agents (or voters) are often required to provide their preferences as linear orders. To determine a winner, the given linear orders can be aggregated according to a voting protocol. However, in realistic settings, the voters may often only provide partial orders. This directly leads to the Possible Winner problem that asks, given a set of partial votes, whether a distinguished candidate can still become a winner. In this work, we consider the computational complexity of Possible Winner for the broad class of voting protocols defined by scoring rules. A scoring rule provides a score value for every position which a candidate can have in a linear order. Prominent examples include plurality, k-approval, and Borda. Generalizing previous NP-hardness results for some special cases, we settle the computational complexity for all but one scoring rule. More precisely, for an unbounded number of candidates and unweighted voters, we show that Possible Winner is NP-complete for all pure scoring rules except plurality, veto, and the scoring rule defined by the scoring vector (2,1,...,1,0), while it is solvable in polynomial time for plurality and veto.
End-to-End Algebraic Network Coding for Wireless TCP/IP Networks
Venue: arXiv cs.IT 2010
Year: 2010

The Transmission Control Protocol (TCP) was designed to provide reliable transport services in wired networks. In such networks, packet losses mainly occur due to congestion. Hence, TCP was designed to apply congestion avoidance techniques to cope with packet losses. Nowadays, TCP is also utilized in wireless networks where, besides congestion, numerous other reasons for packet losses exist. This results in reduced throughput and increased transmission round-trip time when the state of the wireless channel is bad. We propose a new network layer, that transparently sits below the transport layer and hides non congestion-imposed packet losses from TCP. The network coding in this new layer is based on the well-known class of Maximum Distance Separable (MDS) codes.
Efficient Relay Beamforming Design with SIC Detection for Dual-Hop MIMO Relay Networks
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we consider a dual-hop Multiple Input Multiple Output (MIMO) relay wireless network, in which a source-destination pair both equipped with multiple antennas communicates through a large number of half-duplex amplify-and-forward (AF) relay terminals. Two novel linear beamforming schemes based on the matched filter (MF) and regularized zero-forcing (RZF) precoding techniques are proposed for the MIMO relay system. We focus on the linear process at the relay nodes and design the new relay beamformers by utilizing the channel state information (CSI) of both backward channel and forward channel. The proposed beamforming designs are based on the QR decomposition (QRD) filter at the destination node which performs successive interference cancellation (SIC) to achieve the maximum spatial multiplexing gain. Simulation results demonstrate that the proposed beamformers that fulfil both the intranode array gain and distributed array gain outperform other relaying schemes under different system parameters in terms of the ergodic capacity.
Evolutionary multi-stage financial scenario tree generation
Venue: arXiv cs.NE 2010
Year: 2010

Multi-stage financial decision optimization under uncertainty depends on a careful numerical approximation of the underlying stochastic process, which describes the future returns of the selected assets or asset categories. Various approaches towards an optimal generation of discrete-time, discrete-state approximations (represented as scenario trees) have been suggested in the literature. In this paper, a new evolutionary algorithm to create scenario trees for multi-stage financial optimization models will be presented. Numerical results and implementation details conclude the paper.
Network Coding for Computing: Cut-Set Bounds
Venue: arXiv cs.IT 2010
Year: 2010

The following \textit{network computing} problem is considered. Source nodes in a directed acyclic network generate independent messages and a single receiver node computes a target function $f$ of the messages. The objective is to maximize the average number of times $f$ can be computed per network usage, i.e., the ``computing capacity''. The \textit{network coding} problem for a single-receiver network is a special case of the network computing problem in which all of the source messages must be reproduced at the receiver. For network coding with a single receiver, routing is known to achieve the capacity by achieving the network \textit{min-cut} upper bound. We extend the definition of min-cut to the network computing problem and show that the min-cut is still an upper bound on the maximum achievable rate and is tight for computing (using coding) any target function in multi-edge tree networks and for computing linear target functions in any network. We also study the bound's tightness for different classes of target functions. In particular, we give a lower bound on the computing capacity in terms of the Steiner tree packing number and a different bound for symmetric functions. We also show that for certain networks and target functions, the computing capacity can be less than an arbitrarily small fraction of the min-cut bound.
Application Driven Joint Uplink-Downlink Optimization in Wireless Communications
Venue: arXiv cs.IT 2010
Year: 2010

This paper introduces a new mathematical framework, which is used to derive joint uplink/downlink achievable rate regions for multi-user spatial multiplexing between one base station and multiple terminals. The framework consists of two models: the first one is a simple transmission model for uplink and downlink, which is capable to give a lower bound on the capacity for the case that the transmission is subject to imperfect CSI. A detailed model for concrete channel estimation and feedback schemes provides parameter input to the former model and covers the most important aspects such as pilot design optimization, linear channel estimation, feedback delay, and feedback quantization. We apply this framework to determine optimal pilot densities and CSI feedback quantity, given that a weighted sum of uplink and downlink throughput is to be maximized for a certain user velocity. We show that for low speed, and if downlink throughput is of particular importance, a significant portion of the uplink should be invested into CSI feedback. At higher velocity, however, downlink performance becomes mainly affected by CSI feedback delay, and hence CSI feedback brings little gain considering the inherent sacrifice of uplink capacity. We further show that for high velocities, it becomes beneficial to use no CSI feedback at all, but apply random beamforming in the downlink and operate in time-division duplex.
Computing Least Fixed Points of Probabilistic Systems of Polynomials
Venue: arXiv cs.DS 2010
Year: 2010

We study systems of equations of the form X1 = f1(X1, ..., Xn), ..., Xn = fn(X1, ..., Xn), where each fi is a polynomial with nonnegative coefficients that add up to 1. The least nonnegative solution, say mu, of such equation systems is central to problems from various areas, like physics, biology, computational linguistics and probabilistic program verification. We give a simple and strongly polynomial algorithm to decide whether mu=(1, ..., 1) holds. Furthermore, we present an algorithm that computes reliable sequences of lower and upper bounds on mu, converging linearly to mu. Our algorithm has these features despite using inexact arithmetic for efficiency. We report on experiments that show the performance of our algorithms.
Complexity Analysis of Unsaturated Flow in Heterogeneous Media Using a Complex Network Approach
Venue: arXiv cs.CE 2010
Year: 2010

In this study, we investigate the complexity of two-phase flow (air/water) in a heterogeneous soil sample by using complex network theory, where the supposed porous media is non-deformable media, under the time-dependent gas pressure. Based on the different similarity measurements (i.e., correlation, Euclidean metrics) over the emerged patterns from the evolution of saturation of non-wetting phase of a multi-heterogeneous soil sample, the emerged complex networks are recognized. Understanding of the properties of complex networks (such degree distribution, mean path length, clustering coefficient) can be supposed as a way to analysis of variation of saturation profiles structures (as the solution of finite element method on the coupled PDEs) where complexity is coming from the changeable connection and links between assumed nodes. Also, the path of evolution of the supposed system will be illustrated on the state space of networks either in correlation and Euclidean measurements. The results of analysis showed in a closed system the designed complex networks approach to small world network where the mean path length and clustering coefficient are low and high, respectively. As another result, the evolution of macro -states of system (such mean velocity of air or pressure) can be scaled with characteristics of structure complexity of saturation. In other part, we tried to find a phase transition criterion based on the variation of non-wetting phase velocity profiles over a network which had been constructed over correlation distance.
Diversity-Multiplexing-Delay Tradeoffs in MIMO Multihop Networks with ARQ
Venue: arXiv cs.IT 2010
Year: 2010

Tradeoff in diversity, multiplexing, and delay in multihop MIMO relay networks with ARQ is studied, where the random delay is caused by queueing and ARQ retransmission. This leads to an optimal ARQ allocation problem with per-hop delay or end-to-end delay constraint. The optimal ARQ allocation has to trade off between the ARQ error that the receiver fails to decode in the allocated maximum ARQ rounds and the packet loss due to queueing delay. These two probability of errors are characterized using the diversity-multiplexing-delay tradeoff (DMDT) (without queueing) and the tail probability of random delay derived using large deviation techniques, respectively. Then the optimal ARQ allocation problem can be formulated as a convex optimization problem. We show that the optimal ARQ allocation should balance each link performance as well avoid significant queue delay, which is also demonstrated by numerical examples.
A Complete Theory of Everything (will be subjective)
Venue: arXiv cs.IT 2010
Year: 2010

Increasingly encompassing models have been suggested for our world. Theories range from generally accepted to increasingly speculative to apparently bogus. The progression of theories from ego- to geo- to helio-centric models to universe and multiverse theories and beyond was accompanied by a dramatic increase in the sizes of the postulated worlds, with humans being expelled from their center to ever more remote and random locations. Rather than leading to a true theory of everything, this trend faces a turning point after which the predictive power of such theories decreases (actually to zero). Incorporating the location and other capacities of the observer into such theories avoids this problem and allows to distinguish meaningful from predictively meaningless theories. This also leads to a truly complete theory of everything consisting of a (conventional objective) theory of everything plus a (novel subjective) observer process. The observer localization is neither based on the controversial anthropic principle, nor has it anything to do with the quantum-mechanical observation process. The suggested principle is extended to more practical (partial, approximate, probabilistic, parametric) world models (rather than theories of everything). Finally, I provide a justification of Ockham's razor, and criticize the anthropic principle, the doomsday argument, the no free lunch theorem, and the falsifiability dogma.
Exact Regeneration Codes for Distributed Storage Repair Using Interference Alignment
Venue: arXiv cs.IT 2010
Year: 2010

The high repair cost of (n,k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of codes, called Regenerating Codes, that optimally trade off storage cost for repair bandwidth. On one end of this spectrum of Regenerating Codes are Minimum Storage Regenerating (MSR) codes that can match the minimum storage cost of MDS codes while also significantly reducing repair bandwidth. In this paper, we describe Exact-MSR codes which allow for any failed nodes (whether they are systematic or parity nodes) to be regenerated exactly rather than only functionally or information-equivalently. We show that Exact-MSR codes come with no loss of optimality with respect to random-network-coding based MSR codes (matching the cutset-based lower bound on repair bandwidth) for the cases of: (a) k/n <= 1/2; and (b) k <= 3. Our constructive approach is based on interference alignment techniques, and, unlike the previous class of random-network-coding based approaches, we provide explicit and deterministic coding schemes that require a finite-field size of at most 2(n-k).
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses
Venue: arXiv cs.CC 2010
Year: 2010

This paper presents the following results on sets that are complete for NP. 1. If there is a problem in NP that requires exponential time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. 2. If there is a problem in coNP that cannot be solved by polynomial-size nondeterministic circuits, then every many-one complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. 3. If there exist a one-way permutation that is secure against subexponential-size circuits and there is a hard tally language in NP intersect coNP, then there is a Turing complete language for NP that is not many-one complete. Our first two results use worst-case hardness hypotheses whereas earlier work that showed similar results relied on average-case or almost-everywhere hardness assumptions. The use of average-case and worst-case hypotheses in the last result is unique as previous results obtaining the same consequence relied on almost-everywhere hardness results.
Intrinsic Universality in Self-Assembly
Venue: arXiv cs.CC 2010
Year: 2010

We show that the Tile Assembly Model exhibits a strong notion of universality where the goal is to give a single tile assembly system that simulates the behavior of any other tile assembly system. We give a tile assembly system that is capable of simulating a very wide class of tile systems, including itself. Specifically, we give a tile set that simulates the assembly of any tile assembly system in a class of systems that we call \emph{locally consistent}: each tile binds with exactly the strength needed to stay attached, and that there are no glue mismatches between tiles in any produced assembly. Our construction is reminiscent of the studies of \emph{intrinsic universality} of cellular automata by Ollinger and others, in the sense that our simulation of a tile system $T$ by a tile system $U$ represents each tile in an assembly produced by $T$ by a $c \times c$ block of tiles in $U$, where $c$ is a constant depending on $T$ but not on the size of the assembly $T$ produces (which may in fact be infinite). Also, our construction improves on earlier simulations of tile assembly systems by other tile assembly systems (in particular, those of Soloveichik and Winfree, and of Demaine et al.) in that we simulate the actual process of self-assembly, not just the end result, as in Soloveichik and Winfree's construction, and we do not discriminate against infinite structures. Both previous results simulate only temperature 1 systems, whereas our construction simulates tile assembly systems operating at temperature 2.
How to retrieve priced data
Venue: arXiv cs.CR 2010
Year: 2010

Databases are an indispensable resource for retrieving up-to-date information. However, curious database operators may be able to find out the users' interests when the users buy something from the database. For these cases, if the digital goods have the identical prices, then a $k$-out-of-$n$ oblivious transfer protocol could help the users to hide their choices, but when the goods have different prices, this would not work. In this paper, we propose a scheme to help users to keep their choices secret when buying priced digital goods from databases.
Self-Selected or Mandated, Open Access Increases Citation Impact for Higher Quality Research
Venue: arXiv cs.CY 2010
Year: 2010

Articles whose authors make them Open Access (OA) by self-archiving them online are cited significantly more than articles accessible only to subscribers. Some have suggested that this "OA Advantage" may not be causal but just a self-selection bias, because authors preferentially make higher-quality articles OA. To test this we compared self-selective self-archiving with mandatory self-archiving for a sample of 27,197 articles published 2002-2006 in 1,984 journals. The OA Advantage proved just as high for both. Logistic regression showed that the advantage is independent of other correlates of citations (article age; journal impact factor; number of co-authors, references or pages; field; article type; or country) and greatest for the most highly cited articles. The OA Advantage is real, independent and causal, but skewed. Its size is indeed correlated with quality, just as citations themselves are (the top 20% of articles receive about 80% of all citations). The advantage is greater for the more citeable articles, not because of a quality bias from authors self-selecting what to make OA, but because of a quality advantage, from users self-selecting what to use and cite, freed by OA from the constraints of selective accessibility to subscribers only.
MapReduce for Integer Factorization
Venue: arXiv cs.DC 2010
Year: 2010

Integer factorization is a very hard computational problem. Currently no efficient algorithm for integer factorization is publicly known. However, this is an important problem on which it relies the security of many real world cryptographic systems. I present an implementation of a fast factorization algorithm on MapReduce. MapReduce is a programming model for high performance applications developed originally at Google. The quadratic sieve algorithm is split into the different MapReduce phases and compared against a standard implementation.
Semantic Modeling and Retrieval of Dance Video Annotations
Venue: arXiv cs.MM 2010
Year: 2010

Dance video is one of the important types of narrative videos with semantic rich content. This paper proposes a new meta model, Dance Video Content Model (DVCM) to represent the expressive semantics of the dance videos at multiple granularity levels. The DVCM is designed based on the concepts such as video, shot, segment, event and object, which are the components of MPEG-7 MDS. This paper introduces a new relationship type called Temporal Semantic Relationship to infer the semantic relationships between the dance video objects. Inverted file based index is created to reduce the search time of the dance queries. The effectiveness of containment queries using precision and recall is depicted. Keywords: Dance Video Annotations, Effectiveness Metrics, Metamodeling, Temporal Semantic Relationships.
MacWilliams Identities for Terminated Convolutional Codes
Venue: arXiv cs.IT 2010
Year: 2010

Shearer and McEliece [1977] showed that there is no MacWilliams identity for the free distance spectra of orthogonal linear convolutional codes. We show that on the other hand there does exist a MacWilliams identity between the generating functions of the weight distributions per unit time of a linear convolutional code C and its orthogonal code C^\perp, and that this distribution is as useful as the free distance spectrum for estimating code performance. These observations are similar to those made recently by Bocharova, Hug, Johannesson and Kudryashov; however, we focus on terminating by tail-biting rather than by truncation.