OpenRaiser/Intern-Atlas huggingface dataset:
Performance Bounds on Sparse Representations Using Redundant Frames
Venue: arXiv cs.IT 2007
Year: 2007

We consider approximations of signals by the elements of a frame in a complex vector space of dimension $N$ and formulate both the noiseless and the noisy sparse representation problems. The noiseless representation problem is to find sparse representations of a signal $\mathbf{r}$ given that such representations exist. In this case, we explicitly construct a frame, referred to as the Vandermonde frame, for which the noiseless sparse representation problem can be solved uniquely using $O(N^2)$ operations, as long as the number of non-zero coefficients in the sparse representation of $\mathbf{r}$ is $εN$ for some $0 \le ε\le 0.5$, thus improving on a result of Candes and Tao \cite{Candes-Tao}. We also show that $ε\le 0.5$ cannot be relaxed without violating uniqueness. The noisy sparse representation problem is to find sparse representations of a signal $\mathbf{r}$ satisfying a distortion criterion. In this case, we establish a lower bound on the trade-off between the sparsity of the representation, the underlying distortion and the redundancy of any given frame.
Optimal Power Allocation for Distributed Detection over MIMO Channels in Wireless Sensor Networks
Venue: arXiv cs.IT 2007
Year: 2007

In distributed detection systems with wireless sensor networks, the communication between sensors and a fusion center is not perfect due to interference and limited transmitter power at the sensors to combat noise at the fusion center's receiver. The problem of optimizing detection performance with such imperfect communication brings a new challenge to distributed detection. In this paper, sensors are assumed to have independent but nonidentically distributed observations, and a multi-input/multi-output (MIMO) channel model is included to account for imperfect communication between the sensors and the fusion center. The J-divergence between the distributions of the detection statistic under different hypotheses is used as a performance criterion in order to provide a tractable analysis. Optimizing the performance (in terms of the J-divergence) with individual and total transmitter power constraints on the sensors is studied, and the corresponding power allocation scheme is provided. It is interesting to see that the proposed power allocation is a tradeoff between two factors, the communication channel quality and the local decision quality. For the case with orthogonal channels under certain conditions, the power allocation can be solved by a weighted water-filling algorithm. Simulations show that, to achieve the same performance, the proposed power allocation in certain cases only consumes as little as 25 percent of the total power used by an equal power allocation scheme.
Satisfying assignments of Random Boolean CSP: Clusters and Overlaps
Venue: arXiv cs.DM 2007
Year: 2007

The distribution of overlaps of solutions of a random CSP is an indicator of the overall geometry of its solution space. For random $k$-SAT, nonrigorous methods from Statistical Physics support the validity of the ``one step replica symmetry breaking'' approach. Some of these predictions were rigorously confirmed in \cite{cond-mat/0504070/prl} \cite{cond-mat/0506053}. There it is proved that the overlap distribution of random $k$-SAT, $k\geq 9$, has discontinuous support. Furthermore, Achlioptas and Ricci-Tersenghi proved that, for random $k$-SAT, $k\geq 8$. and constraint densities close enough to the phase transition there exists an exponential number of clusters of satisfying assignments; moreover, the distance between satisfying assignments in different clusters is linear. We aim to understand the structural properties of random CSP that lead to solution clustering. To this end, we prove two results on the cluster structure of solutions for binary CSP under the random model from Molloy (STOC 2002) 1. For all constraint sets $S$ (described explicitly in Creignou and Daude (2004), Istrate (2005)) s.t. $SAT(S)$ has a sharp threshold and all $q\in (0,1]$, $q$-overlap-$SAT(S)$ has a sharp threshold (i.e. the first step of the approach in Mora et al. works in all nontrivial cases). 2. For any constraint density value $c<1$, the set of solutions of a random instance of 2-SAT form, w.h.p., a single cluster. Also, for and any $q\in (0,1]$ such an instance has w.h.p. two satisfying assignment of overlap $\sim q$. Thus, as expected from Statistical Physics predictions, the second step of the approach in Mora et al. fails for 2-SAT.
Domain Directed Dialogs for Decision Processes
Venue: arXiv cs.OH 2007
Year: 2007

