OpenRaiser/Intern-Atlas huggingface dataset:
Signature Quantization in Fading CDMA With Limited Feedback
Venue: arXiv cs.IT 2011
Year: 2011

In this work, we analyze the performance of a signature quantization scheme for reverse-link Direct Sequence (DS)- Code Division Multiple Access (CDMA). Assuming perfect estimates of the channel and interference covariance, the receiver selects the signature that minimizes interference power or maximizes signal-to-interference plus noise ratio (SINR) for a desired user from a signature codebook. The codebook index corresponding to the optimal signature is then relayed to the user with a finite number of bits via a feedback channel. Here we are interested in the performance of a Random Vector Quantization (RVQ) codebook, which contains independent isotropically distributed vectors. Assuming arbitrary transmit power allocation, we consider additive white Gaussian noise (AWGN) channel first with no fading and subsequently, with multipath fading. We derive the corresponding SINR in a large system limit at the output of matched filter and linear minimum mean squared error (MMSE) receiver. Numerical examples show that the derived large system results give a good approximation to the performance of finite-size system and that the MMSE receiver achieves close to a single-user performance with only one feedback bit per signature element.
Faster Approximate String Matching for Short Patterns
Venue: arXiv cs.DS 2011
Year: 2011

We study the classical approximate string matching problem, that is, given strings $P$ and $Q$ and an error threshold $k$, find all ending positions of substrings of $Q$ whose edit distance to $P$ is at most $k$. Let $P$ and $Q$ have lengths $m$ and $n$, respectively. On a standard unit-cost word RAM with word size $w \geq \log n$ we present an algorithm using time $$ O(nk \cdot \min(\frac{\log^2 m}{\log n},\frac{\log^2 m\log w}{w}) + n) $$ When $P$ is short, namely, $m = 2^{o(\sqrt{\log n})}$ or $m = 2^{o(\sqrt{w/\log w})}$ this improves the previously best known time bounds for the problem. The result is achieved using a novel implementation of the Landau-Vishkin algorithm based on tabulation and word-level parallelism.
Distributed Scalar Quantization for Computing: High-Resolution Analysis and Extensions
Venue: arXiv cs.IT 2011
Year: 2011

Communication of quantized information is frequently followed by a computation. We consider situations of \emph{distributed functional scalar quantization}: distributed scalar quantization of (possibly correlated) sources followed by centralized computation of a function. Under smoothness conditions on the sources and function, companding scalar quantizer designs are developed to minimize mean-squared error (MSE) of the computed function as the quantizer resolution is allowed to grow. Striking improvements over quantizers designed without consideration of the function are possible and are larger in the entropy-constrained setting than in the fixed-rate setting. As extensions to the basic analysis, we characterize a large class of functions for which regular quantization suffices, consider certain functions for which asymptotic optimality is achieved without arbitrarily fine quantization, and allow limited collaboration between source encoders. In the entropy-constrained setting, a single bit per sample communicated between encoders can have an arbitrarily-large effect on functional distortion. In contrast, such communication has very little effect in the fixed-rate setting.
Channel Estimation and Linear Precoding in Multiuser Multiple-Antenna TDD Systems
Venue: arXiv cs.IT 2011
Year: 2011

Traditional approaches in the analysis of downlink systems decouple the precoding and the channel estimation problems. However, in cellular systems with mobile users, these two problems are in fact tightly coupled. In this paper, this coupling is explicitly studied by accounting for channel training overhead and estimation error while determining the overall system throughput. The paper studies the problem of utilizing imperfect channel estimates for efficient linear precoding and user selection. It presents precoding methods that take into account the degree of channel estimation error. Information-theoretic lower and upper bounds are derived to evaluate the performance of these precoding methods. In typical scenarios, these bounds are close.
Fault Attacks on RSA Public Keys: Left-To-Right Implementations are also Vulnerable
Venue: arXiv cs.CR 2011
Year: 2011

