arXiv
(422,153 recursos)
This is one of the most extensive subject based repositories in the world in the field of physics, mathematics, astronomy, computer sciences and quantitative biology. This is the principal site with almost 20 mirror versions around the globe. The site is supported by an extensive collection of information and background documentation. An RSS feed is available for anyone interested in keeping up-to-date with newly added materials.
Mostrando recursos 41 - 60 de 9,277
41.
Inside-Outside Estimation Meets Dynamic EM - Prescher, Detlef
We briefly review the inside-outside and EM algorithm for probabilistic
context-free grammars. As a result, we formally prove that inside-outside
estimation is a dynamic-programming variant of EM. This is interesting in its
own right, but even more when considered in a theoretical context since the
well-known convergence behavior of inside-outside estimation has been confirmed
by many experiments but apparently has never been formally proved. However,
being a version of EM, inside-outside estimation also inherits the good
convergence behavior of EM. Therefore, the as yet imperfect line of
argumentation can be transformed into a coherent proof.
42.
An Analysis of the Skype Peer-to-Peer Internel Telephony Protocol - Baset, Salman A.; Schulzrinne, Henning
Skype is a peer-to-peer VoIP client developed by KaZaa in 2003. Skype claims
that it can work almost seamlessly across NATs and firewalls and has better
voice quality than the MSN and Yahoo IM applications. It encrypts calls
end-to-end, and stores user information in a decentralized fashion. Skype also
supports instant messaging and conferencing. This report analyzes key Skype
functions such as login, NAT and firewall traversal, call establishment, media
transfer, codecs, and conferencing under three different network setups.
Analysis is performed by careful study of Skype network traffic.
43.
Modeling Complex Higher Order Patterns - He, Zengyou; Xu, Xiaofei; Deng, Shengchun
The goal of this paper is to show that generalizing the notion of frequent
patterns can be useful in extending association analysis to more complex higher
order patterns. To that end, we describe a general framework for modeling a
complex pattern based on evaluating the interestingness of its sub-patterns. A
key goal of any framework is to allow people to more easily express, explore,
and communicate ideas, and hence, we illustrate how our framework can be used
to describe a variety of commonly used patterns, such as frequent patterns,
frequent closed patterns, indirect association patterns, hub patterns and
authority patterns. To further illustrate the usefulness of the framework,...
44.
A Link Clustering Based Approach for Clustering Categorical Data - He, Zengyou; Xu, Xiaofei; Deng, Shengchun
Categorical data clustering (CDC) and link clustering (LC) have been
considered as separate research and application areas. The main focus of this
paper is to investigate the commonalities between these two problems and the
uses of these commonalities for the creation of new clustering algorithms for
categorical data based on cross-fertilization between the two disjoint research
fields. More precisely, we formally transform the CDC problem into an LC
problem, and apply LC approach for clustering categorical data. Experimental
results on real datasets show that LC based clustering method is competitive
with existing CDC algorithms with respect to clustering accuracy.
45.
Towards Reliable Network Wide Broadcast in Mobile Ad Hoc Networks - Rogers, Paul; Abu-Ghazaleh, Nael
Network-Wide Broadcast (NWB) is a common operation in Mobile Ad hoc Networks
(MANETs) used by routing protocols to discover routes and in group
communication operations. NWB is commonly performed via flooding, which has
been shown to be expensive in dense MANETs because of its high redundancy.
Several efforts have targeted reducing the redundancy of floods. In this work,
we target another problem that can substantially impact the success of NWBs:
since MAC level broadcasts are unreliable, it is possible for critical
rebroadcasts to be lost, leading to a significant drop in the node coverage.
This is especially true under heavy load and in sparse topologies. We show that
the...
46.
Finite Domain Bounds Consistency Revisited - Choi, Chiu Wo; Harvey, Warwick; Lee, Jimmy Ho-Man; Stuckey, Peter J.
A widely adopted approach to solving constraint satisfaction problems
combines systematic tree search with constraint propagation for pruning the
search space. Constraint propagation is performed by propagators implementing a
certain notion of consistency. Bounds consistency is the method of choice for
building propagators for arithmetic constraints and several global constraints
in the finite integer domain. However, there has been some confusion in the
definition of bounds consistency. In this paper we clarify the differences and
similarities among the three commonly used notions of bounds consistency.
47.
Minimum Dilation Stars - Eppstein, David; Wortman, Kevin A.
The dilation of a Euclidean graph is defined as the ratio of distance in the
graph divided by distance in R^d. In this paper we consider the problem of
positioning the root of a star such that the dilation of the resulting star is
minimal. We present a deterministic O(n log n)-time algorithm for evaluating
the dilation of a given star; a randomized O(n log n) expected-time algorithm
for finding an optimal center in R^d; and for the case d=2, a randomized O(n
2^(alpha(n)) log^2 n) expected-time algorithm for finding an optimal center
among the input points.
48.
Removing Propagation Redundant Constraints in Redundant Modeling - Choi, Chiu Wo; Lee, Jimmy Ho-Man; Stuckey, Peter J.
A widely adopted approach to solving constraint satisfaction problems
combines systematic tree search with various degrees of constraint propagation
for pruning the search space. One common technique to improve the execution
efficiency is to add redundant constraints, which are constraints logically
implied by others in the problem model. However, some redundant constraints are
propagation redundant and hence do not contribute additional propagation
information to the constraint solver. Redundant constraints arise naturally in
the process of redundant modeling where two models of the same problem are
connected and combined through channeling constraints. In this paper, we give
general theorems for proving propagation redundancy of one constraint with
respect to channeling constraints...
49.
A feasible algorithm for typing in Elementary Affine Logic - Baillot, Patrick; Terui, Kazushige
We give a new type inference algorithm for typing lambda-terms in Elementary
Affine Logic (EAL), which is motivated by applications to complexity and
optimal reduction. Following previous references on this topic, the variant of
EAL type system we consider (denoted EAL*) is a variant without sharing and
without polymorphism. Our algorithm improves over the ones already known in
that it offers a better complexity bound: if a simple type derivation for the
term t is given our algorithm performs EAL* type inference in polynomial time.
50.
Data-stationary Architecture to Execute Quantum Algorithms Classically - Burger, J. R.
This paper presents a data stationary architecture in which each word has an
attached address field. Address fields massively update in parallel to record
data interchanges. Words do not move until memory is read for post processing.
A sea of such cells can test large-scale quantum algorithms, although other
programming is possible.
51.
The approximability of three-valued MAX CSP - Jonsson, Peter; Klasson, Mikael; Krokhin, Andrei
In the maximum constraint satisfaction problem (Max CSP), one is given a
finite collection of (possibly weighted) constraints on overlapping sets of
variables, and the goal is to assign values from a given domain to the
variables so as to maximize the number (or the total weight, for the weighted
case) of satisfied constraints. This problem is NP-hard in general, and,
therefore, it is natural to study how restricting the allowed types of
constraints affects the approximability of the problem. It is known that every
Boolean (that is, two-valued) Max CSP problem with a finite set of allowed
constraint types is either solvable exactly in polynomial time or...
52.
Quasiconvex Programming - Eppstein, David
We define quasiconvex programming, a form of generalized linear programming
in which one seeks the point minimizing the pointwise maximum of a collection
of quasiconvex functions. We survey algorithms for solving quasiconvex programs
either numerically or via generalizations of the dual simplex method from
linear programming, and describe varied applications of this geometric
optimization technique in meshing, scientific computation, information
visualization, automated algorithm analysis, and robust statistics.
53.
On computing fixed points for generalized sandpiles - Formenti, Enrico; Masson, Benoit
We prove fixed points results for sandpiles starting with arbitrary initial
conditions. We give an effective algorithm for computing such fixed points, and
we refine it in the particular case of SPM.
54.
Monotonicity Results for Coherent MIMO Rician Channels - Hoesli, Daniel; Kim, Young-Han; Lapidoth, Amos
The dependence of the Gaussian input information rate on the line-of-sight
(LOS) matrix in multiple-input multiple-output coherent Rician fading channels
is explored. It is proved that the outage probability and the mutual
information induced by a multivariate circularly symmetric Gaussian input with
any covariance matrix are monotonic in the LOS matrix D, or more precisely,
monotonic in D'D in the sense of the Loewner partial order. Conversely, it is
also demonstrated that this ordering on the LOS matrices is a necessary
condition for the uniform monotonicity over all input covariance matrices. This
result is subsequently applied to prove the monotonicity of the isotropic
Gaussian input information rate and channel...
55.
Isomorphic Implication - Bauland, Michael; Hemaspaandra, Edith
We study the isomorphic implication problem for Boolean constraints. We show
that this is a natural analog of the subgraph isomorphism problem. We prove
that, depending on the set of constraints, this problem is in P, NP-complete,
or NP-hard, coNP-hard, and in parallel access to NP. We show how to extend the
NP-hardness and coNP-hardness to hardness for parallel access to NP for some
cases, and conjecture that this can be done in all cases.
56.
On the existence of stable models of non-stratified logic programs - Costantini, Stefania
This paper introduces a fundamental result, which is relevant for Answer Set
programming, and planning. For the first time since the definition of the
stable model semantics, the class of logic programs for which a stable model
exists is given a syntactic characterization. This condition may have a
practical importance both for defining new algorithms for checking consistency
and computing answer sets, and for improving the existing systems. The approach
of this paper is to introduce a new canonical form (to which any logic program
can be reduced to), to focus the attention on cyclic dependencies. The
technical result is then given in terms of programs in canonical...
57.
Mutual Information and Minimum Mean-square Error in Gaussian Channels - Guo, Dongning; Shamai, Shlomo; Verdu, Sergio
This paper deals with arbitrarily distributed finite-power input signals
observed through an additive Gaussian noise channel. It shows a new formula
that connects the input-output mutual information and the minimum mean-square
error (MMSE) achievable by optimal estimation of the input given the output.
That is, the derivative of the mutual information (nats) with respect to the
signal-to-noise ratio (SNR) is equal to half the MMSE, regardless of the input
statistics. This relationship holds for both scalar and vector signals, as well
as for discrete-time and continuous-time noncausal MMSE estimation. This
fundamental information-theoretic result has an unexpected consequence in
continuous-time nonlinear estimation: For any input signal with finite power,
the causal...
58.
Source Coding With Encoder Side Information - Martinian, Emin; Wornell, Gregory W.; Zamir, Ram
We introduce the idea of distortion side information, which does not directly
depend on the source but instead affects the distortion measure. We show that
such distortion side information is not only useful at the encoder, but that
under certain conditions, knowing it at only the encoder is as good as knowing
it at both encoder and decoder, and knowing it at only the decoder is useless.
Thus distortion side information is a natural complement to the signal side
information studied by Wyner and Ziv, which depends on the source but does not
involve the distortion measure. Furthermore, when both types of side
information are present, we characterize...
59.
Reductions in Distributed Computing Part II: k-Threshold Agreement Tasks - Charron-Bost, Bernadette
We extend the results of Part I by considering a new class of agreement
tasks, the so-called k-Threshold Agreement tasks (previously introduced by
Charron-Bost and Le Fessant). These tasks naturally interpolate between Atomic
Commitment and Consensus. Moreover, they constitute a valuable tool to derive
irreducibility results between Consensus tasks only. In particular, they allow
us to show that (A) for a fixed set of processes, the higher the resiliency
degree is, the harder the Consensus task is, and (B) for a fixed resiliency
degree, the smaller the set of processes is, the harder the Consensus task is.
The proofs of these results lead us to consider new...
60.
Thematic Annotation: extracting concepts out of documents - Andrews, Pierre; Rajman, Martin
Contrarily to standard approaches to topic annotation, the technique used in
this work does not centrally rely on some sort of -- possibly statistical --
keyword extraction. In fact, the proposed annotation algorithm uses a large
scale semantic database -- the EDR Electronic Dictionary -- that provides a
concept hierarchy based on hyponym and hypernym relations. This concept
hierarchy is used to generate a synthetic representation of the document by
aggregating the words present in topically homogeneous document segments into a
set of concepts best preserving the document's content.
This new extraction technique uses an unexplored approach to topic selection.
Instead of using semantic similarity measures based on...
41.
