OpenRaiser/Intern-Atlas huggingface dataset:
Hypercontractivity and its applications
Venue: arXiv cs.DM 2011
Year: 2011

Hypercontractive inequalities are a useful tool in dealing with extremal questions in the geometry of high-dimensional discrete and continuous spaces. In this survey we trace a few connections between different manifestations of hypercontractivity, and also present some relatively recent applications of these techniques in computer science.
A Deterministic Polynomial--Time Algorithm for Constructing a Multicast Coding Scheme for Linear Deterministic Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

We propose a new way to construct a multicast coding scheme for linear deterministic relay networks. Our construction can be regarded as a generalization of the well-known multicast network coding scheme of Jaggi et al. to linear deterministic relay networks and is based on the notion of flow for a unicast session that was introduced by the authors in earlier work. We present randomized and deterministic polynomial--time versions of our algorithm and show that for a network with $g$ destinations, our deterministic algorithm can achieve the capacity in $\left\lceil \log(g+1)\right\rceil $ uses of the network.
Deflation and Certified Isolation of Singular Zeros of Polynomial Systems
Venue: arXiv cs.SC 2011
Year: 2011

We develop a new symbolic-numeric algorithm for the certification of singular isolated points, using their associated local ring structure and certified numerical computations. An improvement of an existing method to compute inverse systems is presented, which avoids redundant computation and reduces the size of the intermediate linear systems to solve. We derive a one-step deflation technique, from the description of the multiplicity structure in terms of differentials. The deflated system can be used in Newton-based iterative schemes with quadratic convergence. Starting from a polynomial system and a small-enough neighborhood, we obtain a criterion for the existence and uniqueness of a singular root of a given multiplicity structure, applying a well-chosen symbolic perturbation. Standard verification methods, based eg. on interval arithmetic and a fixed point theorem, are employed to certify that there exists a unique perturbed system with a singular root in the domain. Applications to topological degree computation and to the analysis of real branches of an implicit curve illustrate the method.
Multi-Stage Improved Route Planning Approach: theoretical foundations
Venue: arXiv cs.DS 2011
Year: 2011

A new approach to the static route planning problem, based on a multi-staging concept and a \emph{scope} notion, is presented. The main goal (besides implied efficiency of planning) of our approach is to address---with a solid theoretical foundation---the following two practically motivated aspects: a \emph{route comfort} and a very \emph{limited storage} space of a small navigation device, which both do not seem to be among the chief objectives of many other studies. We show how our novel idea can tackle both these seemingly unrelated aspects at once, and may also contribute to other established route planning approaches with which ours can be naturally combined. We provide a theoretical proof that our approach efficiently computes exact optimal routes within this concept, as well as we demonstrate with experimental results on publicly available road networks of the US the good practical performance of the solution.
Decision-Feedback Differential Detection in Impulse-Radio Ultra-Wideband Systems
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we present decision-feedback differential detection (DF-DD) schemes for autocorrelation-based detection in impulse-radio ultra-wideband (IR-UWB) systems, a signaling scheme regarded as a promising candidate in particular for low-complexity wireless sensor networks. To this end, we first discuss ideal noncoherent sequence estimation and approximations thereof based on block-wise multiple-symbol differential detection (MSDD) and the Viterbi algorithm (VA) from the perspective of tree-search/trellis decoding. Exploiting relations well-known from tree-search decoding, we are able to derive the novel decision-feedback differential detection (DF-DD) schemes. A comprehensive comparison with respect to performance and complexity of the presented schemes in a typical IR-UWB scenario reveals---along with novel insights in techniques for complexity reduction of the sphere decoder applied for MSDD---that sorted DF-DD achieves close-to-optimum performance at very low, and in particular constant receiver complexity.
Collaborative Filtering without Explicit Feedbacks for Digital Recorders
Venue: arXiv cs.IR 2011
Year: 2011

Recommendation is usually reduced to a prediction problem over the function $r(u_a, e_i)$ that returns the expected rating of element $e_i$ for user $u_a$. In the IPTV domain, we deal with an environment where the definitions of all the parameters involved in this function (i.e., user profiles, feedback ratings and elements) are controversial. To our knowledge, this paper represents the first attempt to run collaborative filtering algorithms without inner assumptions: we start our analysis from an unstructured set of recordings, before performing a data pre-processing phase in order to extract useful information. Hence, we experiment with a real Digital Video Recorder system where EPG have not been provided to the user for selecting event timings and where explicit feedbacks were not collected.
CAL: A Language for Aggregating Functional and Extrafunctional Constraints in Streaming Networks
Venue: arXiv cs.PL 2011
Year: 2011