After attacking the RSA by injecting fault and corresponding countermeasures, works appear now about the need for protecting RSA public elements against fault attacks. We provide here an extension of a recent attack based on the public modulus corruption. The difficulty to decompose the "Left-To-Right" exponentiation into partial multiplications is overcome by modifying the public modulus to a number with known factorization. This fault model is justified here by a complete study of faulty prime numbers with a fixed size. The good success rate of this attack combined with its practicability raises the question of using faults for changing algebraic properties of finite field based cryptosystems.
On the Energy Benefit of Network Coding for Wireless Multiple Unicast
Venue: arXiv cs.IT 2011
Year: 2011

We consider the energy savings that can be obtained by employing network coding instead of plain routing in wireless multiple unicast problems. We establish lower bounds on the benefit of network coding, defined as the maximum of the ratio of the minimum energy required by routing and network coding solutions, where the maximum is over all configurations. It is shown that if coding and routing solutions are using the same transmission range, the benefit in $d$-dimensional networks is at least $2d/\lfloor\sqrt{d}\rfloor$. Moreover, it is shown that if the transmission range can be optimized for routing and coding individually, the benefit in 2-dimensional networks is at least 3. Our results imply that codes following a \emph{decode-and-recombine} strategy are not always optimal regarding energy efficiency.
How happy is your web browsing? A model to quantify satisfaction of an Internet user, searching for desired information
Venue: arXiv cs.HC 2011
Year: 2011

We feel happy when web-browsing operations provide us with necessary information; otherwise, we feel bitter. How to measure this happiness (or bitterness)? How does the profile of happiness grow and decay during the course of web-browsing? We propose a probabilistic framework that models evolution of user satisfaction, on top of his/her continuous frustration at not finding the required information. It is found that the cumulative satisfaction profile of a web-searching individual can be modeled effectively as the sum of random number of random terms, where each term is mutually independent random variable, originating from 'memoryless' Poisson flow. Evolution of satisfaction over the entire time interval of user's browsing was modeled with auto-correlation analysis. A utilitarian marker, magnitude of greater than unity of which describe happy web-searching operations; and an empirical limit that connects user's satisfaction with his frustration level - are proposed too. Presence of pertinent information in the very first page of a web-site and magnitude of the decay parameter of user satisfaction (frustration, irritation etc.), are found to be two key aspects that dominate web-browser's psychology. The proposed model employed different combination of decay parameter, searching time and number of helpful web-sites. Obtained results are found to match the results from three real-life case-studies.
Fast FPT algorithms for vertex subset and vertex partitioning problems using neighborhood unions
Venue: arXiv cs.DS 2011
Year: 2011

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods across a cut of a graph. Boolean-width is similar to rank-width, which is related to the number of $GF[2]$-sums (1+1=0) of neighborhoods instead of the boolean-sums (1+1=1) used for boolean-width. We give algorithms for a large class of NP-hard vertex subset and vertex partitioning problems that are FPT when parameterized by either boolean-width, rank-width or clique-width, with runtime single exponential in either parameter if given the pertinent optimal decomposition. To compare boolean-width versus rank-width or clique-width, we first show that for any graph, the square root of its boolean-width is never more than its rank-width. Next, we exhibit a class of graphs, the Hsu-grids, for which we can solve NP-hard problems in polynomial time, if we use the right parameter. An $n \times \frac{n}{10}$ Hsu-grid on ${1/10}n^2$ vertices has boolean-width $Θ(\log n)$ and rank-width $Θ(n)$. Moreover, any optimal rank-decomposition of such a graph will have boolean-width $Θ(n)$, i.e. exponential in the optimal boolean-width. A main open problem is to approximate the boolean-width better than what is given by the algorithm for rank-width [Hliněný and Oum, 2008]
Privacy in Search Logs
Venue: arXiv cs.DB 2011
Year: 2011

