OpenRaiser/Intern-Atlas huggingface dataset:
Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
Venue: arXiv cs.DS 2011
Year: 2011

In the stochastic knapsack problem, we are given a knapsack of size B, and a set of jobs whose sizes and rewards are drawn from a known probability distribution. However, we know the actual size and reward only when the job completes. How should we schedule jobs to maximize the expected total reward? We know O(1)-approximations when we assume that (i) rewards and sizes are independent random variables, and (ii) we cannot prematurely cancel jobs. What can we say when either or both of these assumptions are changed? The stochastic knapsack problem is of interest in its own right, but techniques developed for it are applicable to other stochastic packing problems. Indeed, ideas for this problem have been useful for budgeted learning problems, where one is given several arms which evolve in a specified stochastic fashion with each pull, and the goal is to pull the arms a total of B times to maximize the reward obtained. Much recent work on this problem focus on the case when the evolution of the arms follows a martingale, i.e., when the expected reward from the future is the same as the reward at the current state. What can we say when the rewards do not form a martingale? In this paper, we give constant-factor approximation algorithms for the stochastic knapsack problem with correlations and/or cancellations, and also for budgeted learning problems where the martingale condition is not satisfied. Indeed, we can show that previously proposed LP relaxations have large integrality gaps. We propose new time-indexed LP relaxations, and convert the fractional solutions into distributions over strategies, and then use the LP values and the time ordering information from these strategies to devise a randomized adaptive scheduling algorithm. We hope our LP formulation and decomposition methods may provide a new way to address other correlated bandit problems with more general contexts.
The Iterated Prisoner's Dilemma on a Cycle
Venue: arXiv cs.GT 2011
Year: 2011

Pavlov, a well-known strategy in game theory, has been shown to have some advantages in the Iterated Prisoner's Dilemma (IPD) game. However, this strategy can be exploited by inveterate defectors. We modify this strategy to mitigate the exploitation. We call the resulting strategy Rational Pavlov. This has a parameter p which measures the "degree of forgiveness" of the players. We study the evolution of cooperation in the IPD game, when n players are arranged in a cycle, and all play this strategy. We examine the effect of varying p on the convergence rate and prove that the convergence rate is fast, O(n log n) time, for high values of p. We also prove that the convergence rate is exponentially slow in n for small enough p. Our analysis leaves a gap in the range of p, but simulations suggest that there is, in fact, a sharp phase transition.
Aligned Interference Neutralization and the Degrees of Freedom of the 2 User Interference Channel with Instantaneous Relay
Venue: arXiv cs.IT 2011
Year: 2011

It is well known that the classical 2 user Gaussian interference channel has only 1 degree of freedom (DoF), which can be achieved by orthogonal time division among the 2 users. It is also known that the use of conventional relays, which introduce a processing delay of at least one symbol duration relative to the direct paths between sources and destinations, does not increase the DoF of the 2 user interference channel. The use of instantaneous relays (relays-without-delay) has been explored for the single user point-to-point setting and it is known that such a relay, even with memoryless forwarding at the relay, can achieve a higher capacity than conventional relays. In this work, we show that the 2 user interference channel with an instantaneous relay, achieves 3/2 DoF. Thus, an instantaneous relay increases not only the capacity but also the DoF of the 2 user interference channel. The achievable scheme is inspired by the aligned interference neutralization scheme recently proposed for the 2X2X2 interference channel. Remarkably the DoF gain is achieved with memoryless relays, i.e., with relays that have no memory of past received symbols.
On weakly APN functions and 4-bit S-Boxes
Venue: arXiv cs.CR 2011
Year: 2011

S-Boxes are important security components of block ciphers. We provide theoretical results on necessary or sufficient criteria for an (invertible) 4-bit S-Box to be weakly APN. Thanks to a classification of 4-bit invertible S-Boxes achieved independently by De Canniére and Leander-Poschmann, we can strengthen our results with a computer-aided proof.
A Sub-Space Method to Detect Multiple Wireless Microphone Signals in TV Band White Space
Venue: arXiv cs.IT 2011
Year: 2011

The main hurdle in the realization of dynamic spectrum access (DSA) systems from physical layer perspective is the reliable sensing of low power licensed users. One such scenario shows up in the unlicensed use of TV bands where the TV Band Devices (TVBDs) are required to sense extremely low power wireless microphones (WMs). The lack of technical standard among various wireless manufacturers and the resemblance of certain WM signals to narrow-band interference signals, such as spurious emissions, further aggravate the problem. Due to these uncertainties, it is extremely difficult to abstract the features of WM signals and hence develop robust sensing algorithms. To partly counter these challenges, we develop a two-stage sub-space algorithm that detects multiple narrow-band analog frequency-modulated signals generated by WMs. The performance of the algorithm is verified by using experimentally captured low power WM signals with received power ranging from -100 to -105 dBm. The problem of differentiating between the WM and other narrow-band signals is left as a future work.
Privacy Preserving Spam Filtering
Venue: arXiv cs.LG 2011
Year: 2011