In this article we present the {\em Constraint Aggregation Language} (CAL), a declarative language for describing properties of stateless program components that interact by exchanging messages. CAL allows one to describe functional as well as extra-functional behaviours, such as computation latency. The CAL language intention is to be able to describe the behaviour of so-called boxes in the context of S-Net. However, the language would find application in other coordination models based on stateless components.
Efficient Independence-Based MAP Approach for Robust Markov Networks Structure Discovery
Venue: arXiv cs.AI 2011
Year: 2011

This work introduces the IB-score, a family of independence-based score functions for robust learning of Markov networks independence structures. Markov networks are a widely used graphical representation of probability distributions, with many applications in several fields of science. The main advantage of the IB-score is the possibility of computing it without the need of estimation of the numerical parameters, an NP-hard problem, usually solved through an approximate, data-intensive, iterative optimization. We derive a formal expression for the IB-score from first principles, mainly maximum a posteriori and conditional independence properties, and exemplify several instantiations of it, resulting in two novel algorithms for structure learning: IBMAP-HC and IBMAP-TS. Experimental results over both artificial and real world data show these algorithms achieve important error reductions in the learnt structures when compared with the state-of-the-art independence-based structure learning algorithm GSMN, achieving increments of more than 50% in the amount of independencies they encode correctly, and in some cases, learning correctly over 90% of the edges that GSMN learnt incorrectly. Theoretical analysis shows IBMAP-HC proceeds efficiently, achieving these improvements in a time polynomial to the number of random variables in the domain.
Automated Image Processing for the Analysis of DNA Repair Dynamics
Venue: arXiv cs.CV 2011
Year: 2011

The efficient repair of cellular DNA is essential for the maintenance and inheritance of genomic information. In order to cope with the high frequency of spontaneous and induced DNA damage, a multitude of repair mechanisms have evolved. These are enabled by a wide range of protein factors specifically recognizing different types of lesions and finally restoring the normal DNA sequence. This work focuses on the repair factor XPC (xeroderma pigmentosum complementation group C), which identifies bulky DNA lesions and initiates their removal via the nucleotide excision repair pathway. The binding of XPC to damaged DNA can be visualized in living cells by following the accumulation of a fluorescent XPC fusion at lesions induced by laser microirradiation in a fluorescence microscope. In this work, an automated image processing pipeline is presented which allows to identify and quantify the accumulation reaction without any user interaction. The image processing pipeline comprises a preprocessing stage where the image stack data is filtered and the nucleus of interest is segmented. Afterwards, the images are registered to each other in order to account for movements of the cell, and then a bounding box enclosing the XPC-specific signal is automatically determined. Finally, the time-dependent relocation of XPC is evaluated by analyzing the intensity change within this box. Comparison of the automated processing results with the manual evaluation yields qualitatively similar results. However, the automated analysis provides more accurate, reproducible data with smaller standard errors. The image processing pipeline presented in this work allows for an efficient analysis of large amounts of experimental data with no user interaction required.
Behavioral On-Line Advertising
Venue: arXiv cs.IR 2011
Year: 2011

We present a new algorithm for behavioral targeting of banner advertisements. We record different user's actions such as clicks, search queries and page views. We use the collected information on the user to estimate in real time the probability of a click on a banner. A banner is displayed if it either has the highest probability of being clicked or if it is the one that generates the highest average profit.
The "psychological map of the brain", as a personal information card (file), - a project for the student of the 21st century
Venue: arXiv cs.AI 2011
Year: 2011

We suggest a procedure that is relevant both to electronic performance and human psychology, so that the creative logic and the respect for human nature appear in a good agreement. The idea is to create an electronic card containing basic information about a person's psychological behavior in order to make it possible to quickly decide about the suitability of one for another. This "psychological electronics" approach could be tested via student projects.
Clustering Protein Sequences Given the Approximation Stability of the Min-Sum Objective Function
Venue: arXiv cs.DS 2011
Year: 2011

We study the problem of efficiently clustering protein sequences in a limited information setting. We assume that we do not know the distances between the sequences in advance, and must query them during the execution of the algorithm. Our goal is to find an accurate clustering using few queries. We model the problem as a point set $S$ with an unknown metric $d$ on $S$, and assume that we have access to \emph{one versus all} distance queries that given a point $s \in S$ return the distances between $s$ and all other points. Our one versus all query represents an efficient sequence database search program such as BLAST, which compares an input sequence to an entire data set. Given a natural assumption about the approximation stability of the \emph{min-sum} objective function for clustering, we design a provably accurate clustering algorithm that uses few one versus all queries. In our empirical study we show that our method compares favorably to well-established clustering algorithms when we compare computationally derived clusterings to gold-standard manual classifications.
Series Expansion for Interference in Wireless Networks
Venue: arXiv cs.IT 2011
Year: 2011