Search engine companies collect the "database of intentions", the histories of their users' search queries. These search logs are a gold mine for researchers. Search engine companies, however, are wary of publishing search logs in order not to disclose sensitive information. In this paper we analyze algorithms for publishing frequent keywords, queries and clicks of a search log. We first show how methods that achieve variants of $k$-anonymity are vulnerable to active attacks. We then demonstrate that the stronger guarantee ensured by $ε$-differential privacy unfortunately does not provide any utility for this problem. We then propose an algorithm ZEALOUS and show how to set its parameters to achieve $(ε,δ)$-probabilistic privacy. We also contrast our analysis of ZEALOUS with an analysis by Korolova et al. [17] that achieves $(ε',δ')$-indistinguishability. Our paper concludes with a large experimental study using real applications where we compare ZEALOUS and previous work that achieves $k$-anonymity in search log publishing. Our results show that ZEALOUS yields comparable utility to $k-$anonymity while at the same time achieving much stronger privacy guarantees.
Colorful Strips
Venue: arXiv cs.CG 2011
Year: 2011

Given a planar point set and an integer $k$, we wish to color the points with $k$ colors so that any axis-aligned strip containing enough points contains all colors. The goal is to bound the necessary size of such a strip, as a function of $k$. We show that if the strip size is at least $2k{-}1$, such a coloring can always be found. We prove that the size of the strip is also bounded in any fixed number of dimensions. In contrast to the planar case, we show that deciding whether a 3D point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. We also consider the problem of coloring a given set of axis-aligned strips, so that any sufficiently covered point in the plane is covered by $k$ colors. We show that in $d$ dimensions the required coverage is at most $d(k{-}1)+1$. Lower bounds are given for the two problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. Finally, we study a variant where strips are replaced by wedges.
Modelling Concurrency with Comtraces and Generalized Comtraces
Venue: arXiv cs.LO 2011
Year: 2011

Comtraces (combined traces) are extensions of Mazurkiewicz traces that can model the "not later than" relationship. In this paper, we first introduce the novel notion of generalized comtraces, extensions of comtraces that can additionally model the "non-simultaneously" relationship. Then we study some basic algebraic properties and canonical reprentations of comtraces and generalized comtraces. Finally we analyze the relationship between generalized comtraces and generalized stratified order structures. The major technical contribution of this paper is a proof showing that generalized comtraces can be represented by generalized stratified order structures.
Inapproximability of the Tutte polynomial of a planar graph
Venue: arXiv cs.CC 2011
Year: 2011

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: given as input a planar graph G, determine T(G;x,y). Vertigan completely mapped the complexity of exactly computing the Tutte polynomial of a planar graph. He showed that the problem can be solved in polynomial time if (x,y) is on the hyperbola H_q given by (x-1)(y-1)=q for q=1 or q=2 or if (x,y) is one of the two special points (x,y)=(-1,-1) or (x,y)=(1,1). Otherwise, the problem is #P-hard. In this paper, we consider the problem of approximating T(G;x,y), in the usual sense of "fully polynomial randomised approximation scheme" or FPRAS. Roughly speaking, an FPRAS is required to produce, in polynomial time and with high probability, an answer that has small relative error. Assuming that NP is different from RP, we show that there is no FPRAS for the Tutte polynomial in a large portion of the (x,y) plane. In particular, there is no FPRAS if x>1, y<-1 or if y>1, x<-1 or if x<0, y<0 and q>5. Also, there is no FPRAS if x<1, y<1 and q=3. For q>5, our result is intriguing because it shows that there is no FPRAS at (x,y)=(1-q/(1+epsilon),-epsilon) for any positive epsilon but it leaves open the limit point epsilon=0, which corresponds to approximately counting q-colourings of a planar graph.
Randomised Buffer Management with Bounded Delay against Adaptive Adversary
Venue: arXiv cs.DS 2011
Year: 2011

