OpenRaiser/Intern-Atlas huggingface dataset:
Internal Constraints of the Trifocal Tensor
Venue: arXiv cs.CV 2011
Year: 2011

The fundamental matrix and trifocal tensor are convenient algebraic representations of the epipolar geometry of two and three view configurations, respectively. The estimation of these entities is central to most reconstruction algorithms, and a solid understanding of their properties and constraints is therefore very important. The fundamental matrix has 1 internal constraint which is well understood, whereas the trifocal tensor has 8 independent algebraic constraints. The internal tensor constraints can be represented in many ways, although there is only one minimal and sufficient set of 8 constraints known. In this paper, we derive a second set of minimal and sufficient constraints that is simpler. We also show how this can be used in a new parameterization of the trifocal tensor. We hope that this increased understanding of the internal constraints may lead to improved algorithms for estimating the trifocal tensor, although the primary contribution is an improved theoretical understanding.
QCSP on partially reflexive forests
Venue: arXiv cs.CC 2011
Year: 2011

We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over partially reflexive forests. We obtain a complexity-theoretic dichotomy: QCSP(H) is either in NL or is NP-hard. The separating condition is related firstly to connectivity, and thereafter to accessibility from all vertices of H to connected reflexive subgraphs. In the case of partially reflexive paths, we give a refinement of our dichotomy: QCSP(H) is either in NL or is Pspace-complete.
Sparse Vector Distributions and Recovery from Compressed Sensing
Venue: arXiv cs.DS 2011
Year: 2011

It is well known that the performance of sparse vector recovery algorithms from compressive measurements can depend on the distribution underlying the non-zero elements of a sparse vector. However, the extent of these effects has yet to be explored, and formally presented. In this paper, I empirically investigate this dependence for seven distributions and fifteen recovery algorithms. The two morals of this work are: 1) any judgement of the recovery performance of one algorithm over that of another must be prefaced by the conditions for which this is observed to be true, including sparse vector distributions, and the criterion for exact recovery; and 2) a recovery algorithm must be selected carefully based on what distribution one expects to underlie the sensed sparse signal.
Localized Dimension Growth in Random Network Coding: A Convolutional Approach
Venue: arXiv cs.IT 2011
Year: 2011

We propose an efficient Adaptive Random Convolutional Network Coding (ARCNC) algorithm to address the issue of field size in random network coding. ARCNC operates as a convolutional code, with the coefficients of local encoding kernels chosen randomly over a small finite field. The lengths of local encoding kernels increase with time until the global encoding kernel matrices at related sink nodes all have full rank. Instead of estimating the necessary field size a priori, ARCNC operates in a small finite field. It adapts to unknown network topologies without prior knowledge, by locally incrementing the dimensionality of the convolutional code. Because convolutional codes of different constraint lengths can coexist in different portions of the network, reductions in decoding delay and memory overheads can be achieved with ARCNC. We show through analysis that this method performs no worse than random linear network codes in general networks, and can provide significant gains in terms of average decoding delay in combination networks.
On the binary codes with parameters of triply-shortened 1-perfect codes
Venue: arXiv cs.IT 2011
Year: 2011

We study properties of binary codes with parameters close to the parameters of 1-perfect codes. An arbitrary binary $(n=2^m-3, 2^{n-m-1}, 4)$ code $C$, i.e., a code with parameters of a triply-shortened extended Hamming code, is a cell of an equitable partition of the $n$-cube into six cells. An arbitrary binary $(n=2^m-4, 2^{n-m}, 3)$ code $D$, i.e., a code with parameters of a triply-shortened Hamming code, is a cell of an equitable family (but not a partition) from six cells. As a corollary, the codes $C$ and $D$ are completely semiregular; i.e., the weight distribution of such a code depends only on the minimal and maximal codeword weights and the code parameters. Moreover, if $D$ is self-complementary, then it is completely regular. As an intermediate result, we prove, in terms of distance distributions, a general criterion for a partition of the vertices of a graph (from rather general class of graphs, including the distance-regular graphs) to be equitable. Keywords: 1-perfect code; triply-shortened 1-perfect code; equitable partition; perfect coloring; weight distribution; distance distribution
Distributed Denial of Service is a Scalability Problem
Venue: arXiv cs.NI 2011
Year: 2011