The spatial correlations in transmitter node locations introduced by common multiple access protocols makes the analysis of interference, outage, and other related metrics in a wireless network extremely difficult. Most works therefore assume that nodes are distributed either as a Poisson point process (PPP) or a grid, and utilize the independence properties of the PPP (or the regular structure of the grid) to analyze interference, outage and other metrics. But,the independence of node locations makes the PPP a dubious model for nontrivial MACs which intentionally introduce correlations, e.g. spatial separation, while the grid is too idealized to model real networks. In this paper, we introduce a new technique based on the factorial moment expansion of functionals of point processes to analyze functions of interference, in particular outage probability. We provide a Taylor-series type expansion of functions of interference, wherein increasing the number of terms in the series provides a better approximation at the cost of increased complexity of computation. Various examples illustrate how this new approach can be used to find outage probability in both Poisson and non-Poisson wireless networks.
Relay Selection with Partial Information in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Our work is motivated by geographical forwarding of sporadic alarm packets to a base station in a wireless sensor network (WSN), where the nodes are sleep-wake cycling periodically and asynchronously. When a node (referred to as the source) gets a packet to forward, either by detecting an event or from an upstream node, it has to wait for its neighbors in a forwarding set (referred to as relays) to wake-up. Each of the relays is associated with a random reward (e.g., the progress made towards the sink) that is iid. To begin with, the source is uncertain about the number of relays, their wake-up times and the reward values, but knows their distributions. At each relay wake-up instant, when a relay reveals its reward value, the source's problem is to forward the packet or to wait for further relays to wake-up. In this setting, we seek to minimize the expected waiting time at the source subject to a lower bound on the average reward. In terms of the operations research literature, our work can be considered as a variant of the asset selling problem. We formulate the relay selection problem as a partially observable Markov decision process (POMDP), where the unknown state is the number of relays. We begin by considering the case where the source knows the number of relays. For the general case, where the source only knows a pmf on the number of relays, it has to maintain a posterior pmf on the number of relays and forward the packet iff the pmf is in an optimum stopping set. We show that the optimum stopping set is convex and obtain inner and outer bounds to this set. The computational complexity of the above policies motivates us to formulate an alternative simplified model, the optimal policy for which is a simple threshold rule. We provide simulation results to compare the performance of the various one-hop and end-to-end forwarding policies.
Selection of network coding nodes for minimal playback delay in streaming overlays
Venue: arXiv cs.MM 2011
Year: 2011

Network coding permits to deploy distributed packet delivery algorithms that locally adapt to the network availability in media streaming applications. However, it may also increase delay and computational complexity if it is not implemented efficiently. We address here the effective placement of nodes that implement randomized network coding in overlay networks, so that the goodput is kept high while the delay for decoding stays small in streaming applications. We first estimate the decoding delay at each client, which depends on the innovative rate in the network. This estimation permits to identify the nodes that have to perform coding for a reduced decoding delay. We then propose two iterative algorithms for selecting the nodes that should perform network coding. The first algorithm relies on the knowledge of the full network statistics. The second algorithm uses only local network statistics at each node. Simulation results show that large performance gains can be achieved with the selection of only a few network coding nodes. Moreover, the second algorithm performs very closely to the central estimation strategy, which demonstrates that the network coding nodes can be selected efficiently in a distributed manner. Our scheme shows large gains in terms of achieved throughput, delay and video quality in realistic overlay networks when compared to methods that employ traditional streaming strategies as well as random network nodes selection algorithms.
Languages of Dot-depth One over Infinite Words
Venue: arXiv cs.FL 2011
Year: 2011

Over finite words, languages of dot-depth one are expressively complete for alternation-free first-order logic. This fragment is also known as the Boolean closure of existential first-order logic. Here, the atomic formulas comprise order, successor, minimum, and maximum predicates. Knast (1983) has shown that it is decidable whether a language has dot-depth one. We extend Knast's result to infinite words. In particular, we describe the class of languages definable in alternation-free first-order logic over infinite words, and we give an effective characterization of this fragment. This characterization has two components. The first component is identical to Knast's algebraic property for finite words and the second component is a topological property, namely being a Boolean combination of Cantor sets. As an intermediate step we consider finite and infinite words simultaneously. We then obtain the results for infinite words as well as for finite words as special cases. In particular, we give a new proof of Knast's Theorem on languages of dot-depth one over finite words.
Relating coalgebraic notions of bisimulation
Venue: arXiv cs.LO 2011
Year: 2011