We give a new analysis of the RMix algorithm by Chin et al. for the Buffer Management with Bounded Delay problem (or online scheduling of unit jobs to maximise weighted throughput). Unlike the original proof of e/(e-1)-competitiveness, the new one holds even in adaptive-online adversary model. In fact, the proof works also for a slightly more general problem studied by Bie{ń}kowski et al.
Caching in Wireless Networks
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of delivering content cached in a wireless network of n nodes randomly located on a square of area n. The network performance is described by the n2^n-dimensional caching capacity region of the wireless network. We provide an inner bound on this caching capacity region, and, in the high path-loss regime, a matching (in the scaling sense) outer bound. For large path-loss exponent, this provides an information-theoretic scaling characterization of the entire caching capacity region. The proposed communication scheme achieving the inner bound shows that the problems of cache selection and channel coding can be solved separately without loss of order-optimality. On the other hand, our results show that the common architecture of nearest-neighbor cache selection can be arbitrarily bad, implying that cache selection and load balancing need to be performed jointly.
Monadic second-order model-checking on decomposable matroids
Venue: arXiv cs.DM 2011
Year: 2011

A notion of branch-width, which generalizes the one known for graphs, can be defined for matroids. We first give a proof of the polynomial time model-checking of monadic second-order formulas on representable matroids of bounded branch-width, by reduction to monadic second-order formulas on trees. This proof is much simpler than the one previously known. We also provide a link between our logical approach and a grammar that allows to build matroids of bounded branch-width. Finally, we introduce a new class of non-necessarily representable matroids, described by a grammar and on which monadic second-order formulas can be checked in linear time.
A Fresh Look at Coding for q-ary Symmetric Channels
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies coding schemes for the $q$-ary symmetric channel based on binary low-density parity-check (LDPC) codes that work for any alphabet size $q=2^m$, $m\in\mathbb{N}$, thus complementing some recently proposed packet-based schemes requiring large $q$. First, theoretical optimality of a simple layered scheme is shown, then a practical coding scheme based on a simple modification of standard binary LDPC decoding is proposed. The decoder is derived from first principles and using a factor-graph representation of a front-end that maps $q$-ary symbols to groups of $m$ bits connected to a binary code. The front-end can be processed with a complexity that is linear in $m=\log_2 q$. An extrinsic information transfer chart analysis is carried out and used for code optimization. Finally, it is shown how the same decoder structure can also be applied to a larger class of $q$-ary channels.
On Secure Network Coding with Nonuniform or Restricted Wiretap Sets
Venue: arXiv cs.IT 2011
Year: 2011

The secrecy capacity of a network, for a given collection of permissible wiretap sets, is the maximum rate of communication such that observing links in any permissible wiretap set reveals no information about the message. This paper considers secure network coding with nonuniform or restricted wiretap sets, for example, networks with unequal link capacities where a wiretapper can wiretap any subset of $k$ links, or networks where only a subset of links can be wiretapped. Existing results show that for the case of uniform wiretap sets (networks with equal capacity links/packets where any $k$ can be wiretapped), the secrecy capacity is given by the cut-set bound, and can be achieved by injecting $k$ random keys at the source which are decoded at the sink along with the message. This is the case whether or not the communicating users have information about the choice of wiretap set. In contrast, we show that for the nonuniform case, the cut-set bound is not achievable in general when the wiretap set is unknown, whereas it is achievable when the wiretap set is made known. We give achievable strategies where random keys are canceled at intermediate non-sink nodes, or injected at intermediate non-source nodes. Finally, we show that determining the secrecy capacity is a NP-hard problem.
Solution of Non-Square Fuzzy Linear Systems
Venue: arXiv cs.NA 2011
Year: 2011