Distributed denial of service attacks are often considered a security problem. While this may be the way to view the problem with today's Internet, new network architectures attempting to address the issue should view it as a scalability problem. In addition, they need to address the problem based on a rigorous foundation.
Quantization Audio Watermarking with Optimal Scaling on Wavelet Coefficients
Venue: arXiv cs.CR 2011
Year: 2011

In recent years, discrete wavelet transform (DWT) provides an useful platform for digital information hiding and copyright protection. Many DWT-based algorithms for this aim are proposed. The performance of these algorithms is in term of signal-to-noise ratio (SNR) and bit-error-rate (BER) which are used to measure the quality and the robustness of an embedded audio. However, there is a tradeoff relationship between the embedded-audio quality and robustness. The tradeoff relationship is a signal processing problem in the wavelet domain. To solve this problem, this study presents an optimization-based scaling scheme using optimal multi-coefficients quantization in the wavelet domain. Firstly, the multi-coefficients quantization technique is rewritten as an equation with arbitrary scaling on DWT coefficients and set SNR to be a performance index. Then, a functional connecting the equation and the performance index is derived. Secondly, Lagrange Principle is used to obtain the optimal solution. Thirdly, the scaling factors of the DWT coefficients are also optimized. Moreover, the invariant feature of these optimized scaling factors is used to resist the amplitude scaling. Experimental results show that the embedded audio has high SNR and strong robustness against many attacks
Why The Results of Parallel and Serial Monte Carlo Simulations May Differ
Venue: arXiv cs.DC 2011
Year: 2011

Parallel Monte Carlo simulations often expose faults in random number generators
Separate Source-Channel Coding for Broadcasting Correlated Gaussians
Venue: arXiv cs.IT 2011
Year: 2011

The problem of broadcasting a pair of correlated Gaussian sources using optimal separate source and channel codes is studied. Considerable performance gains over previously known separate source-channel schemes are observed. Although source-channel separation yields suboptimal performance in general, it is shown that the proposed scheme is very competitive for any bandwidth compression/expansion scenarios. In particular, for a high channel SNR scenario, it can be shown to achieve optimal power-distortion tradeoff.
Gaussian Robust Classification
Venue: arXiv cs.LG 2011
Year: 2011

Supervised learning is all about the ability to generalize knowledge. Specifically, the goal of the learning is to train a classifier using training data, in such a way that it will be capable of classifying new unseen data correctly. In order to acheive this goal, it is important to carefully design the learner, so it will not overfit the training data. The later can is done usually by adding a regularization term. The statistical learning theory explains the success of this method by claiming that it restricts the complexity of the learned model. This explanation, however, is rather abstract and does not have a geometric intuition. The generalization error of a classifier may be thought of as correlated with its robustness to perturbations of the data: a classifier that copes with disturbance is expected to generalize well. Indeed, Xu et al. [2009] have shown that the SVM formulation is equivalent to a robust optimization (RO) formulation, in which an adversary displaces the training and testing points within a ball of pre-determined radius. In this work we explore a different kind of robustness, namely changing each data point with a Gaussian cloud centered at the sample. Loss is evaluated as the expectation of an underlying loss function on the cloud. This setup fits the fact that in many applications, the data is sampled along with noise. We develop an RO framework, in which the adversary chooses the covariance of the noise. In our algorithm named GURU, the tuning parameter is a spectral bound on the noise, thus it can be estimated using physical or applicative considerations. Our experiments show that this framework performs as well as SVM and even slightly better in some cases. Generalizations for Mercer kernels and for the multiclass case are presented as well. We also show that our framework may be further generalized, using the technique of convex perspective functions.
An Efficient Method Based on Genetic Algorithms to Solve Sensor Network Optimization Problem
Venue: arXiv cs.NI 2011
Year: 2011