Email is a private medium of communication, and the inherent privacy constraints form a major obstacle in developing effective spam filtering methods which require access to a large amount of email data belonging to multiple users. To mitigate this problem, we envision a privacy preserving spam filtering system, where the server is able to train and evaluate a logistic regression based spam classifier on the combined email data of all users without being able to observe any emails using primitives such as homomorphic encryption and randomization. We analyze the protocols for correctness and security, and perform experiments of a prototype system on a large scale spam filtering task. State of the art spam filters often use character n-grams as features which result in large sparse data representation, which is not feasible to be used directly with our training and evaluation protocols. We explore various data independent dimensionality reduction which decrease the running time of the protocol making it feasible to use in practice while achieving high accuracy.
An Analytical Model for Service Profile Based Service Quality of an Institutional eLibrary
Venue: arXiv cs.DL 2011
Year: 2011

Devising a scheme for evaluating the service quality of an institutional electronic library is a difficult and challenging task. The challenge comes from the fact that the services provided by an institutional electronic library depend upon the contents requested by the users and the contents housed by the library. Different types of users might be interested in different types of contents. In this paper, we propose a technique for evaluating the service quality of an institutional electronic library. Our scheme is based on the service profiles of contents requested by the users at the server side which is hosted at the library. Further, we propose models to analyze the service quality of an electronic library. For analyzing the service quality, we present two analytical models. The first one is based on the number of days by which the item to be served by the library is delayed and the penalty points per day for the duration for which the item is delayed. The second model is based on the credits earned by the library if the item is served in a timely fashion, and the penalties, thereof, if the item is delayed. These models may help in evaluating the service quality of an electronic library and taking the corrective measures to improve it.
Memory Reduction via Delayed Simulation
Venue: arXiv cs.GT 2011
Year: 2011

We address a central (and classical) issue in the theory of infinite games: the reduction of the memory size that is needed to implement winning strategies in regular infinite games (i.e., controllers that ensure correct behavior against actions of the environment, when the specification is a regular omega-language). We propose an approach which attacks this problem before the construction of a strategy, by first reducing the game graph that is obtained from the specification. For the cases of specifications represented by "request-response"-requirements and general "fairness" conditions, we show that an exponential gain in the size of memory is possible.
An FPTAS for the Lead-Based Multiple Video Transmission LMVT Problem
Venue: arXiv cs.DS 2011
Year: 2011

The Lead-Based Multiple Video Transmission (LMVT) problem is motivated by applications in managing the quality of experience (QoE) of video streaming for mobile clients. In an earlier work, the LMVT problem has been shown to be NP-hard for a specific bit-to-lead conversion function $ϕ$. In this work, we show the problem to be NP-hard even if the function $ϕ$ is linear. We then design a fully polynomial time approximation scheme (FPTAS) for the problem. This problem is exactly equivalent to the Santa Clause Problem on which there has been a lot of work done off-late.
Characterizing and approximating eigenvalue sets of symmetric interval matrices
Venue: arXiv cs.RO 2011
Year: 2011

We consider the eigenvalue problem for the case where the input matrix is symmetric and its entries perturb in some given intervals. We present a characterization of some of the exact boundary points, which allows us to introduce an inner approximation algorithm, that in many case estimates exact bounds. To our knowledge, this is the first algorithm that is able to guaran- tee exactness. We illustrate our approach by several examples and numerical experiments.
Approachability of Convex Sets in Games with Partial Monitoring
Venue: arXiv cs.GT 2011
Year: 2011

We provide a necessary and sufficient condition under which a convex set is approachable in a game with partial monitoring, i.e.\ where players do not observe their opponents' moves but receive random signals. This condition is an extension of Blackwell's Criterion in the full monitoring framework, where players observe at least their payoffs. When our condition is fulfilled, we construct explicitly an approachability strategy, derived from a strategy satisfying some internal consistency property in an auxiliary game. We also provide an example of a convex set, that is neither (weakly)-approachable nor (weakly)-excludable, a situation that cannot occur in the full monitoring case. We finally apply our result to describe an $ε$-optimal strategy of the uninformed player in a zero-sum repeated game with incomplete information on one side.
Numerical investigation of a solar greenhouse tunnel drier for drying of copra
Venue: arXiv cs.OH 2011
Year: 2011