The search for a standardized optimum way to communicate using natural language dialog has involved a lot of research. However, due to the diversity of communication domains, we think that this is extremely difficult to achieve and different dialogue management techniques should be applied for different situations. Our work presents the basis of a communication mechanism that supports decision processes, is based on decision trees, and minimizes the number of steps (turn-takes) in the dialogue. The initial dialog workflow is automatically generated and the user's interaction with the system can also change the decision tree and create new dialog paths with optimized cost. The decision tree represents the chronological ordering of the actions (via the parent-child relationship) and uses an object frame to represent the information state (capturing the notion of context). This paper presents our framework, the formalism for interaction and dialogue, and an evaluation of the system compared to relevant dialog planning frameworks (i.e. finite state diagrams, frame-based, information state and planning-based dialogue systems).
A New Numerical Abstract Domain Based on Difference-Bound Matrices
Venue: arXiv cs.PL 2007
Year: 2007

This paper presents a new numerical abstract domain for static analysis by abstract interpretation. This domain allows us to represent invariants of the form (x-y<=c) and (+/-x<=c), where x and y are variables values and c is an integer or real constant. Abstract elements are represented by Difference-Bound Matrices, widely used by model-checkers, but we had to design new operators to meet the needs of abstract interpretation. The result is a complete lattice of infinite height featuring widening, narrowing and common transfer functions. We focus on giving an efficient O(n2) representation and graph-based O(n3) algorithms - where n is the number of variables|and claim that this domain always performs more precisely than the well-known interval domain. To illustrate the precision/cost tradeoff of this domain, we have implemented simple abstract interpreters for toy imperative and parallel languages which allowed us to prove some non-trivial algorithms correct.
Multimodal Meaning Representation for Generic Dialogue Systems Architectures
Venue: arXiv cs.AI 2007
Year: 2007

An unified language for the communicative acts between agents is essential for the design of multi-agents architectures. Whatever the type of interaction (linguistic, multimodal, including particular aspects such as force feedback), whatever the type of application (command dialogue, request dialogue, database querying), the concepts are common and we need a generic meta-model. In order to tend towards task-independent systems, we need to clarify the modules parameterization procedures. In this paper, we focus on the characteristics of a meta-model designed to represent meaning in linguistic and multimodal applications. This meta-model is called MMIL for MultiModal Interface Language, and has first been specified in the framework of the IST MIAMM European project. What we want to test here is how relevant is MMIL for a completely different context (a different task, a different interaction type, a different linguistic domain). We detail the exploitation of MMIL in the framework of the IST OZONE European project, and we draw the conclusions on the role of MMIL in the parameterization of task-independent dialogue managers.
Comparing BB84 and Authentication-Aided Kak's Three-Stage Quantum Protocol
Venue: arXiv cs.CR 2007
Year: 2007

This paper compares the popular quantum key distribution (QKD) protocol BB84 with the more recent Kak's three-stage protocol and the latter is shown to be more secure. A theoretical representation of an authentication-aided version of Kak's three-stage protocol is provided that makes it possible to deal with the man-in-the-middle attack.
Copula Component Analysis
Venue: arXiv cs.IR 2007
Year: 2007

A framework named Copula Component Analysis (CCA) for blind source separation is proposed as a generalization of Independent Component Analysis (ICA). It differs from ICA which assumes independence of sources that the underlying components may be dependent with certain structure which is represented by Copula. By incorporating dependency structure, much accurate estimation can be made in principle in the case that the assumption of independence is invalidated. A two phrase inference method is introduced for CCA which is based on the notion of multidimensional ICA.
Generation of Efficient Codes for Realizing Boolean Functions in Nanotechnologies
Venue: arXiv cs.IT 2007
Year: 2007