Minimization of the number of cluster heads in a wireless sensor network is a very important problem to reduce channel contention and to improve the efficiency of the algorithm when executed at the level of cluster-heads. In this paper, we propose an efficient method based on genetic algorithms (GAs) to solve a sensor network optimization problem. Long communication distances between sensors and a sink in a sensor network can greatly drain the energy of sensors and reduce the lifetime of a network. By clustering a sensor network into a number of independent clusters using a GA, we can greatly minimize the total communication distance, thus prolonging the network lifetime. Simulation results show that our algorithm can quickly find a good solution.
PadSteg: Introducing Inter-Protocol Steganography
Venue: arXiv cs.CR 2011
Year: 2011

Hiding information in network traffic may lead to leakage of confidential information. In this paper we introduce a new steganographic system: the PadSteg (Padding Steganography). To authors' best knowledge it is the first information hiding solution which represents inter-protocol steganography i.e. usage of relation between two or more protocols from the TCP/IP stack to enable secret communication. PadSteg utilizes ARP and TCP protocols together with an Etherleak vulnerability (improper Ethernet frame padding) to facilitate secret communication for hidden groups in LANs (Local Area Networks). Basing on real network traces we confirm that PadSteg is feasible in today's networks and we estimate what steganographic bandwidth is achievable while limiting the chance of disclosure. We also point at possible countermeasures against PadSteg.
Joint Transmission and State Estimation: A Constrained Channel Coding Approach
Venue: arXiv cs.IT 2011
Year: 2011

A scenario involving a source, a channel, and a destination, where the destination is interested in {\em both} reliably reconstructing the message transmitted by the source and estimating with a fidelity criterion the state of the channel, is considered. The source knows the channel statistics, but is oblivious to the actual channel state realization. Herein it is established that a distortion constraint for channel state estimation can be reduced to an additional cost constraint on the source input distribution, in the limit of large coding block length. A newly defined capacity-distortion function thus characterizes the fundamental tradeoff between transmission rate and state estimation distortion. It is also shown that non-coherent communication coupled with channel state estimation conditioned on treating the decoded message as training symbols achieves the capacity-distortion function. Among the various examples considered, the capacity-distortion function for a memoryless Rayleigh fading channel is characterized to within 1.443 bits at high signal-to-noise ratio. The constrained channel coding approach is also extended to multiple access channels, leading to a coupled cost constraint on the input distributions for the transmitting sources.
Adaptive Single-Trial Error/Erasure Decoding of Reed-Solomon Codes
Venue: arXiv cs.IT 2011
Year: 2011

Algebraic decoding algorithms are commonly applied for the decoding of Reed-Solomon codes. Their main advantages are low computational complexity and predictable decoding capabilities. Many algorithms can be extended for correction of both errors and erasures. This enables the decoder to exploit binary quantized reliability information obtained from the transmission channel: Received symbols with high reliability are forwarded to the decoding algorithm while symbols with low reliability are erased. In this paper we investigate adaptive single-trial error/erasure decoding of Reed-Solomon codes, i.e. we derive an adaptive erasing strategy which minimizes the residual codeword error probability after decoding. Our result is applicable to any error/erasure decoding algorithm as long as its decoding capabilities can be expressed by a decoder capability function. Examples are Bounded Minimum Distance decoding with the Berlekamp-Massey- or the Sugiyama algorithms and the Guruswami-Sudan list decoder.
Image Retrieval Method Using Top-surf Descriptor
Venue: arXiv cs.CV 2011
Year: 2011

This report presents the results and details of a content-based image retrieval project using the Top-surf descriptor. The experimental results are preliminary, however, it shows the capability of deducing objects from parts of the objects or from the objects that are similar. This paper uses a dataset consisting of 1200 images of which 800 images are equally divided into 8 categories, namely airplane, beach, motorbike, forest, elephants, horses, bus and building, while the other 400 images are randomly picked from the Internet. The best results achieved are from building category.
On the Sphere Decoding Complexity of STBCs for Asymmetric MIMO Systems
Venue: arXiv cs.IT 2011
Year: 2011