In this paper, a linear system of equations with crisp coefficients and fuzzy right-hand sides is investigated. All possible cases pertaining to the number of variables, n, and the number of equations, m, are dealt with. A solution is sought not as a fuzzy vector, as usual, but as a fuzzy set of vectors. Each vector in the solution set solves the given fuzzy linear system with a certain possibility. Assuming that the coefficient matrix is a full rank matrix, three cases are considered: For m = n (square system), the solution set is shown to be a parallelepiped in coordinate space and is expressed by an explicit formula. For m > n (overdetermined system), the solution set is proved to be a convex polyhedron and a novel geometric method is proposed to compute it. For m < n (underdetermined system), by determining the contribution of free variables, general solution is computed. From the results of three cases mentioned above, a method is proposed to handle the general case, in which the coefficient matrix is not necessarily a full rank matrix. Comprehensive examples are provided and investigated in depth to illustrate each case and suggested method.
Large-Scale Time-Shifted Streaming Delivery
Venue: arXiv cs.NI 2011
Year: 2011

An attractive new feature of connected TV systems consists in allowing users to access past portions of the TV channel. This feature, called time-shifted streaming, is now used by millions of TV viewers. We address in this paper the design of a large-scale delivery system for time-shifted streaming. We highlight the characteristics of time-shifted streaming that prevent known video delivery systems to be used. Then, we present two proposals that meet the demand for two radically different types of TV operator. First, the Peer-Assisted Catch-Up Streaming system, namely PACUS, aims at reducing the load on the server of a large TV broadcasters without losing the control of the TV delivery. Second, the turntable structure, is an overlay of nodes that allow an independent content delivery network or a small independent TV broadcaster to ensure that all past TV programs are stored and as available as possible. We show through extensive simulations that our objectives are reached, with a reduction of up to three quarters of the traffic for PACUS and a 100\% guaranteed availability for the turntable structure. We also compare our proposals to the main previous works in the area.
Binary Non-tiles
Venue: arXiv cs.DM 2011
Year: 2011

A subset V of GF(2)^n is a tile if GF(2)^n can be covered by disjoint translates of V. In other words, V is a tile if and only if there is a subset A of GF(2)^n such that V+A = GF(2)^n uniquely (i.e., v + a = v' + a' implies that v=v' and a=a' where v,v' in V and a,a' in A). In some problems in coding theory and hashing we are given a putative tile V, and wish to know whether or not it is a tile. In this paper we give two computational criteria for certifying that V is not a tile. The first involves impossibility of a bin-packing problem, and the second involves infeasibility of a linear program. We apply both criteria to a list of putative tiles given by Gordon, Miller, and Ostapenko in that none of them are, in fact, tiles.
Relating Granger causality to directed information theory for networks of stochastic processes
Venue: arXiv cs.IT 2011
Year: 2011

This paper addresses the problem of inferring circulation of information between multiple stochastic processes. We discuss two possible frameworks in which the problem can be studied: directed information theory and Granger causality. The main goal of the paper is to study the connection between these two frameworks. In the case of directed information theory, we stress the importance of Kramer's causal conditioning. This type of conditioning is necessary not only in the definition of the directed information but also for handling causal side information. We also show how directed information decomposes into the sum of two measures, the first one related to Schreiber's transfer entropy quantifies the dynamical aspects of causality, whereas the second one, termed instantaneous information exchange, quantifies the instantaneous aspect of causality. After having recalled the definition of Granger causality, we establish its connection with directed information theory. The connection is particularly studied in the Gaussian case, showing that Geweke's measures of Granger causality correspond to the transfer entropy and the instantaneous information exchange. This allows to propose an information theoretic formulation of Granger causality.
Time-domain approach to energy efficiency in high-performance network element design
Venue: arXiv cs.NI 2011
Year: 2011

Energy efficiency is a corner stone of sustainability in data center and high-performance networking. However, at present there is a notable structural mismatch between network silicon development targets and network equipment utilization patterns in the field. In particular, some aspects of network energy utilization (eg load-proportional energy consumption) routinely stay out of focus during system design and implementation. Drawing from hands-on research and development in high-speed and grid networking, we identify a novel approach to energy efficiency in network engineering. In this paper, we demonstrate how the problem of efficient network system design can be dissected into smaller sections based on timescales of traffic processing. The newly proposed approach allows R&D efforts to be tightly paired to resources and sustainability targets to improve energy efficiency in many classes of network and telecom devices.