Instrukcja korzystania z Biblioteki

### Serwisy:

Ukryty Internet | Wyszukiwarki specjalistyczne tekstów i źródeł naukowych | Translatory online | Encyklopedie i słowniki online

### Translator:

Kosmos
Astronomia Astrofizyka
Inne

Kultura
Sztuka dawna i współczesna, muzea i kolekcje

Metoda
Metodologia nauk, Matematyka, Filozofia, Miary i wagi, Pomiary

Materia
Substancje, reakcje, energia
Fizyka, chemia i inżynieria materiałowa

Człowiek
Antropologia kulturowa Socjologia Psychologia Zdrowie i medycyna

Wizje
Przewidywania Kosmologia Religie Ideologia Polityka

Ziemia
Geologia, geofizyka, geochemia, środowisko przyrodnicze

Życie
Biologia, biologia molekularna i genetyka

Cyberprzestrzeń
Technologia cyberprzestrzeni, cyberkultura, media i komunikacja

Działalność
Wiadomości | Gospodarka, biznes, zarządzanie, ekonomia

Technologie
Budownictwo, energetyka, transport, wytwarzanie, technologie informacyjne

# Referaty z Computer Science na arXiv.org

## The Sample Complexity of Randomized Methods for Analysis and Design of Uncertain Systems. (arXiv:1304.0678v1 [cs.SY])

In this paper, we study the sample complexity of probabilistic methods for
uncertain systems. In particular, we show the role of the binomial distribution
for some problems involving analysis and design of robust controllers with
finite families. We also address the particular case in which the design
problem can be formulated as an uncertain convex optimization problem. The
second main contribution of the paper is to study a general class of sequential
algorithms which satisfy the required specifications using probabilistic
validation methods and, at each iteration of the sequential algorithm, a
candidate solution is probabilistically validated. The results of the paper
provide the sample complexity which guarantees that the obtained solutions meet
some pre-specified probabilistic specifications.

2013/04/03 - 15:11

## Homotopy limits in Coq. (arXiv:1304.0680v1 [math.LO])

Working in Homotopy Type Theory, we provide a systematic study of basic
homotopy limits and related constructions. The entire development has been
formally verified in the Coq interactive proof assistant.

2013/04/03 - 15:11

## Concurrent and Accurate RNA Sequencing on Multicore Platforms. (arXiv:1304.0681v1 [q-bio.GN])

In this paper we introduce a novel parallel pipeline for fast and accurate
mapping of RNA sequences on servers equipped with multicore processors. Our
software, named HPG-Aligner, leverages the speed of the Burrows-Wheeler
Transform to map a large number of RNA fragments (reads) rapidly, as well as
the accuracy of the Smith-Waterman algorithm, that is employed to deal with
conflictive reads. The aligner is complemented with a careful strategy to
detect splice junctions based on the division of RNA reads into short segments
(or seeds), which are then mapped onto a number of candidate alignment
locations, providing useful information for the successful alignment of the

Experimental results on platforms with AMD and Intel multicore processors
report the remarkable parallel performance of HPG-Aligner, on short and long
RNA reads, which excels in both execution time and sensitivity to an
state-of-the-art aligner such as TopHat 2 built on top of Bowtie and Bowtie 2.

2013/04/03 - 15:11

## Sparse Signal Processing with Linear and Non-Linear Observations: A Unified Shannon Theoretic Approach. (arXiv:1304.0682v1 [cs.IT])

In this work we derive fundamental limits for many linear and non-linear
sparse signal processing models including group testing, quantized compressive
sensing, multivariate regression and observations with missing features. In
general sparse signal processing problems can be characterized in terms of the
following Markovian property. We are given a set of $N$ variables
$X_1,X_2,\ldots,X_N$, and there is an unknown subset $S \subset \{1,\,2,\,\ldots, N\}$ that are \emph{relevant} for predicting outcomes/outputs
$Y$. In other words, when $Y$ is conditioned on $\{X_k\}_{k\in S}$ it is
conditionally independent of the other variables, $\{X_k\}_{k \not \in S}$.

Our goal is to identify the set $S$ from samples of the variables $X$ and the
associated outcomes $Y$. We characterize this problem as a version of the noisy
channel coding theorem. Using asymptotic information theoretic analyses, we
describe mutual information formulas that provide sufficient and necessary
conditions on the number of samples required to successfully recover the
salient variables. This mutual information expression unifies conditions for
both linear and non-linear observations. We then compute sample complexity
bounds based on the mutual information expressions for different settings
including group testing, quantized compressive sensing, multivariate regression
and observations with missing features.

2013/04/03 - 15:11

## Represent MOD function by low degree polynomial with unbounded one-sided error. (arXiv:1304.0713v1 [cs.CC])

