OpenRaiser/Intern-Atlas huggingface dataset:
Simple Channel Coding Bounds
Venue: arXiv cs.IT 2010
Year: 2010

New channel coding converse and achievability bounds are derived for a single use of an arbitrary channel. Both bounds are expressed using a quantity called the "smooth 0-divergence", which is a generalization of Renyi's divergence of order 0. The bounds are also studied in the limit of large block-lengths. In particular, they combine to give a general capacity formula which is equivalent to the one derived by Verdu and Han.
Weighted Well-Covered Graphs without Cycles of Length 4, 5, 6 and 7
Venue: arXiv cs.DM 2010
Year: 2010

A graph is well-covered if every maximal independent set has the same cardinality. The recognition problem of well-covered graphs is known to be co-NP-complete. Let w be a weight function defined on the vertices of G. Then G is w-well-covered if all maximal independent sets of G are of the same weight. The set of weight functions w for which a graph is w-well-covered is a vector space. We prove that finding the vector space of weight functions under which an input graph is w-well-covered can be done in polynomial time, if the input graph does not contain cycles of length 4, 5, 6 and 7.
Rate-Distortion with Side-Information at Many Decoders
Venue: arXiv cs.IT 2010
Year: 2010

We present a new inner bound for the rate region of the $t$-stage successive-refinement problem with side-information. We also present a new upper bound for the rate-distortion function for lossy-source coding with multiple decoders and side-information. Characterising this rate-distortion function is a long-standing open problem, and it is widely believed that the tightest upper bound is provided by Theorem 2 of Heegard and Berger's paper "Rate Distortion when Side Information may be Absent", \emph{IEEE Trans. Inform. Theory}, 1985. We give a counterexample to Heegard and Berger's result.
Randomized Self-Assembly for Exact Shapes
Venue: arXiv cs.CC 2010
Year: 2010

Working in Winfree's abstract tile assembly model, we show that a constant-size tile assembly system can be programmed through relative tile concentrations to build an n x n square with high probability, for any sufficiently large n. This answers an open question of Kao and Schweller (Randomized Self-Assembly for Approximate Shapes, ICALP 2008), who showed how to build an approximately n x n square using tile concentration programming, and asked whether the approximation could be made exact with high probability. We show how this technique can be modified to answer another question of Kao and Schweller, by showing that a constant-size tile assembly system can be programmed through tile concentrations to assemble arbitrary finite *scaled shapes*, which are shapes modified by replacing each point with a c x c block of points, for some integer c. Furthermore, we exhibit a smooth tradeoff between specifying bits of n via tile concentrations versus specifying them via hard-coded tile types, which allows tile concentration programming to be employed for specifying a fraction of the bits of "input" to a tile assembly system, under the constraint that concentrations can only be specified to a limited precision. Finally, to account for some unrealistic aspects of the tile concentration programming model, we show how to modify the construction to use only concentrations that are arbitrarily close to uniform.
A Hybrid Multicast-Unicast Infrastructure for Efficient Publish-Subscribe in Enterprise Networks
Venue: arXiv cs.NI 2010
Year: 2010

One of the main challenges in building a large scale publish-subscribe infrastructure in an enterprise network, is to provide the subscribers with the required information, while minimizing the consumed host and network resources. Typically, previous approaches utilize either IP multicast or point-to-point unicast for efficient dissemination of the information. In this work, we propose a novel hybrid framework, which is a combination of both multicast and unicast data dissemination. Our hybrid framework allows us to take the advantages of both multicast and unicast, while avoiding their drawbacks. We investigate several algorithms for computing the best mapping of publishers' transmissions into multicast and unicast transport. Using extensive simulations, we show that our hybrid framework reduces consumed host and network resources, outperforming traditional solutions. To insure the subscribers interests closely resemble those of real-world settings, our simulations are based on stock market data and on recorded IBM WebShpere subscriptions.
Language recognition by generalized quantum finite automata with unbounded error (abstract & poster)
Venue: arXiv cs.CC 2010
Year: 2010

In this note, we generalize the results of arXiv:0901.2703v1 We show that all one-way quantum finite automaton (QFA) models that are at least as general as Kondacs-Watrous QFA's are equivalent in power to classical probabilistic finite automata in this setting. Unlike their probabilistic counterparts, allowing the tape head to stay put for some steps during its traversal of the input does enlarge the class of languages recognized by such QFA's with unbounded error. (Note that, the proof of Theorem 1 in the abstract was presented in the previous version (arXiv:0901.2703v1).)
A Mathematical Basis for the Chaining of Lossy Interface Adapters
Venue: arXiv cs.DM 2010
Year: 2010