The theory of coalgebras, for an endofunctor on a category, has been proposed as a general theory of transition systems. We investigate and relate four generalizations of bisimulation to this setting, providing conditions under which the four different generalizations coincide. We study transfinite sequences whose limits are the greatest bisimulations.
Online Verification of Control Parameter Calculations in Communication Based Train Control System
Venue: arXiv cs.SE 2011
Year: 2011

Communication Based Train Control (CBTC) system is the state-of-the-art train control system. In a CBTC system, to guarantee the safety of train operation, trains communicate with each other intensively and adjust their control modes autonomously by computing critical control parameters, e.g. velocity range, according to the information they get. As the correctness of the control parameters generated are critical to the safety of the system, a method to verify these parameters is a strong desire in the area of train control system. In this paper, we present our ideas of how to model and verify the control parameter calculations in a CBTC system efficiently. - As the behavior of the system is highly nondeterministic, it is difficult to build and verify the complete behavior space model of the system online in advance. Thus, we propose to model the system according to the ongoing behavior model induced by the control parameters. - As the parameters are generated online and updated very quickly, the verification result will be meaningless if it is given beyond the time bound, since by that time the model will be changed already. Thus, we propose a method to verify the existence of certain dangerous scenarios in the model online quickly. To demonstrate the feasibility of these proposed approaches, we present the composed linear hybrid automata with readable shared variables as a modeling language to model the control parameters calculation and give a path-oriented reachability analysis technique for the scenario-based verification of this model. We demonstrate the model built for the CBTC system, and show the performance of our technique in fast online verification. Last but not least, as CBTC system is a typical CPS system, we also give a short discussion of the potential directions for CPS verification in this paper.
Diffusion framework for geometric and photometric data fusion in non-rigid shape analysis
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, we explore the use of the diffusion geometry framework for the fusion of geometric and photometric information in local and global shape descriptors. Our construction is based on the definition of a diffusion process on the shape manifold embedded into a high-dimensional space where the embedding coordinates represent the photometric information. Experimental results show that such data fusion is useful in coping with different challenges of shape analysis where pure geometric and pure photometric methods fail.
Fundamental Tradeoffs on Green Wireless Networks
Venue: arXiv cs.IT 2011
Year: 2011

Traditional design of mobile wireless networks mainly focuses on ubiquitous access and large capacity. However, as energy saving and environmental protection become a global demand and inevitable trend, wireless researchers and engineers need to shift their focus to energy-efficiency oriented design, that is, green radio. In this paper, we propose a framework for green radio research and integrate the fundamental issues that are currently scattered. The skeleton of the framework consists of four fundamental tradeoffs: deployment efficiency - energy efficiency tradeoff, spectrum efficiency - energy efficiency tradeoff, bandwidth - power tradeoff, and delay - power tradeoff. With the help of the four fundamental tradeoffs, we demonstrate that key network performance/cost indicators are all stringed together.
Order Optimal Information Spreading Using Algebraic Gossip
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate $k$ distinct messages to all $n$ nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of $O((k+\log n + D)Δ)$ rounds with high probability, where $D$ and $Δ$ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of $k$ this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is \emph{order optimal} and the stopping time is $Θ(k + D)$. To eliminate the factor of $Δ$ from the upper bound we propose a non-uniform gossip protocol, TAG, which is based on algebraic gossip and an arbitrary spanning tree protocol $§$. The stopping time of TAG is $O(k+\log n +d(§)+t(§))$, where $t(§)$ is the stopping time of the spanning tree protocol, and $d(§)$ is the diameter of the spanning tree. We provide two general cases in which this bound leads to an order optimal protocol. The first is for $k=Ω(n)$, where, using a simple gossip broadcast protocol that creates a spanning tree in at most linear time, we show that TAG finishes after $Θ(n)$ rounds for any graph. The second uses a sophisticated, recent gossip protocol to build a fast spanning tree on graphs with large weak conductance. In turn, this leads to the optimally of TAG on these graphs for $k=Ω(\mathrm{polylog}(n))$. The technique used in our proofs relies on queuing theory, which is an interesting approach that can be useful in future gossip analysis.