In this paper, we prove tight lower bounds on the smallest degree of a
nonzero polynomial in the ideal generated by $MOD_q$ or $\neg MOD_q$ in the
polynomial ring $F_p[x_1, \ldots, x_n]/(x_1^2 = x_1, \ldots, x_n^2 = x_n)$,
$p,q$ are coprime, which is called \emph{immunity} over $F_p$. The immunity of
$MOD_q$ is lower bounded by $\lfloor (n+1)/2 \rfloor$, which is achievable when
$n$ is a multiple of $2q$; the immunity of $\neg MOD_q$ is exactly $\lfloor (n+q-1)/q \rfloor$ for every $q$ and $n$. Our result improves the previous
bound $\lfloor \frac{n}{2(q-1)} \rfloor$ by Green.

We observe how immunity over $F_p$ is related to $\acc$ circuit lower bound.
For example, if the immunity of $f$ over $F_p$ is lower bounded by $n/2 - o(\sqrt{n})$, and $|1_f| = \Omega(2^n)$, then $f$ requires $\acc$ circuit of
exponential size to compute.

2013/04/03 - 15:11

## A cookbook of translating English to Xapi. (arXiv:1304.0715v1 [cs.AI])

The Xapagy cognitive architecture had been designed to perform narrative
reasoning: to model and mimic the activities performed by humans when
communicates with the outside world using Xapi, a simplified, "pidgin" language
which is strongly tied to the internal representation model (instances, scenes
While not fully a semantic equivalent of natural language, Xapi can represent a
wide range of complex stories. We illustrate the representation technique used
in Xapi through examples taken from folk physics, folk psychology as well as
some more unusual literary examples. We argue that while the Xapi model
represents a conceptual shift from the English representation, the mapping is
logical and consistent, and a trained knowledge engineer can translate between
English and Xapi at near-native speed.

2013/04/03 - 15:11

## Evolution to 200G Passive Optical Network. (arXiv:1304.0722v1 [cs.NI])

New generation passive optical network aims at providing more than 100 Gb/s
capacity. Thanks to recent progress enabling a variety of optical transceivers
up to 40 Gb/s, many evolution possibilities to 200G PONs (passive optical
network) could be investigated. This work proposes two directly deployable
cases of evolution to 200G PON based on the combination of these improved
optical transceivers and WDM (wavelength division multiplexing). The physical
layer of the optical network has been simulated with OptiSystem software to
show the communication links performances behavior when considering key
components parameters in order to achieve good network design for a given area.
The complexity of the proposed architectures and financial cost comparisons are
also discussed.

2013/04/03 - 15:11

## Improved Performance of Unsupervised Method by Renovated K-Means. (arXiv:1304.0725v1 [cs.LG])

Clustering is a separation of data into groups of similar objects. Every
group called cluster consists of objects that are similar to one another and
dissimilar to objects of other groups. In this paper, the K-Means algorithm is
implemented by three distance functions and to identify the optimal distance
function for clustering methods. The proposed K-Means algorithm is compared
with K-Means, Static Weighted K-Means (SWK-Means) and Dynamic Weighted K-Means
(DWK-Means) algorithm by using Davis Bouldin index, Execution Time and
Iteration count methods. Experimental results show that the proposed K-Means
algorithm performed better on Iris and Wine dataset when compared with other
three clustering methods.

2013/04/03 - 15:11

## Preliminary Experiments with EVA - Serious Games Virtual Fire Drill Simulator. (arXiv:1304.0726v1 [cs.CY])

Fire keeps claiming a large number of victims in building fires. Although
there are ways to minimize such events, fire drills are used to train the
building occupants for emergency situations. However, organizing and implement
these exercises is a complex task, and sometimes not sucessfull. Furthermore,
fire drills require the mobilization of some finantial resources and time, and
affect the normal functioning of the site where they occur. To overcome the
aforementioned issues, computer games have a set of features that might
overcome this problem. They offer engagement to their players, keeping them
focused, and providing training to real life situations. The game evaluate
users, providing them some feedback, making possible for the players to improve
their performance. The proposed methodology aims to study the viability of
using a game that recreates a fire drill in a 3D environment using Serious
Games. The information acquired through the player's performance is very
valuable and will be later used to implement an artificial population. A sample
of 20 subjects was selected to test the application. Preliminary results are
promising, showing that the exercise had a positive impact on users. Moreover,
the data acquired is of great important and will be later used to demonstrate
the possibility of creating an artificial population based on human behaviour.

2013/04/03 - 15:11

## Hubs and Authorities of the English Premier League for 2010-2011. (arXiv:1304.0727v1 [cs.OH])

In this work author applies well known web search algorithm Hyperlink -
Induced Topic Search (HITS) to problem of ranking football teams in English
Premier League (EPL). The algorithm allows the ranking of the teams using the
notions of hubs and authorities well known for ranking pages in the World Wide
Web. Results of the games introduced as a graph where losing team 'gives a
link' to a winning team and, if draw registered both team give links to each
other. In case of a win link is weighted as three points in adjacent matrix and
in case of draw as one point. Author uses notion of authority in order to
define team which win a game and hub as a team which lose a game, the winner of
the competition defined as the 'worst' hub, team that didn't reinforced any
other team. Using this ranking system, the champion's team, which is a 'worst
hub' must not lose, or draw games to other 'good authorities' teams. If by the
end of the competition there are teams with an equal number of wins and losses
then the team which has beaten more teams with higher authority ranks, wins.

2013/04/03 - 15:11

## Strong immersions and maximum degree. (arXiv:1304.0728v1 [math.CO])

A graph H is strongly immersed in G if G is obtained from H by a sequence of
vertex splittings (i.e., lifting some pairs of incident edges and removing the
vertex) and edge removals. Equivalently, vertices of H are mapped to distinct
vertices of G (branch vertices) and edges of H are mapped to pairwise
edge-disjoint paths in G, each of them joining the branch vertices
corresponding to the ends of the edge and not containing any other branch
vertices. We show that there exists a function d:N->N such that for all graphs
H and G, if G contains a strong immersion of the star K_{1,d(Delta(H))|V(H)|}
whose branch vertices are Delta(H)-edge-connected to one another, then H is
strongly immersed in G. This has a number of structural consequences for graphs
avoiding a strong immersion of H. In particular, a class C of simple
4-edge-connected graphs contains all graphs of maximum degree 4 as strong
immersions if and only if C has either unbounded maximum degree or unbounded
tree-width.

2013/04/03 - 15:11

## Closed-Form Rate Outage Probability for OFDMA Multi-Hop Broadband Wireless Networks under Nakagami-m Channels. (arXiv:1304.0729v1 [cs.NI])

Rate outage probability is an important performance metric to measure the
level of quality of service (QoS) in the 4th Generation (4G) broadband access
networks. Thus, in this paper, we calculate a closed form expression of the
rate outage probability for a given user in a down-link multi-hop OFDMA-based
system encountered as a result of links channel variations. The channel random
behavior on different subcarriers allocated to a given user is assumed to
follow independent non-identical Nakagami-m distributions. Besides the rate
outage probability formulas for single hop and multi-hop networks, we also
derive a novel closed form formulas for the moment generating function,
probability distribution function (pdf), and the cumulative distribution
function (cdf) of a product of independent non-identical Gamma distributed
random variables (RVs). These RVs are functions of the attainable
signal-to-noise power ratio (SNR) on the allocated group of subcarriers. For
single-hop scenario, inspired by the rate outage probability closed formula, we
formulate an optimization problem in which we allocate subcarriers to users
such that the total transmission rate is maximized while catering for fairness
for all users. In the proposed formulation, fairness is considered by
guaranteeing a minimum rate outage probability for each admitted user

2013/04/03 - 15:11

## Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. (arXiv:1304.0730v1 [cs.LG])

We study the complexity of approximate representation and learning of
submodular functions over the uniform distribution on the Boolean hypercube
$\{0,1\}^n$. Our main result is the following structural theorem: any
submodular function is $\epsilon$-close in $\ell_2$ to a real-valued decision
tree (DT) of depth $O(1/\epsilon^2)$. This immediately implies that any
submodular function is $\epsilon$-close to a function of at most
$2^{O(1/\epsilon^2)}$ variables and has a spectral $\ell_1$ norm of
$2^{O(1/\epsilon^2)}$. It also implies the closest previous result that states
that submodular functions can be approximated by polynomials of degree
$O(1/\epsilon^2)$ (Cheraghchi et al., 2012). Our result is proved by
constructing an approximation of a submodular function by a DT of rank
$4/\epsilon^2$ and a proof that any rank-$r$ DT can be $\epsilon$-approximated
by a DT of depth $\frac{5}{2}(r+\log(1/\epsilon))$.

We show that these structural results can be exploited to give an
attribute-efficient PAC learning algorithm for submodular functions running in
time $\tilde{O}(n^2) \cdot 2^{O(1/\epsilon^{4})}$. The best previous algorithm
for the problem requires $n^{O(1/\epsilon^{2})}$ time and examples (Cheraghchi
et al., 2012) but works also in the agnostic setting. In addition, we give
improved learning algorithms for a number of related settings.

We also prove that our PAC and agnostic learning algorithms are essentially
optimal via two lower bounds: (1) an information-theoretic lower bound of
$2^{\Omega(1/\epsilon^{2/3})}$ on the complexity of learning monotone
submodular functions in any reasonable model; (2) computational lower bound of
$n^{\Omega(1/\epsilon^{2/3})}$ based on a reduction to learning of sparse
parities with noise, widely-believed to be intractable. These are the first
lower bounds for learning of submodular functions over the uniform
distribution.

2013/04/03 - 15:11

## On the Performance of Adaptive Modulation in Cognitive Radio Networks. (arXiv:1304.0732v1 [cs.NI])

We study the performance of cognitive radio networks (CRNs) when
incorporating adaptive modulation at the physical layer. Three types of CRNs
are considered, namely opportunistic spectrum access (OSA), spectrum sharing
(SS) and sensing-based SS. We obtain closed-form expressions for the average
spectral efficiency achieved at the secondary network and the optimal power
allocation for both continuous and discrete rate types of adaptive modulation
assuming perfect channel state information. The obtained numerical results show
the achievable performance gain in terms of average spectral efficiency and the
impact on power allocation when adaptive modulation is implemented at the
physical layer that is due to the effect of the cut-off level that is
determined from the received signal-to-noise ratio for each CRN type. The
performance assessment is taking place for different target bit error rate
values and fading regions, thereby providing useful performance insights for
various possible implementations.

2013/04/03 - 15:11

## On the State Complexity of the Reverse of R- and J-trivial Regular Languages. (arXiv:1304.0733v1 [cs.FL])

The tight upper bound on the state complexity of the reverse of R-trivial and
J-trivial regular languages is 2^{n-1} for languages of the state complexity n.
The witness for R-trivial regular languages is over a ternary alphabet while
for J-trivial regular languages over an (n-1)-element alphabet. In this paper,
we prove that the size of the alphabets cannot be improved, that is, the bound
can be met neither by a binary R-trivial regular language nor by a J-trivial
regular language over an (n-2)-element alphabet. We also present tight bounds
for binary R-trivial and (n-2)-element J-trivial regular languages. Tight
bounds for (n-k)-element J-trivial regular languages, for 2<= k<= n-3, are
open.

2013/04/03 - 15:11

## O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions. (arXiv:1304.0740v1 [cs.LG])

Traditional algorithms for stochastic optimization require projecting the
solution at each iteration into a given domain to ensure its feasibility. When
facing complex domains, such as positive semi-definite cones, the projection
operation can be expensive, leading to a high computational cost per iteration.
In this paper, we present a novel algorithm that aims to reduce the number of
projections for stochastic optimization. The proposed algorithm combines the
strength of several recent developments in stochastic optimization, including
explore the smoothness and strong convexity. We show, both in expectation and
with a high probability, that when the objective function is both smooth and
strongly convex, the proposed algorithm achieves the optimal $O(1/T)$ rate of
convergence with only $O(\log T)$ projections. Our empirical study verifies the
theoretical result.

2013/04/03 - 15:11

## Upper Bounds on Matching Families in $\mathbb{Z}_{pq}^n$. (arXiv:1301.0980v2 [cs.IT] UPDATED)

\textit{Matching families} are one of the major ingredients in the
construction of {\em locally decodable codes} (LDCs) and the best known
constructions of LDCs with a constant number of queries are based on matching
families. The determination of the largest size of any matching family in
$\mathbb{Z}_m^n$, where $\mathbb{Z}_m$ is the ring of integers modulo $m$, is
an interesting problem. In this paper, we show an upper bound of
$O((pq)^{0.625n+0.125})$ for the size of any matching family in
$\mathbb{Z}_{pq}^n$, where $p$ and $q$ are two distinct primes. Our bound is
valid when $n$ is a constant, $p\rightarrow \infty$ and $p/q\rightarrow 1$. Our
result improves an upper bound of Dvir {\it et al.}

2013/04/02 - 17:11

## Fixed point theorems for Boolean networks expressed in terms of forbidden subnetworks. (arXiv:1302.6346v2 [cs.DM] UPDATED)

We are interested in fixed points in Boolean networks, i.e. functions $f$
from $\{0,1\}^n$ to itself. We define the subnetworks of $f$ as the
restrictions of $f$ to the sub-cubes of $\{0,1\}^n$, and we characterizes a
class $\F$ of Boolean networks satisfying the following property: every
subnetwork of $f$ (and $f$ itself in particular) has a unique fixed point if
and only if $f$ has no subnetwork in $\F$. This characterization generalizes
the fixed point theorem of Shih and Dong, which asserts that if for every $x$
in $\{0,1\}^n$ there is no directed cycle in the directed graph whose the
adjacency matrix is the discrete Jacobian matrix of $f$ evaluated at point $x$,
then $f$ has a unique fixed point. Then, denoting by $\C^+$ (resp. $\C^-$) the
networks whose the interaction graph is a positive (resp. negative) cycle, we
show that the non-expansive networks of $\F$ are exactly the networks of
$\C^+\cup \C^-$; and for the class of non-expansive networks we get a
"dichotomization" of the previous forbidden subnetwork theorem: every
subnetwork of $f$ (and $f$ itself in particular) has at most (resp. at least)
one fixed point if and only if $f$ has no subnetworks in $\C^+$ (resp. $\C^-$)
subnetwork. Finally, we prove that if $f$ is a conjunctive network then every
subnetwork of $f$ (and $f$ itself in particular) has at most one fixed point if
and only if $f$ has no subnetworks in $\C^+$. We leave the existence of a fixed
point under the absence of subnetwork in $\C^-$ as an open for this class of
networks.

2013/04/02 - 17:11

## Polylogarithmic Cuts in Models of V^0. (arXiv:1303.6075v2 [cs.LO] UPDATED)

We study initial cuts of models of weak two-sorted Bounded Arithmetics with
respect to the strength of their theories and show that these theories are
stronger than the original one. More explicitly we will see that
polylogarithmic cuts of models of $\mathbf{V}^0$ are models of $\mathbf{VNC}^1$
by formalizing a proof of Nepomnjascij's Theorem in such cuts. This is a
strengthening of a result by Paris and Wilkie. We can then exploit our result
in Proof Complexity to observe that Frege proof systems can be sub
exponentially simulated by bounded depth Frege proof systems. This result has
recently been obtained by Filmus, Pitassi and Santhanam in a direct proof. As
an interesting observation we also obtain an average case separation of
Resolution from AC0-Frege by applying a recent result with Tzameret.

2013/04/02 - 17:11

## Scalable Text and Link Analysis with Mixed-Topic Link Models. (arXiv:1303.7264v1 [cs.LG])

Many data sets contain rich information about objects, as well as pairwise
relations between them. For instance, in networks of websites, scientific
papers, and other documents, each node has content consisting of a collection
of words, as well as hyperlinks or citations to other nodes. In order to
perform inference on such data sets, and make predictions and recommendations,
it is useful to have models that are able to capture the processes which
generate the text at each node and the links between them. In this paper, we
combine classic ideas in topic modeling with a variant of the mixed-membership
block model recently developed in the statistical physics community. The
resulting model has the advantage that its parameters, including the mixture of
topics of each document and the resulting overlapping communities, can be
inferred with a simple and scalable expectation-maximization algorithm. We test
our model on three data sets, performing unsupervised topic classification and
state-of-the-art methods, achieving higher accuracy with significantly less
computation, analyzing a data set with 1.3 million words and 44 thousand links
in a few minutes.

2013/04/01 - 19:00

is a promising technique to save cost and energy in cluster computing systems.
This paper highlights a few challenges of workload consolidation for Hadoop as
one of the current state-of-the-art data-intensive cluster computing system.
Through a systematic step-by-step procedure, we investigate challenges for
efficient server consolidation in Hadoop environments. To this end, we first
investigate the inter-relationship between last level cache (LLC) contention
server employing Hadoop distributed file system (HDFS). We then investigate the
general case of consolidation on multiple physical servers so that their
throughput never falls below a desired/predefined utilization level. We use our
empirical results to model consolidation as a classic two-dimensional bin
packing problem and then design a computationally efficient greedy algorithm to
achieve minimum throughput degradation on multiple servers. Results are very
promising and show that our greedy approach is able to achieve near optimal
solution in all experimented cases.

2013/04/01 - 19:00

## Reputation and Impact in Academic Careers. (arXiv:1303.7274v1 [physics.soc-ph])

Reputation is a key social construct in science. However, the relation
between this key signaling credential and career growth remains poorly
understood. Here we develop an original framework for measuring how citation
paths are shaped by two distinct factors - the scientific merit of each
individual paper versus the reputation of its authors within the scientific
community. To estimate the relative influence of these two factors we perform a
longitudinal analysis of publication data for 450 leading scientists from
biology, physics, and mathematics. Our panel data approach quantifies the role
of social ties, author reputation, and the citation life cycle of individual
papers. We uncover statistical regularities in the coevolution of publications
and citations, which we use as benchmarks to test and validate a stochastic
model for the citation dynamics governing a scientists publication portfolio.
We find strong evidence of increasing returns to scale in the growth of both
publications and citations, reflecting the amplifying role of social processes.
Moreover, our analysis shows that author reputation dominates in the initial
phase of a papers citation life cycle. This latter result suggests that papers
having high reputations in the scientific community. As quantitative measures
become increasingly common in the evaluation of scientific careers, our results
show that the use of measures that do not account for reputation effects may
paradoxically counteract the goal of sustaining talented and diligent young

2013/04/01 - 19:00

## On the symmetrical Kullback-Leibler Jeffreys centroids. (arXiv:1303.7286v1 [cs.IT])

Clustering histograms became an important ingredient of modern information
processing thanks to the success of the bag-of-word modeling paradigm.
Histogram clustering can be performed using the celebrated $k$-means
centroid-based algorithm. From the viewpoint of applications, it is usually
required to deal with symmetric distances. We consider the Jeffreys divergence
that symmetrizes the Kullback-Leibler divergence, and investigate the
computation of centroids with respect to that distance. We first prove that the
Jeffreys centroid can be expressed analytically in closed form using the
Lambert $W$ function for {\em positive} histograms. We then show how to obtain
a fast guaranteed tight approximation when dealing with {\em frequency}
histograms. Finally, we conclude with some remarks on the $k$-means histogram
clustering.

2013/04/01 - 19:00

## A rigorous geometry-probability equivalence in characterization of $\ell_1$-optimization. (arXiv:1303.7287v1 [cs.IT])

In this paper we consider under-determined systems of linear equations that
have sparse solutions. This subject attracted enormous amount of interest in
recent years primarily due to influential works \cite{CRT,DonohoPol}. In a
statistical context it was rigorously established for the first time in
\cite{CRT,DonohoPol} that if the number of equations is smaller than but still
linearly proportional to the number of unknowns then a sparse vector of
sparsity also linearly proportional to the number of unknowns can be recovered
through a polynomial $\ell_1$-optimization algorithm (of course, this assuming
that such a sparse solution vector exists). Moreover, the geometric approach of
\cite{DonohoPol} produced the exact values for the proportionalities in
question. In our recent work \cite{StojnicCSetam09} we introduced an
alternative statistical approach that produced attainable values of the
proportionalities. Those happened to be in an excellent numerical agreement
with the ones of \cite{DonohoPol}. In this paper we give a rigorous analytical
confirmation that the results of \cite{StojnicCSetam09} indeed match those from
\cite{DonohoPol}.

2013/04/01 - 19:00

## A Full-Diversity Beamforming Scheme in Two-Way Amplified-and-Forward Relay Systems. (arXiv:1303.7288v1 [cs.IT])

Consider a simple two-way relaying channel where two single-antenna sources
exchange information via a multiple-antenna relay. To such a scenario, all the
existing works which can achieve full diversity order are based on the
antenna/relay selection, where the difficulty to design the beamforming lies in
the fact that a single beamformer needs to serve two destinations. In this
paper, we propose a new full-diversity beamforming scheme which ensures that
the relay signals are coherently combined at both destinations. Both analytical
and numerical results are provided to demonstrate that this proposed scheme can
outperform the existing one based on the antenna selection.

2013/04/01 - 19:00

## Upper-bounding $\ell_1$-optimization weak thresholds. (arXiv:1303.7289v1 [cs.IT])

In our recent work \cite{StojnicCSetam09} we considered solving
under-determined systems of linear equations with sparse solutions. In a large
dimensional and statistical context we proved that if the number of equations
in the system is proportional to the length of the unknown vector then there is
a sparsity (number of non-zero elements of the unknown vector) also
proportional to the length of the unknown vector such that a polynomial
$\ell_1$-optimization technique succeeds in solving the system. We provided
lower bounds on the proportionality constants that are in a solid numerical
agreement with what one can observe through numerical experiments. Here we
create a mechanism that can be used to derive the upper bounds on the
proportionality constants. Moreover, the upper bounds obtained through such a
mechanism match the lower bounds from \cite{StojnicCSetam09} and ultimately
make the latter ones optimal.

2013/04/01 - 19:00

## A framework to characterize performance of LASSO algorithms. (arXiv:1303.7291v1 [cs.IT])

In this paper we consider solving \emph{noisy} under-determined systems of
linear equations with sparse solutions. A noiseless equivalent attracted
enormous attention in recent years, above all, due to work of
\cite{CRT,CanRomTao06,DonohoPol} where it was shown in a statistical and large
dimensional context that a sparse unknown vector (of sparsity proportional to
the length of the vector) can be recovered from an under-determined system via
a simple polynomial $\ell_1$-optimization algorithm. \cite{CanRomTao06} further
established that even when the equations are \emph{noisy}, one can, through an
SOCP noisy equivalent of $\ell_1$, obtain an approximate solution that is (in
an $\ell_2$-norm sense) no further than a constant times the noise from the
sparse unknown vector. In our recent works
\cite{StojnicCSetam09,StojnicUpper10}, we created a powerful mechanism that
helped us characterize exactly the performance of $\ell_1$ optimization in the
noiseless case (as shown in \cite{StojnicEquiv10} and as it must be if the
axioms of mathematics are well set, the results of
\cite{StojnicCSetam09,StojnicUpper10} are in an absolute agreement with the
corresponding exact ones from \cite{DonohoPol}). In this paper we design a
mechanism, as powerful as those from \cite{StojnicCSetam09,StojnicUpper10},
that can handle the analysis of a LASSO type of algorithm (and many others)
that can be (or typically are) used for "solving" noisy under-determined
systems. Using the mechanism we then, in a statistical context, compute the
exact worst-case $\ell_2$ norm distance between the unknown sparse vector and
the approximate one obtained through such a LASSO. The obtained results match
the corresponding exact ones obtained in \cite{BayMon10,DonMalMon10}. Moreover,
as a by-product of our analysis framework we recognize existence of an SOCP
type of algorithm that achieves the same performance.

2013/04/01 - 19:00

## Regularly random duality. (arXiv:1303.7295v1 [cs.IT])

In this paper we look at a class of random optimization problems. We discuss
ways that can help determine typical behavior of their solutions. When the
dimensions of the optimization problems are large such an information often can
be obtained without actually solving the original problems. Moreover, we also
discover that fairly often one can actually determine many quantities of
interest (such as, for example, the typical optimal values of the objective
functions) completely analytically. We present a few general ideas and
emphasize that the range of applications is enormous.

2013/04/01 - 19:00

## On Constellations for Physical Layer Network Coded Two-Way Relaying. (arXiv:1303.7296v1 [cs.IT])

Modulation schemes for two-way bidirectional relay network employing two
phases: Multiple access (MA) phase and Broadcast (BC) phase and using physical
layer network coding are currently studied intensively. Recently, adaptive
modulation schemes using Latin Squares to obtain network coding maps with the
denoise and forward protocol have been reported with good end-to-end
performance. These schemes work based on avoiding the detrimental effects of
distance shortening in the effective receive constellation at the end of the MA
phase at the relay. The channel fade states that create such distance
shortening called singular fade states, are effectively removed using
appropriate Latin squares. This scheme as well as all other known schemes
studied so far use conventional regular PSK or QAM signal sets for the end
users which lead to the relay using different sized constellations for the BC
phase depending upon the fade state. In this work, we propose a 4-point signal
set that would always require a 4-ary constellation for the BC phase for all
the channel fade conditions. We also propose an 8-point constellation that
gives better SER performance (gain of 1 dB) than 8-PSK while still using 8-ary
constellation for BC phase like the case with 8-PSK. This is in spite of the
fact that the proposed 8-point signal set has more number of singular fade
states than for 8-PSK.

2013/04/01 - 19:00

## Queuing Methodology Based Power Efficient Routing Protocol for Reliable Data Communications in Manets. (arXiv:1303.7300v1 [cs.DC])

A mobile ad hoc network (MANET) is a wireless network that uses multi-hop
peer-to- peer routing instead of static network infrastructure to provide
network connectivity. MANETs have applications in rapidly deployed and dynamic
military and civilian systems. The network topology in a MANET usually changes
with time. Therefore, there are new challenges for routing protocols in MANETs
since traditional routing protocols may not be suitable for MANETs. In recent
years, a variety of new routing protocols targeted specifically at this
environment have been developed, but little performance information on each
protocol and no realistic performance comparison between them is available.
This paper presents the results of a detailed packet-level simulation comparing
three multi-hop wireless ad hoc network routing protocols that cover a range of
design choices: DSR, NFPQR, and clustered NFPQR. By applying queuing
methodology to the introduced routing protocol the reliability and throughput
of the network is increased.

2013/04/01 - 19:00

## Exploring the Role of Logically Related Non-Question Phrases for Answering Why-Questions. (arXiv:1303.7310v1 [cs.IR])

In this paper, we show that certain phrases although not present in a given
question/query, play a very important role in answering the question. Exploring
the role of such phrases in answering questions not only reduces the dependency
on matching question phrases for extracting answers, but also improves the
quality of the extracted answers. Here matching question phrases means phrases
which co-occur in given question and candidate answers. To achieve the above
discussed goal, we introduce a bigram-based word graph model populated with
semantic and topical relatedness of terms in the given document. Next, we apply
an improved version of ranking with a prior-based approach, which ranks all
words in the candidate document with respect to a set of root words (i.e.
non-stopwords present in the question and in the candidate document). As a
result, terms logically related to the root words are scored higher than terms
that are not related to the root words. Experimental results show that our
Why-questions.

2013/04/01 - 19:00

## Proof nets and the call-by-value lambda-calculus. (arXiv:1303.7326v1 [cs.LO])

This paper gives a detailed account of the relationship between (a variant
of) the call-by-value lambda calculus and linear logic proof nets. The
presentation is carefully tuned in order to realize a strong bisimulation
between the two systems: every single rewriting step on the calculus maps to a
single step on the nets, and viceversa. In this way, we obtain an algebraic
reformulation of proof nets. Moreover, we provide a simple correctness
criterion for our proof nets, which employ boxes in an unusual way.

2013/04/01 - 19:00

## Symmetries in Modal Logics. (arXiv:1303.7327v1 [cs.LO])

We generalize the notion of symmetries of propositional formulas in
conjunctive normal form to modal formulas. Our framework uses the coinductive
models and, hence, the results apply to a wide class of modal logics including,
for example, hybrid logics. Our main result shows that the symmetries of a
modal formula preserve entailment.

2013/04/01 - 19:00

## Elementary Deduction Problem for Locally Stable Theories with Normal Forms. (arXiv:1303.7328v1 [cs.LO])

We present an algorithm to decide the intruder deduction problem (IDP) for a
class of locally stable theories enriched with normal forms. Our result relies
on a new and efficient algorithm to solve a restricted case of higher-order
associative-commutative matching, obtained by combining the Distinct
Occurrences of AC- matching algorithm and a standard algorithm to solve systems
of linear Diophantine equations. A translation between natural deduction and
sequent calculus allows us to use the same approach to decide the
\emphelementary deduction problem for locally stable theories. As an
application, we model the theory of blind signatures and derive an algorithm to
decide IDP in this context, extending previous decidability results.

2013/04/01 - 19:00

## Minimal lambda-theories by ultraproducts. (arXiv:1303.7329v1 [cs.LO])

A longstanding open problem in lambda calculus is whether there exist
continuous models of the untyped lambda calculus whose theory is exactly the
least lambda-theory lambda-beta or the least sensible lambda-theory H
(generated by equating all the unsolvable terms). A related question is
whether, given a class of lambda models, there is a minimal lambda-theory
represented by it. In this paper, we give a general tool to answer positively
to this question and we apply it to a wide class of webbed models: the
i-models. The method then applies also to graph models, Krivine models,
coherent models and filter models. In particular, we build an i-model whose
theory is the set of equations satisfied in all i-models.

2013/04/01 - 19:00

## The untyped stack calculus and Bohm's theorem. (arXiv:1303.7330v1 [cs.LO])

The stack calculus is a functional language in which is in a Curry-Howard
correspondence with classical logic. It enjoys confluence but, as well as
Parigot's lambda-mu, does not admit the Bohm Theorem, typical of the
lambda-calculus. We present a simple extension of stack calculus which is for
the stack calculus what Saurin's Lambda-mu is for lambda-mu.

2013/04/01 - 19:00

## The stack calculus. (arXiv:1303.7331v1 [cs.LO])

We introduce a functional calculus with simple syntax and operational
semantics in which the calculi introduced so far in the Curry-Howard
correspondence for Classical Logic can be faithfully encoded. Our calculus
enjoys confluence without any restriction. Its type system enforces strong
normalization of expressions and it is a sound and complete system for full
implicational Classical Logic. We give a very simple denotational semantics
which allows easy calculations of the interpretation of expressions.

2013/04/01 - 19:00

## A weak HOAS approach to the POPLmark Challenge. (arXiv:1303.7332v1 [cs.LO])

Capitalizing on previous encodings and formal developments about nominal
calculi and type systems, we propose a weak Higher-Order Abstract Syntax
formalization of the type language of pure System F<: within Coq, a proof
assistant based on the Calculus of Inductive Constructions.

Our encoding allows us to accomplish the proof of the transitivity property
of algorithmic subtyping, which is in fact the first of the three tasks stated
by the POPLmark Challenge, a set of problems that capture the most critical
issues in formalizing programming language metatheory.

2013/04/01 - 19:00

## Sequent Calculi for the classical fragment of Bochvar and Halld\'en's Nonsense Logics. (arXiv:1303.7333v1 [cs.LO])

In this paper sequent calculi for the classical fragment (that is, the
conjunction-disjunction-implication-negation fragment) of the nonsense logics
B3, introduced by Bochvar, and H3, introduced by Halld\'en, are presented.
These calculi are obtained by restricting in an appropriate way the application
of the rules of a sequent calculus for classical propositional logic CPL. The
nice symmetry between the provisos in the rules reveal the semantical
relationship between these logics. The Soundness and Completeness theorems for
both calculi are obtained, as well as the respective Cut elimination theorems.

2013/04/01 - 19:00

## Non determinism through type isomorphism. (arXiv:1303.7334v1 [cs.LO])

We define an equivalence relation on propositions and a proof system where
equivalent propositions have the same proofs. The system obtained this way
resembles several known non-deterministic and algebraic lambda-calculi.

2013/04/01 - 19:00