Despite providing similar functionality, multiple network services may require the use of different interfaces to access the functionality, and this problem will only get worse with the widespread deployment of ubiquitous computing environments. One way around this problem is to use interface adapters that adapt one interface into another. Chaining these adapters allows flexible interface adaptation with fewer adapters, but the loss incurred due to imperfect interface adaptation must be considered. This paper outlines a mathematical basis for analyzing the chaining of lossy interface adapters. We also show that the problem of finding an optimal interface adapter chain is NP-complete.
An Optimal Multi-Unit Combinatorial Procurement Auction with Single Minded Bidders
Venue: arXiv cs.GT 2010
Year: 2010

The current art in optimal combinatorial auctions is limited to handling the case of single units of multiple items, with each bidder bidding on exactly one bundle (single minded bidders). This paper extends the current art by proposing an optimal auction for procuring multiple units of multiple items when the bidders are single minded. The auction minimizes the cost of procurement while satisfying Bayesian incentive compatibility and interim individual rationality. Under appropriate regularity conditions, this optimal auction also satisfies dominant strategy incentive compatibility.
A Unified Perspective on Parity- and Syndrome-Based Binary Data Compression Using Off-the-Shelf Turbo Codecs
Venue: arXiv cs.IT 2010
Year: 2010

We consider the problem of compressing memoryless binary data with or without side information at the decoder. We review the parity- and the syndrome-based approaches and discuss their theoretical limits, assuming that there exists a virtual binary symmetric channel between the source and the side information, and that the source is not necessarily uniformly distributed. We take a factor-graph-based approach in order to devise how to take full advantage of the ready-available iterative decoding procedures when turbo codes are employed, in both a parity- or a syndrome-based fashion. We end up obtaining a unified decoder formulation that holds both for error-free and for error-prone encoder-to-decoder transmission over generic channels. To support the theoretical results, the different compression systems analyzed in the paper are also experimentally tested. They are compared against several different approaches proposed in literature and shown to be competitive in a variety of cases.
A Multiobjective Optimization Framework for Routing in Wireless Ad Hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

Wireless ad hoc networks are seldom characterized by one single performance metric, yet the current literature lacks a flexible framework to assist in characterizing the design tradeoffs in such networks. In this work, we address this problem by proposing a new modeling framework for routing in ad hoc networks, which used in conjunction with metaheuristic multiobjective search algorithms, will result in a better understanding of network behavior and performance when multiple criteria are relevant. Our approach is to take a holistic view of the network that captures the cross-interactions among interference management techniques implemented at various layers of the protocol stack. The resulting framework is a complex multiobjective optimization problem that can be efficiently solved through existing multiobjective search techniques. In this contribution, we present the Pareto optimal sets for an example sensor network when delay, robustness and energy are considered. The aim of this paper is to present the framework and hence for conciseness purposes, the multiobjective optimization search is not developed herein.
On the Gaussian MAC with Imperfect Feedback
Venue: arXiv cs.IT 2010
Year: 2010

New achievable rate regions are derived for the two-user additive white Gaussian multiple-access channel with noisy feedback. The regions exhibit the following two properties. Irrespective of the (finite) Gaussian feedback-noise variances, the regions include rate points that lie outside the no-feedback capacity region, and when the feedback-noise variances tend to 0 the regions converge to the perfect-feedback capacity region. The new achievable regions also apply to the partial-feedback setting where one of the transmitters has a noisy feedback link and the other transmitter has no feedback at all. Again, irrespective of the (finite) noise variance on the feedback link, the regions include rate points that lie outside the no-feedback capacity region. Moreover, in the case of perfect partial feedback, i.e., where the only feedback link is noise-free, for certain channel parameters the new regions include rate points that lie outside the Cover-Leung region. This answers in the negative the question posed by van der Meulen as to whether the Cover-Leung region equals the capacity region of the Gaussian multiple-access channel with perfect partial feedback. Finally, we propose new achievable regions also for a setting where the receiver is cognizant of the realizations of the noise sequences on the feedback links.
Linear Time Split Decomposition Revisited
Venue: arXiv cs.DM 2010
Year: 2010

Given a family F of subsets of a ground set V, its orthogonal is defined to be the family of subsets that do not overlap any element of F. Using this tool we revisit the problem of designing a simple linear time algorithm for undirected graph split (also known as 1-join) decomposition.
Ptarithmetic
Venue: arXiv cs.LO 2010
Year: 2010