A numerical investigation of a solar greenhouse tunnel drier (SGTD) has been performed. In the present study, the geometry of the tunnel roof is assumed semi-circular which is covered with a UV (200μ) stabilized polyethylene film. The simulated SGTD reduces moisture of copra from 52.2% to 8% in 55 h under full load conditions. A system of partial differential equations describing heat and moisture transfer during drying copra in the solar greenhouse dryer was developed and this system of non-linear partial differential equations was solved numerically using the finite difference method (FDM). The numerical solution was programmed in Compaq Visual FORTRAN version 6.5. The simulated results reasonably agreed with the experimental data for solar drying copra. This model can be used to provide the design data and is also essential for optimal design of the dryer. For instance the user is able to change the radiation properties of the roof cover for different materials of roof cover.
On the Core of a Unicyclic Graph
Venue: arXiv cs.DM 2011
Year: 2011

A set S is independent in a graph G if no two vertices from S are adjacent. By core(G) we mean the intersection of all maximum independent sets. The independence number alpha(G) is the cardinality of a maximum independent set, while mu(G) is the size of a maximum matching in G. A connected graph having only one cycle, say C, is a unicyclic graph. In this paper we prove that if G is a unicyclic graph of order n and n-1 = alpha(G) + mu(G), then core(G) coincides with the union of cores of all trees in G-C.
Efficient evaluation of polynomials over finite fields
Venue: arXiv cs.IT 2011
Year: 2011

A method is described which allows to evaluate efficiently a polynomial in a (possibly trivial) extension of the finite field of its coefficients. Its complexity is shown to be lower than that of standard techniques when the degree of the polynomial is large with respect to the base field. Applications to the syndrome computation in the decoding of cyclic codes, Reed-Solomon codes in particular, are highlighted.
Computing linear functions by linear coding over networks
Venue: arXiv cs.IT 2011
Year: 2011

We consider the scenario in which a set of sources generate messages in a network and a receiver node demands an arbitrary linear function of these messages. We formulate an algebraic test to determine whether an arbitrary network can compute linear functions using linear codes. We identify a class of linear functions that can be computed using linear codes in every network that satisfies a natural cut-based condition. Conversely, for another class of linear functions, we show that the cut-based condition does not guarantee the existence of a linear coding solution. For linear functions over the binary field, the two classes are complements of each other.
Counting Solutions of Constraint Satisfiability Problems:Exact Phase Transitions and Approximate Algorithm
Venue: arXiv cs.AI 2011
Year: 2011