In the landmark paper by Hassibi and Hochwald, it is claimed without proof that the upper triangular matrix R encountered during the sphere decoding of any linear dispersion code is full-ranked whenever the rate of the code is less than the minimum of the number of transmit and receive antennas. In this paper, we show that this claim is true only when the number of receive antennas is at least as much as the number of transmit antennas. We also show that all known families of high rate (rate greater than 1 complex symbol per channel use) multigroup ML decodable codes have rank-deficient R matrix even when the criterion on rate is satisfied, and that this rank-deficiency problem arises only in asymmetric MIMO with number of receive antennas less than the number of transmit antennas. Unlike the codes with full-rank R matrix, the average sphere decoding complexity of the STBCs whose R matrix is rank-deficient is polynomial in the constellation size. We derive the sphere decoding complexity of most of the known high rate multigroup ML decodable codes, and show that for each code, the complexity is a decreasing function of the number of receive antennas.
NCRAWL: Network Coding for Rate Adaptive Wireless Links
Venue: arXiv cs.NI 2011
Year: 2011

Intersession network coding (NC) can provide significant performance benefits via mixing packets at wireless routers; these benefits are especially pronounced when NC is applied in conjunction with intelligent link scheduling. NC however imposes certain processing operations, such as encoding, decoding, copying and storage. When not utilized carefully, all these operations can induce tremendous processing overheads in practical, wireless, multi-rate settings. Our measurements with prior NC implementations suggest that such processing operations severely degrade the router throughput, especially at high bit rates. Motivated by this, we design {\bf NCRAWL}, a Network Coding framework for Rate Adaptive Wireless Links. The design of NCRAWL facilitates low overhead NC functionalities, thereby effectively approaching the theoretically expected capacity benefits of joint NC and scheduling. We implement and evaluate NCRAWL on a wireless testbed. Our experiments demonstrate that NCRAWL meets the theoretical predicted throughput gain while requiring much less CPU processing, compared to related frameworks.
A Non-Orthogonal DF Scheme for the Single Relay Channel and the Effect of Labelling
Venue: arXiv cs.IT 2011
Year: 2011

We consider the uncoded transmission over the half-duplex single relay channel, with a single antenna at the source, relay and destination nodes, in a Rayleigh fading environment. The phase during which the relay is in reception mode is referred to as Phase 1 and the phase during which the relay is in transmission mode is referred to as Phase 2. The following two cases are considered: the Non-Orthogonal Decode and Forward (NODF) scheme, in which both the source and the relay transmit during Phase 2 and the Orthogonal Decode and Forward (ODF) scheme, in which the relay alone transmits during Phase 2. A near ML decoder which gives full diversity (diversity order 2) for the NODF scheme is proposed. Due to the proximity of the relay to the destination, the Source-Destination link, in general, is expected to be much weaker than the Relay-Destination link. Hence it is not clear whether the transmission made by the source during Phase 2 in the NODF scheme, provides any performance improvement over the ODF scheme or not. In this regard, it is shown that the NODF scheme provides significant performance improvement over the ODF scheme. In fact, at high SNR, the performance of the NODF scheme with the non-ideal Source-Relay link, is same as that of the NODF scheme with an ideal Source-Relay link. In other words, to study the high SNR performance of the NODF scheme, one can assume that the Source-Relay link is ideal, whereas the same is not true for the ODF scheme. Further, it is shown that proper choice of the mapping of the bits on to the signal points at the source and the relay, provides a significant improvement in performance, for both the NODF and the ODF schemes.
Quantifier Elimination over Finite Fields Using Gröbner Bases
Venue: arXiv cs.SC 2011
Year: 2011

We give an algebraic quantifier elimination algorithm for the first-order theory over any given finite field using Gröbner basis methods. The algorithm relies on the strong Nullstellensatz and properties of elimination ideals over finite fields. We analyze the theoretical complexity of the algorithm and show its application in the formal analysis of a biological controller model.
Enhanced stiffness modeling of manipulators with passive joints
Venue: arXiv cs.RO 2011
Year: 2011