The present article introduces ptarithmetic (short for "polynomial time arithmetic") -- a formal number theory similar to the well known Peano arithmetic, but based on the recently born computability logic (see http://www.cis.upenn.edu/~giorgi/cl.html) instead of classical logic. The formulas of ptarithmetic represent interactive computational problems rather than just true/false statements, and their "truth" is understood as existence of a polynomial time solution. The system of ptarithmetic elaborated in this article is shown to be sound and complete. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a polynomial time solution and, furthermore, such a solution can be effectively extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a polynomial time solution is represented by some theorem T of the system. The paper is self-contained, and can be read without any previous familiarity with computability logic.
Error-Correcting Tournaments
Venue: arXiv cs.AI 2010
Year: 2010

We present a family of pairwise tournaments reducing $k$-class classification to binary classification. These reductions are provably robust against a constant fraction of binary errors. The results improve on the PECOC construction \cite{SECOC} with an exponential improvement in computation, from $O(k)$ to $O(\log_2 k)$, and the removal of a square root in the regret dependence, matching the best possible computation and regret up to a constant.
Progress in Computer-Assisted Inductive Theorem Proving by Human-Orientedness and Descente Infinie?
Venue: arXiv cs.AI 2010
Year: 2010

In this short position paper we briefly review the development history of automated inductive theorem proving and computer-assisted mathematical induction. We think that the current low expectations on progress in this field result from a faulty narrow-scope historical projection. Our main motivation is to explain--on an abstract but hopefully sufficiently descriptive level--why we believe that future progress in the field is to result from human-orientedness and descente infinie.
On Optimum End-to-End Distortion in MIMO Systems
Venue: arXiv cs.IT 2010
Year: 2010

This paper presents the joint impact of the numbers of antennas, source-to-channel bandwidth ratio and spatial correlation on the optimum expected end-to-end distortion in an outage-free MIMO system. In particular, based on an analytical expression valid for any SNR, a closed-form expression of the optimum asymptotic expected end-to-end distortion valid for high SNR is derived. It is comprised of the optimum distortion exponent and the multiplicative optimum distortion factor. Demonstrated by the simulation results, the analysis on the joint impact of the optimum distortion exponent and the optimum distortion factor explains the behavior of the optimum expected end-to-end distortion varying with the numbers of antennas, source-to-channel bandwidth ratio and spatial correlation. It is also proved that as the correlation tends to zero, the optimum asymptotic expected end-to-end distortion in the setting of correlated channel approaches that in the setting of uncorrelated channel. The results in this paper could be performance objectives for analog-source transmission systems. To some extend, they are instructive for system design.
Performance Assessment of MIMO-BICM Demodulators based on System Capacity
Venue: arXiv cs.IT 2010
Year: 2010

We provide a comprehensive performance comparison of soft-output and hard-output demodulators in the context of non-iterative multiple-input multiple-output bit-interleaved coded modulation (MIMO-BICM). Coded bit error rate (BER), widely used in literature for demodulator comparison, has the drawback of depending strongly on the error correcting code being used. This motivates us to propose a code-independent performance measure in terms of system capacity, i.e., mutual information of the equivalent modulation channel that comprises modulator, wireless channel, and demodulator. We present extensive numerical results for ergodic and quasi-static fading channels under perfect and imperfect channel state information. These results reveal that the performance ranking of MIMO demodulators is rate-dependent. Furthermore, they provide new insights regarding MIMO-BICM system design, i.e., the choice of antenna configuration, symbol constellation, and demodulator for a given target rate.
Compressive estimation of doubly selective channels in multicarrier systems: Leakage effects and sparsity-enhancing processing
Venue: arXiv cs.IT 2010
Year: 2010

We consider the application of compressed sensing (CS) to the estimation of doubly selective channels within pulse-shaping multicarrier systems (which include OFDM systems as a special case). By exploiting sparsity in the delay-Doppler domain, CS-based channel estimation allows for an increase in spectral efficiency through a reduction of the number of pilot symbols. For combating leakage effects that limit the delay-Doppler sparsity, we propose a sparsity-enhancing basis expansion and a method for optimizing the basis with or without prior statistical information about the channel. We also present an alternative CS-based channel estimator for (potentially) strongly time-frequency dispersive channels, which is capable of estimating the "off-diagonal" channel coefficients characterizing intersymbol and intercarrier interference (ISI/ICI). For this estimator, we propose a basis construction combining Fourier (exponential) and prolate spheroidal sequences. Simulation results assess the performance gains achieved by the proposed sparsity-enhancing processing techniques and by explicit estimation of ISI/ICI channel coefficients.
SEPIA: Security through Private Information Aggregation
Venue: arXiv cs.NI 2010
Year: 2010

Secure multiparty computation (MPC) allows joint privacy-preserving computations on data of multiple parties. Although MPC has been studied substantially, building solutions that are practical in terms of computation and communication cost is still a major challenge. In this paper, we investigate the practical usefulness of MPC for multi-domain network security and monitoring. We first optimize MPC comparison operations for processing high volume data in near real-time. We then design privacy-preserving protocols for event correlation and aggregation of network traffic statistics, such as addition of volume metrics, computation of feature entropy, and distinct item count. Optimizing performance of parallel invocations, we implement our protocols along with a complete set of basic operations in a library called SEPIA. We evaluate the running time and bandwidth requirements of our protocols in realistic settings on a local cluster as well as on PlanetLab and show that they work in near real-time for up to 140 input providers and 9 computation nodes. Compared to implementations using existing general-purpose MPC frameworks, our protocols are significantly faster, requiring, for example, 3 minutes for a task that takes 2 days with general-purpose frameworks. This improvement paves the way for new applications of MPC in the area of networking. Finally, we run SEPIA's protocols on real traffic traces of 17 networks and show how they provide new possibilities for distributed troubleshooting and early anomaly detection.
Turbo Packet Combining for Broadband Space-Time BICM Hybrid-ARQ Systems with Co-Channel Interference
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, efficient turbo packet combining for single carrier (SC) broadband multiple-input--multiple-output (MIMO) hybrid--automatic repeat request (ARQ) transmission with unknown co-channel interference (CCI) is studied. We propose a new frequency domain soft minimum mean square error (MMSE)-based signal level combining technique where received signals and channel frequency responses (CFR)s corresponding to all retransmissions are used to decode the data packet. We provide a recursive implementation algorithm for the introduced scheme, and show that both its computational complexity and memory requirements are quite insensitive to the ARQ delay, i.e., maximum number of ARQ rounds. Furthermore, we analyze the asymptotic performance, and show that under a sum-rank condition on the CCI MIMO ARQ channel, the proposed packet combining scheme is not interference-limited. Simulation results are provided to demonstrate the gains offered by the proposed technique.
Two Designs of Space-Time Block Codes Achieving Full Diversity with Partial Interference Cancellation Group Decoding
Venue: arXiv cs.IT 2010
Year: 2010

A partial interference cancellation (PIC) group decoding based space-time block code (STBC) design criterion was recently proposed by Guo and Xia, where the decoding complexity and the code rate trade-off is dealt when the full diversity is achieved. In this paper, two designs of STBC are proposed for any number of transmit antennas that can obtain full diversity when a PIC group decoding (with a particular grouping scheme) is applied at receiver. With the PIC group decoding and an appropriate grouping scheme for the decoding, the proposed STBC are shown to obtain the same diversity gain as the ML decoding, but have a low decoding complexity. The first proposed STBC is designed with multiple diagonal layers and it can obtain the full diversity for two-layer design with the PIC group decoding and the rate is up to 2 symbols per channel use. But with PIC-SIC group decoding, the first proposed STBC can obtain full diversity for any number of layers and the rate can be full. The second proposed STBC can obtain full diversity and a rate up to 9/4 with the PIC group decoding. Some code design examples are given and simulation results show that the newly proposed STBC can well address the rate-performance-complexity tradeoff of the MIMO systems.
Refined Coding Bounds and Code Constructions for Coherent Network Error Correction
Venue: arXiv cs.IT 2010
Year: 2010

Coherent network error correction is the error-control problem in network coding with the knowledge of the network codes at the source and sink nodes. With respect to a given set of local encoding kernels defining a linear network code, we obtain refined versions of the Hamming bound, the Singleton bound and the Gilbert-Varshamov bound for coherent network error correction. Similar to its classical counterpart, this refined Singleton bound is tight for linear network codes. The tightness of this refined bound is shown by two construction algorithms of linear network codes achieving this bound. These two algorithms illustrate different design methods: one makes use of existing network coding algorithms for error-free transmission and the other makes use of classical error-correcting codes. The implication of the tightness of the refined Singleton bound is that the sink nodes with higher maximum flow values can have higher error correction capabilities.
Reverse nearest neighbor queries in fixed dimension
Venue: arXiv cs.CG 2010
Year: 2010

Reverse nearest neighbor queries are defined as follows: Given an input point-set P, and a query point q, find all the points p in P whose nearest point in P U {q} \ {p} is q. We give a data structure to answer reverse nearest neighbor queries in fixed-dimensional Euclidean space. Our data structure uses O(n) space, its preprocessing time is O(n log n), and its query time is O(log n).
Lexicographically least words in the orbit closure of the Rudin-Shapiro word
Venue: arXiv cs.FL 2010
Year: 2010

We give an effective characterization of the lexicographically least word in the orbit closure of the Rudin-Shapiro word w having a specified prefix. In particular, the lexicographically least word in the orbit closure of the Rudin-Shapiro word is 0w. This answers a question Allouche et al.
Faster Projection in Sphere Decoding
Venue: arXiv cs.IT 2010
Year: 2010

Most of the calculations in standard sphere decoders are redundant, in the sense that they either calculate quantities that are never used or calculate some quantities more than once. A new method, which is applicable to lattices as well as finite constellations, is proposed to avoid these redundant calculations while still returning the same result. Pseudocode is given to facilitate immediate implementation. Simulations show that the speed gain with the proposed method increases linearly with the lattice dimension. At dimension 60, the new algorithms avoid about 75% of all floating-point operations.