The study of phase transition phenomenon of NP complete problems plays an important role in understanding the nature of hard problems. In this paper, we follow this line of research by considering the problem of counting solutions of Constraint Satisfaction Problems (#CSP). We consider the random model, i.e. RB model. We prove that phase transition of #CSP does exist as the number of variables approaches infinity and the critical values where phase transitions occur are precisely located. Preliminary experimental results also show that the critical point coincides with the theoretical derivation. Moreover, we propose an approximate algorithm to estimate the expectation value of the solutions number of a given CSP instance of RB model.
Further Results on Geometric Properties of a Family of Relative Entropies
Venue: arXiv cs.IT 2011
Year: 2011

This paper extends some geometric properties of a one-parameter family of relative entropies. These arise as redundancies when cumulants of compressed lengths are considered instead of expected compressed lengths. These parametric relative entropies are a generalization of the Kullback-Leibler divergence. They satisfy the Pythagorean property and behave like squared distances. This property, which was known for finite alphabet spaces, is now extended for general measure spaces. Existence of projections onto convex and certain closed sets is also established. Our results may have applications in the Rényi entropy maximization rule of statistical physics.
An Equivariance Theorem with Applications to Renaming (Preliminary Version)
Venue: arXiv cs.DC 2011
Year: 2011

In the renaming problem, each process in a distributed system is issued a unique name from a large name space, and the processes must coordinate with one another to choose unique names from a much smaller name space. We show that lower bounds on the solvability of renaming in an asynchronous distributed system can be formulated as a purely topological question about the existence of an equivariant chain map from a topological disk to a topological annulus. Proving the non-existence of such a map implies the non-existence of a distributed renaming algorithm in several related models of computation.
Physical expander in Virtual Tree Overlay
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we propose a new construction of constantdegree expanders motivated by their application in P2P overlay networks and in particular in the design of robust trees overlay. Our key result can be stated as follows. Consider a complete binary tree T and construct a random pairing Π between leaf nodes and internal nodes. We prove that the graph GΠobtained from T by contracting all pairs (leaf-internal nodes) achieves a constant node expansion with high probability. The use of our result in improving the robustness of tree overlays is straightforward. That is, if each physical node participating to the overlay manages a random pair that couples one virtual internal node and one virtual leaf node then the physical-node layer exhibits a constant expansion with high probability. We encompass the difficulty of obtaining this random tree virtualization by proposing a local, selforganizing and churn resilient uniformly-random pairing algorithm with O(log2 n) running time. Our algorithm has the merit to not modify the original tree virtual overlay (we just control the mapping between physical nodes and virtual nodes). Therefore, our scheme is general and can be applied to a large number of tree overlay implementations. We validate its performances in dynamic environments via extensive simulations.
Variable Length Coding over the Two-User Multiple-Access Channel
Venue: arXiv cs.IT 2011
Year: 2011

For discrete memoryless multiple-access channels, we propose a general definition of variable length codes with a measure of the transmission rates at the receiver side. This gives a receiver perspective on the multiple-access channel coding problem and allows us to characterize the region of achievable rates when the receiver is able to decode each transmitted message at a different instant of time.We show an outer bound on this region and derive a simple coding scheme that can achieve, in particular settings, all rates within the region delimited by the outer bound. In addition, we propose a random variable length coding scheme that achieve the direct part of the block code capacity region of a multiple-access channel without requiring any agreement between the transmitters.
Diversity-Multiplexing Tradeoff in the Low-SNR Regime
Venue: arXiv cs.IT 2011
Year: 2011

An extension of the popular diversity-multiplexing tradeoff framework to the low-SNR (or wideband) regime is proposed. The concept of diversity gain is shown to be redundant in this regime since the outage probability is SNR-independent and depends on the multiplexing gain and the channel power gain statistics only. The outage probability under the DMT framework is obtained in an explicit, closed form for a broad class of channels. The low and high-SNR regime boundaries are explicitly determined for the scalar Rayleigh-fading channel, indicating a significant limitation of the SNR-asymptotic DMT when the multiplexing gain is small.
Transmitting important bits and sailing high radio waves: a decentralized cross-layer approach to cooperative video transmission
Venue: arXiv cs.MM 2011
Year: 2011

We investigate the impact of cooperative relaying on uplink and downlink multi-user (MU) wireless video transmissions. The objective is to maximize the long-term sum of utilities across the video terminals in a decentralized fashion, by jointly optimizing the packet scheduling, the resource allocation, and the cooperation decisions, under the assumption that some nodes are willing to act as cooperative relays. A pricing-based distributed resource allocation framework is adopted, where the price reflects the expected future congestion in the network. Specifically, we formulate the wireless video transmission problem as an MU Markov decision process (MDP) that explicitly considers the cooperation at the physical layer and the medium access control sublayer, the video users' heterogeneous traffic characteristics, the dynamically varying network conditions, and the coupling among the users' transmission strategies across time due to the shared wireless resource. Although MDPs notoriously suffer from the curse of dimensionality, our study shows that, with appropriate simplications and approximations, the complexity of the MU-MDP can be significantly mitigated. Our simulation results demonstrate that integrating cooperative decisions into the MU-MDP optimization can increase the resource price in networks that only support low transmission rates and can decrease the price in networks that support high transmission rates. Additionally, our results show that cooperation allows users with feeble direct signals to achieve improvements in video quality on the order of 5-10 dB peak signal-to-noise ratio (PSNR), with less than 0.8 dB quality loss by users with strong direct signals, and with a moderate increase in total network energy consumption that is significantly less than the energy that a distant node would require to achieve an equivalent PSNR without exploiting cooperative diversity.
Nondeterministic automata: equivalence, bisimulations, and uniform relations
Venue: arXiv cs.FL 2011
Year: 2011

In this paper we study the equivalence of nondeterministic automata pairing the concept of a bisimulation with the recently introduced concept of a uniform relation. In this symbiosis, uniform relations serve as equivalence relations which relate states of two possibly different nondeterministic automata, and bisimulations ensure compatibility with the transitions, initial and terminal states of these automata. We define six types of bisimulations, but due to the duality we discuss three of them: forward, backward-forward, and weak forward bisimulations. For each od these three types of bisimulations we provide a procedure which decides whether there is a bisimulation of this type between two automata, and when it exists, the same procedure computes the greatest one. We also show that there is a uniform forward bisimulation between two automata if and only if the factor automata with respect to the greatest forward bisimulation equivalences on these automata are isomorphic. We prove a similar theorem for weak forward bisimulations, using the concept of a weak forward isomorphism instead of an isomorphism. We also give examples that explain the relationships between the considered types of bisimulations.
Minimum multicuts and Steiner forests for Okamura-Seymour graphs
Venue: arXiv cs.DS 2011
Year: 2011

We study the problem of finding minimum multicuts for an undirected planar graph, where all the terminal vertices are on the boundary of the outer face. This is known as an Okamura-Seymour instance. We show that for such an instance, the minimum multicut problem can be reduced to the minimum-cost Steiner forest problem on a suitably defined dual graph. The minimum-cost Steiner forest problem has a 2-approximation algorithm. Hence, the minimum multicut problem has a 2-approximation algorithm for an Okamura-Seymour instance.