The paper presents a methodology to enhance the stiffness analysis of serial and parallel manipulators with passive joints. It directly takes into account the loading influence on the manipulator configuration and, consequently, on its Jacobians and Hessians. The main contributions of this paper are the introduction of a non-linear stiffness model for the manipulators with passive joints, a relevant numerical technique for its linearization and computing of the Cartesian stiffness matrix which allows rank-deficiency. Within the developed technique, the manipulator elements are presented as pseudo-rigid bodies separated by multidimensional virtual springs and perfect passive joints. Simulation examples are presented that deal with parallel manipulators of the Ortholide family and demonstrate the ability of the developed methodology to describe non-linear behavior of the manipulator structure such as a sudden change of the elastic instability properties (buckling).
The Anna Karenina principle: A concept for the explanation of success in science
Venue: arXiv cs.DL 2011
Year: 2011

The first sentence of Leo Tolstoy's novel Anna Karenina is: "Happy families are all alike; every unhappy family is unhappy in its own way." Here Tolstoy means that for a family to be happy, several key aspects must be given (such as good health of all family members, acceptable financial security, and mutual affection). If there is a deficiency in any one or more of these key aspects, the family will be unhappy. In this paper we introduce the Anna Karenina principle as a concept that can explain success in science. Here we will refer to three central areas in modern science in which scarce resources will most usually lead to failure: (1) peer review of research grant proposals and manuscripts (money and journal space as scarce resources), (2) citation of publications (reception as a scarce resource), and (3) new scientific discoveries (recognition as a scarce resource). If resources are scarce (journal space, funds, reception, and recognition), there can be success only when several key prerequisites for the allocation of the resources are fulfilled. If any one of these prerequisites is not fulfilled, the grant proposal, manuscript submission, the published paper, or the discovery will not be successful.
Haptic devices and objects, robots and mannequin simulation in a CAD-CAM software: eM-Virtual Desktop
Venue: arXiv cs.RO 2011
Year: 2011

This paper presents the development of a new software in order to manage objects, robots and mannequins in using the possibilities given by the haptic feedback of the Phantom desktop devices. The haptic device provides 6 positional degrees of freedom sensing but three degrees force feedback. This software called eM-Virtual Desktop is integrated in the Tecnomatix's solution called eM-Workplace. The eM-Workplace provides powerful solutions for planning and designing of complex assembly facilities, lines and workplaces. In the digital mockup context, the haptic interfaces can be used to reduce the development cycle of products. Three different loops are used to manage the graphic, the collision detection and the haptic feedback according to theirs own frequencies. The developed software is currently tested in industrial context by a European automotive constructor.
Streaming algorithms for language recognition problems
Venue: arXiv cs.DS 2011
Year: 2011

We study the complexity of the following problems in the streaming model. Membership testing for \DLIN We show that every language in \DLIN\ can be recognised by a randomized one-pass $O(\log n)$ space algorithm with inverse polynomial one-sided error, and by a deterministic p-pass $O(n/p)$ space algorithm. We show that these algorithms are optimal. Membership testing for \LL$(k)$ For languages generated by \LL$(k)$ grammars with a bound of $r$ on the number of nonterminals at any stage in the left-most derivation, we show that membership can be tested by a randomized one-pass $O(r\log n)$ space algorithm with inverse polynomial (in $n$) one-sided error. Membership testing for \DCFL We show that randomized algorithms as efficient as the ones described above for \DLIN\ and $\LL(k)$ (which are subclasses of \DCFL) cannot exist for all of \DCFL: there is a language in \VPL\ (a subclass of \DCFL) for which any randomized p-pass algorithm with error bounded by $ε< 1/2$ must use $Ω(n/p)$ space. Degree sequence problem We study the problem of determining, given a sequence $d_1, d_2,..., d_n$ and a graph $G$, whether the degree sequence of $G$ is precisely $d_1, d_2,..., d_n$. We give a randomized one-pass $O(\log n)$ space algorithm with inverse polynomial one-sided error probability. We show that our algorithms are optimal. Our randomized algorithms are based on the recent work of Magniez et al. \cite{MMN09}; our lower bounds are obtained by considering related communication complexity problems.