We address the challenge of implementing reliable computation of Boolean functions in future nanocircuit fabrics. Such fabrics are projected to have very high defect rates. We overcome this limitation by using a combination of cheap but unreliable nanodevices and reliable but expensive CMOS devices. In our approach, defect tolerance is achieved through a novel coding of Boolean functions; specifically, we exploit the dont cares of Boolean functions encountered in multi-level Boolean logic networks for constructing better codes. We show that compared to direct application of existing coding techniques, the coding overhead in terms of extra bits can be reduced, on average by 23%, and savings can go up to 34%. We demonstrate that by incorporating efficient coding techniques more than a 40% average yield improvement is possible in case of 1% and 0.1% defect rates. With 0.1% defect density, the savings can be up to 90%.
Mathematical model of interest matchmaking in electronic social networks
Venue: arXiv cs.CY 2007
Year: 2007

The problem of matchmaking in electronic social networks is formulated as an optimization problem. In particular, a function measuring the matching degree of fields of interest of a search profile with those of an advertising profile is proposed.
The periodic domino problem is undecidable in the hyperbolic plane
Venue: arXiv cs.CG 2007
Year: 2007

In this paper, we consider the periodic tiling problem which was proved undecidable in the Euclidean plane by Yu. Gurevich and I. Koriakov in 1972. Here, we prove that the same problem for the hyperbolic plane is also undecidable.
Analysis of the 802.11e Enhanced Distributed Channel Access Function
Venue: arXiv cs.NI 2008
Year: 2008

The IEEE 802.11e standard revises the Medium Access Control (MAC) layer of the former IEEE 802.11 standard for Quality-of-Service (QoS) provision in the Wireless Local Area Networks (WLANs). The Enhanced Distributed Channel Access (EDCA) function of 802.11e defines multiple Access Categories (AC) with AC-specific Contention Window (CW) sizes, Arbitration Interframe Space (AIFS) values, and Transmit Opportunity (TXOP) limits to support MAC-level QoS and prioritization. We propose an analytical model for the EDCA function which incorporates an accurate CW, AIFS, and TXOP differentiation at any traffic load. The proposed model is also shown to capture the effect of MAC layer buffer size on the performance. Analytical and simulation results are compared to demonstrate the accuracy of the proposed approach for varying traffic loads, EDCA parameters, and MAC layer buffer space.
A study of structural properties on profiles HMMs
Venue: arXiv cs.AI 2008
Year: 2008

Motivation: Profile hidden Markov Models (pHMMs) are a popular and very useful tool in the detection of the remote homologue protein families. Unfortunately, their performance is not always satisfactory when proteins are in the 'twilight zone'. We present HMMER-STRUCT, a model construction algorithm and tool that tries to improve pHMM performance by using structural information while training pHMMs. As a first step, HMMER-STRUCT constructs a set of pHMMs. Each pHMM is constructed by weighting each residue in an aligned protein according to a specific structural property of the residue. Properties used were primary, secondary and tertiary structures, accessibility and packing. HMMER-STRUCT then prioritizes the results by voting. Results: We used the SCOP database to perform our experiments. Throughout, we apply leave-one-family-out cross-validation over protein superfamilies. First, we used the MAMMOTH-mult structural aligner to align the training set proteins. Then, we performed two sets of experiments. In a first experiment, we compared structure weighted models against standard pHMMs and against each other. In a second experiment, we compared the voting model against individual pHMMs. We compare method performance through ROC curves and through Precision/Recall curves, and assess significance through the paired two tailed t-test. Our results show significant performance improvements of all structurally weighted models over default HMMER, and a significant improvement in sensitivity of the combined models over both the original model and the structurally weighted models.
The Complexity of Weighted Boolean #CSP
Venue: arXiv cs.CC 2008
Year: 2008

This paper gives a dichotomy theorem for the complexity of computing the partition function of an instance of a weighted Boolean constraint satisfaction problem. The problem is parameterised by a finite set F of non-negative functions that may be used to assign weights to the configurations (feasible solutions) of a problem instance. Classical constraint satisfaction problems correspond to the special case of 0,1-valued functions. We show that the partition function, i.e. the sum of the weights of all configurations, can be computed in polynomial time if either (1) every function in F is of ``product type'', or (2) every function in F is ``pure affine''. For every other fixed set F, computing the partition function is FP^{#P}-complete.
Minimizing Unsatisfaction in Colourful Neighbourhoods
Venue: arXiv cs.DS 2008
Year: 2008

Colouring sparse graphs under various restrictions is a theoretical problem of significant practical relevance. Here we consider the problem of maximizing the number of different colours available at the nodes and their neighbourhoods, given a predetermined number of colours. In the analytical framework of a tree approximation, carried out at both zero and finite temperatures, solutions obtained by population dynamics give rise to estimates of the threshold connectivity for the incomplete to complete transition, which are consistent with those of existing algorithms. The nature of the transition as well as the validity of the tree approximation are investigated.
Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem
Venue: arXiv cs.CC 2008
Year: 2008

Holzer and Holzer (Discrete Applied Mathematics 144(3):345--358, 2004) proved that the Tantrix(TM) rotation puzzle problem is NP-complete. They also showed that for infinite rotation puzzles, this problem becomes undecidable. We study the counting version and the unique version of this problem. We prove that the satisfiability problem parsimoniously reduces to the Tantrix(TM) rotation puzzle problem. In particular, this reduction preserves the uniqueness of the solution, which implies that the unique Tantrix(TM) rotation puzzle problem is as hard as the unique satisfiability problem, and so is DP-complete under polynomial-time randomized reductions, where DP is the second level of the boolean hierarchy over NP.
Pricing American Options for Jump Diffusions by Iterating Optimal Stopping Problems for Diffusions
Venue: arXiv cs.CE 2008
Year: 2008

We approximate the price of the American put for jump diffusions by a sequence of functions, which are computed iteratively. This sequence converges to the price function uniformly and exponentially fast. Each element of the approximating sequence solves an optimal stopping problem for geometric Brownian motion, and can be numerically computed using the classical finite difference methods. We prove the convergence of this numerical scheme and present examples to illustrate its performance.
Optimal Constellations for the Low SNR Noncoherent MIMO Block Rayleigh Fading Channel
Venue: arXiv cs.IT 2008
Year: 2008

Reliable communication over the discrete-input/continuous-output noncoherent multiple-input multiple-output (MIMO) Rayleigh block fading channel is considered when the signal-to-noise ratio (SNR) per degree of freedom is low. Two key problems are posed and solved to obtain the optimum discrete input. In both problems, the average and peak power per space-time slot of the input constellation are constrained. In the first one, the peak power to average power ratio (PPAPR) of the input constellation is held fixed, while in the second problem, the peak power is fixed independently of the average power. In the first PPAPR-constrained problem, the mutual information, which grows as O(SNR^2), is maximized up to second order in SNR. In the second peak-constrained problem, where the mutual information behaves as O(SNR), the structure of constellations that are optimal up to first order, or equivalently, that minimize energy/bit, are explicitly characterized. Furthermore, among constellations that are first-order optimal, those that maximize the mutual information up to second order, or equivalently, the wideband slope, are characterized. In both PPAPR-constrained and peak-constrained problems, the optimal constellations are obtained in closed-form as solutions to non-convex optimizations, and interestingly, they are found to be identical. Due to its special structure, the common solution is referred to as Space Time Orthogonal Rank one Modulation, or STORM. In both problems, it is seen that STORM provides a sharp characterization of the behavior of noncoherent MIMO capacity.
Minimum Sum Edge Colorings of Multicycles
Venue: arXiv cs.DM 2008
Year: 2008

In the minimum sum edge coloring problem, we aim to assign natural numbers to edges of a graph, so that adjacent edges receive different numbers, and the sum of the numbers assigned to the edges is minimum. The {\em chromatic edge strength} of a graph is the minimum number of colors required in a minimum sum edge coloring of this graph. We study the case of multicycles, defined as cycles with parallel edges, and give a closed-form expression for the chromatic edge strength of a multicycle, thereby extending a theorem due to Berge. It is shown that the minimum sum can be achieved with a number of colors equal to the chromatic index. We also propose simple algorithms for finding a minimum sum edge coloring of a multicycle. Finally, these results are generalized to a large family of minimum cost coloring problems.
Fractional Power Control for Decentralized Wireless Networks
Venue: arXiv cs.IT 2008
Year: 2008

We consider a new approach to power control in decentralized wireless networks, termed fractional power control (FPC). Transmission power is chosen as the current channel quality raised to an exponent -s, where s is a constant between 0 and 1. The choices s = 1 and s = 0 correspond to the familiar cases of channel inversion and constant power transmission, respectively. Choosing s in (0,1) allows all intermediate policies between these two extremes to be evaluated, and we see that usually neither extreme is ideal. We derive closed-form approximations for the outage probability relative to a target SINR in a decentralized (ad hoc or unlicensed) network as well as for the resulting transmission capacity, which is the number of users/m^2 that can achieve this SINR on average. Using these approximations, which are quite accurate over typical system parameter values, we prove that using an exponent of 1/2 minimizes the outage probability, meaning that the inverse square root of the channel strength is a sensible transmit power scaling for networks with a relatively low density of interferers. We also show numerically that this choice of s is robust to a wide range of variations in the network parameters. Intuitively, s=1/2 balances between helping disadvantaged users while making sure they do not flood the network with interference.
Are there Hilbert-style Pure Type Systems?
Venue: arXiv cs.LO 2008
Year: 2008

For many a natural deduction style logic there is a Hilbert-style logic that is equivalent to it in that it has the same theorems (i.e. valid judgements with empty contexts). For intuitionistic logic, the axioms of the equivalent Hilbert-style logic can be propositions which are also known as the types of the combinators I, K and S. Hilbert-style versions of illative combinatory logic have formulations with axioms that are actual type statements for I, K and S. As pure type systems (PTSs)are, in a sense, equivalent to systems of illative combinatory logic, it might be thought that Hilbert-style PTSs (HPTSs) could be based in a similar way. This paper shows that some PTSs have very trivial equivalent HPTSs, with only the axioms as theorems and that for many PTSs no equivalent HPTS can exist. Most commonly used PTSs belong to these two classes. For some PTSs however, including lambda* and the PTS at the basis of the proof assistant Coq, there is a nontrivial equivalent HPTS, with axioms that are type statements for I, K and S.
Pricing Asian Options for Jump Diffusions
Venue: arXiv cs.CE 2008
Year: 2008

We construct a sequence of functions that uniformly converge (on compact sets) to the price of Asian option, which is written on a stock whose dynamics follows a jump diffusion, exponentially fast. Each of the element in this sequence solves a parabolic partial differen- tial equation (not an integro-differential equation). As a result we obtain a fast numerical approximation scheme whose accuracy versus speed characteristics can be controlled. We analyze the performance of our numerical algorithm on several examples.
Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
Venue: arXiv cs.IT 2008
Year: 2008

A framework to analyze inference performance in densely connected single-layer feed-forward networks is developed for situations where a given data set is composed of correlated patterns. The framework is based on the assumption that the left and right singular value bases of the given pattern matrix are generated independently and uniformly from Haar measures. This assumption makes it possible to characterize the objective system by a single function of two variables which is determined by the eigenvalue spectrum of the cross-correlation matrix of the pattern matrix. Links to existing methods for analysis of perceptron learning and Gaussian linear vector channels and an application to a simple but nontrivial problem are also shown.