OpenRaiser/Intern-Atlas huggingface dataset:
Discriminately Decreasing Discriminability with Learned Image Filters
Venue: arXiv cs.CV 2011
Year: 2011

In machine learning and computer vision, input images are often filtered to increase data discriminability. In some situations, however, one may wish to purposely decrease discriminability of one classification task (a "distractor" task), while simultaneously preserving information relevant to another (the task-of-interest): For example, it may be important to mask the identity of persons contained in face images before submitting them to a crowdsourcing site (e.g., Mechanical Turk) when labeling them for certain facial attributes. Another example is inter-dataset generalization: when training on a dataset with a particular covariance structure among multiple attributes, it may be useful to suppress one attribute while preserving another so that a trained classifier does not learn spurious correlations between attributes. In this paper we present an algorithm that finds optimal filters to give high discriminability to one task while simultaneously giving low discriminability to a distractor task. We present results showing the effectiveness of the proposed technique on both simulated data and natural face images.
Practical Wireless Network Coding and Decoding Methods for Multiple Unicast Transmissions
Venue: arXiv cs.IT 2011
Year: 2011

We propose a simple yet effective wireless network coding and decoding technique. It utilizes spatial diversity through cooperation between nodes which carry out distributed encoding operations dictated by generator matrices of linear block codes. For this purpose, we make use of greedy codes over the binary field and show that desired diversity orders can be flexibly assigned to nodes in a multiple unicast network, contrary to the previous findings in the literature. Furthermore, we present the optimal detection rule for the given model that accounts for intermediate node errors and suggest a network decoder using the sum-product algorithm. The proposed sum-product detector exhibits near optimal performance.
Directed information and Pearl's causal calculus
Venue: arXiv cs.IT 2011
Year: 2011

Probabilistic graphical models are a fundamental tool in statistics, machine learning, signal processing, and control. When such a model is defined on a directed acyclic graph (DAG), one can assign a partial ordering to the events occurring in the corresponding stochastic system. Based on the work of Judea Pearl and others, these DAG-based "causal factorizations" of joint probability measures have been used for characterization and inference of functional dependencies (causal links). This mostly expository paper focuses on several connections between Pearl's formalism (and in particular his notion of "intervention") and information-theoretic notions of causality and feedback (such as causal conditioning, directed stochastic kernels, and directed information). As an application, we show how conditional directed information can be used to develop an information-theoretic version of Pearl's "back-door" criterion for identifiability of causal effects from passive observations. This suggests that the back-door criterion can be thought of as a causal analog of statistical sufficiency.
Integral Value Transformations: A Class of Affine Discrete Dynamical Systems and an Application
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, the notion of Integral Value Transformations (IVTs), a class of Discrete Dynamical Maps has been introduced. Then notion of Affine Discrete Dynamical System (ADDS) in the light of IVTs is defined and some rudimentary mathematical properties of the system are depicted. Collatz Conjecture is one of the most enigmatic problems in 20th Century. The Conjecture was posed by German Mathematician L. Collatz in 1937. There are much advancement in generalizing and defining analogous conjectures, but even to the date, there is no fruitful result for the advancement for the settlement of the conjecture. We have made an effort to make a Collatz type problem in the domain of IVTs and we have been able to solve the problem in 2011 [1]. Here mainly, we have focused and inquired on Collatz-like ADDS. Finally, we have designed the Optimal Distributed and Parallel Environment (ODPE) in the light of ADDS.
Hierarchies of Inefficient Kernelizability
Venue: arXiv cs.CC 2011
Year: 2011

The framework of Bodlaender et al. (ICALP 2008) and Fortnow and Santhanam (STOC 2008) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-theoretical assumptions. However, there are also some issues that are not addressed by this framework, including the existence of Turing kernels such as the "kernelization" of Leaf Out Branching(k) into a disjunction over n instances of size poly(k). Observing that Turing kernels are preserved by polynomial parametric transformations, we define a kernelization hardness hierarchy, akin to the M- and W-hierarchy of ordinary parameterized complexity, by the PPT-closure of problems that seem likely to be fundamentally hard for efficient Turing kernelization. We find that several previously considered problems are complete for our fundamental hardness class, including Min Ones d-SAT(k), Binary NDTM Halting(k), Connected Vertex Cover(k), and Clique(k log n), the clique problem parameterized by k log n.
Towards a native toplevel for the OCaml language
Venue: arXiv cs.PL 2011
Year: 2011

This paper presents the current state of our work on an interactive toplevel for the OCaml language based on the optimizing native code compiler and runtime. Our native toplevel is up to 100 times faster than the default OCaml toplevel, which is based on the byte code compiler and interpreter. It uses Just-In-Time techniques to compile toplevel phrases to native code at runtime, and currently works with various Unix-like systems running on x86 or x86-64 processors.
Optimal Deadline Scheduling with Commitment
Venue: arXiv cs.DS 2011
Year: 2011

We consider an online preemptive scheduling problem where jobs with deadlines arrive sporadically. A commitment requirement is imposed such that the scheduler has to either accept or decline a job immediately upon arrival. The scheduler's decision to accept an arriving job constitutes a contract with the customer; if the accepted job is not completed by its deadline as promised, the scheduler loses the value of the corresponding job and has to pay an additional penalty depending on the amount of unfinished workload. The objective of the online scheduler is to maximize the overall profit, i.e., the total value of the admitted jobs completed before their deadlines less the penalty paid for the admitted jobs that miss their deadlines. We show that the maximum competitive ratio is $3-2\sqrt{2}$ and propose a simple online algorithm to achieve this competitive ratio. The optimal scheduling includes a threshold admission and a greedy scheduling policies. The proposed algorithm has direct applications to the charging of plug-in hybrid electrical vehicles (PHEV) at garages or parking lots.
On Joint Diagonalisation for Dynamic Network Analysis
Venue: arXiv cs.SI 2011
Year: 2011

Joint diagonalisation (JD) is a technique used to estimate an average eigenspace of a set of matrices. Whilst it has been used successfully in many areas to track the evolution of systems via their eigenvectors; its application in network analysis is novel. The key focus in this paper is the use of JD on matrices of spanning trees of a network. This is especially useful in the case of real-world contact networks in which a single underlying static graph does not exist. The average eigenspace may be used to construct a graph which represents the `average spanning tree' of the network or a representation of the most common propagation paths. We then examine the distribution of deviations from the average and find that this distribution in real-world contact networks is multi-modal; thus indicating several \emph{modes} in the underlying network. These modes are identified and are found to correspond to particular times. Thus JD may be used to decompose the behaviour, in time, of contact networks and produce average static graphs for each time. This may be viewed as a mixture between a dynamic and static graph approach to contact network analysis.
Audio Watermarking with Error Correction
Venue: arXiv cs.CR 2011
Year: 2011

In recent times, communication through the internet has tremendously facilitated the distribution of multimedia data. Although this is indubitably a boon, one of its repercussions is that it has also given impetus to the notorious issue of online music piracy. Unethical attempts can also be made to deliberately alter such copyrighted data and thus, misuse it. Copyright violation by means of unauthorized distribution, as well as unauthorized tampering of copyrighted audio data is an important technological and research issue. Audio watermarking has been proposed as a solution to tackle this issue. The main purpose of audio watermarking is to protect against possible threats to the audio data and in case of copyright violation or unauthorized tampering, authenticity of such data can be disputed by virtue of audio watermarking.
Two-Way Automata Making Choices Only at the Endmarkers
Venue: arXiv cs.FL 2011
Year: 2011

The question of the state-size cost for simulation of two-way nondeterministic automata (2NFAs) by two-way deterministic automata (2DFAs) was raised in 1978 and, despite many attempts, it is still open. Subsequently, the problem was attacked by restricting the power of 2DFAs (e.g., using a restricted input head movement) to the degree for which it was already possible to derive some exponential gaps between the weaker model and the standard 2NFAs. Here we use an opposite approach, increasing the power of 2DFAs to the degree for which it is still possible to obtain a subexponential conversion from the stronger model to the standard 2DFAs. In particular, it turns out that subexponential conversion is possible for two-way automata that make nondeterministic choices only when the input head scans one of the input tape endmarkers. However, there is no restriction on the input head movement. This implies that an exponential gap between 2NFAs and 2DFAs can be obtained only for unrestricted 2NFAs using capabilities beyond the proposed new model. As an additional bonus, conversion into a machine for the complement of the original language is polynomial in this model. The same holds for making such machines self-verifying, halting, or unambiguous. Finally, any superpolynomial lower bound for the simulation of such machines by standard 2DFAs would imply L<>NL. In the same way, the alternating version of these machines is related to L =? NL =? P, the classical computational complexity problems.
A Dual-based Method for Resource Allocation in OFDMA-SDMA Systems with Minimum Rate Constraints
Venue: arXiv cs.IT 2011
Year: 2011

We consider multi-antenna base stations using orthogonal frequency-division multiple access (OFDMA) and space division multiple access (SDMA) techniques to serve single antenna users, where some of those users have minimum rate requirements and must be served in the current time slot (real time users), while others do not have strict timing constraints (non real time users) and are served on a best effort basis. The resource allocation problem is to find the user assignment to subcarriers and the transmit beamforming vectors that maximize a linear utility function of the user rates subject to power and minimum rate constraints. The exact optimal solution to this problem can not be reasonably obtained for practical parameters values of the communication system. We thus derive a dual problem formulation whose optimal solution provides an upper bound to all feasible solutions and can be used to benchmark the performance of any heuristic method used to solve this problem. We also derive from this dual optimal solution a primal-feasible dual-based method to solve the problem and we compare its performance and computation time against a standard weight adjustment method. We find that our method follows the dual optimal bound more closely than the weight adjustment method. This off-line algorithm can serve as the basis to develop more efficient heuristic methods.
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
Venue: arXiv cs.DS 2011
Year: 2011

The densest k-subgraph (DkS) problem (i.e. find a size k subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significant gap between known upper and lower bounds for DkS: the current best algorithm gives an ~ O(n^{1/4}) approximation, while even showing a small constant factor hardness requires significantly stronger assumptions than P != NP. In addition to interest in designing better algorithms, a number of recent results have exploited the conjectured hardness of densest k-subgraph and its variants. Thus, understanding the approximability of DkS is an important challenge. In this work, we give evidence for the hardness of approximating DkS within polynomial factors. Specifically, we expose the limitations of strong semidefinite programs from SDP hierarchies in solving densest k-subgraph. Our results include: * A lower bound of Omega(n^{1/4}/log^3 n) on the integrality gap for Omega(log n/log log n) rounds of the Sherali-Adams relaxation for DkS. This also holds for the relaxation obtained from Sherali-Adams with an added SDP constraint. Our gap instances are in fact Erdos-Renyi random graphs. * For every epsilon > 0, a lower bound of n^{2/53-eps} on the integrality gap of n^{Omega(eps)} rounds of the Lasserre SDP relaxation for DkS, and an n^{Omega_eps(1)} gap for n^{1-eps} rounds. Our construction proceeds via a reduction from random instances of a certain Max-CSP over large domains. In the absence of inapproximability results for DkS, our results show that even the most powerful SDPs are unable to beat a factor of n^{Omega(1)}, and in fact even improving the best known n^{1/4} factor is a barrier for current techniques.
A Face Recognition Scheme using Wavelet Based Dominant Features
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, a multi-resolution feature extraction algorithm for face recognition is proposed based on two-dimensional discrete wavelet transform (2D-DWT), which efficiently exploits the local spatial variations in a face image. For the purpose of feature extraction, instead of considering the entire face image, an entropy-based local band selection criterion is developed, which selects high-informative horizontal segments from the face image. In order to capture the local spatial variations within these highinformative horizontal bands precisely, the horizontal band is segmented into several small spatial modules. Dominant wavelet coefficients corresponding to each local region residing inside those horizontal bands are selected as features. In the selection of the dominant coefficients, a threshold criterion is proposed, which not only drastically reduces the feature dimension but also provides high within-class compactness and high between-class separability. A principal component analysis is performed to further reduce the dimensionality of the feature space. Extensive experimentation is carried out upon standard face databases and a very high degree of recognition accuracy is achieved by the proposed method in comparison to those obtained by some of the existing methods.
Handwritten Text Image Authentication using Back Propagation
Venue: arXiv cs.CR 2011
Year: 2011

Authentication is the act of confirming the truth of an attribute of a datum or entity. This might involve confirming the identity of a person, tracing the origins of an artefact, ensuring that a product is what it's packaging and labelling claims to be, or assuring that a computer program is a trusted one. The authentication of information can pose special problems (especially man-in-the-middle attacks), and is often wrapped up with authenticating identity. Literary can involve imitating the style of a famous author. If an original manuscript, typewritten text, or recording is available, then the medium itself (or its packaging - anything from a box to e-mail headers) can help prove or disprove the authenticity of the document. The use of digital images of handwritten historical documents has become more popular in recent years. Volunteers around the world now read thousands of these images as part of their indexing process. Handwritten text images of old documents are sometimes difficult to read or noisy due to the preservation of the document and quality of the image [1]. Handwritten text offers challenges that are rarely encountered in machine-printed text. In addition, most problems faced in reading machine- printed text (e.g., character recognition, word segmentation, letter segmentation, etc.) are more severe, in handwritten text. In this paper we Here in this paper we proposed a method for authenticating hand written text images using back propagation algorithm..
Hilbert Matrix Based Cryptosystem using a Session Key
Venue: arXiv cs.CR 2011
Year: 2011

Cryptography protects users by providing functionality for the encryption of data and authentication of other users. This technology lets the receiver of an electronic message verify the sender, ensures that a message can be read only by the intended person, and assures the recipient that a message has not be altered in transit. Classical cryptanalysis involves an interesting combination of analytical reasoning, application of mathematical tools and pattern finding. The objectives of the proposed work are to propose a new cryptographic method based on the special matrix called the Hilbert matrix for authentication and confidentiality and to propose a model for confidentiality and authentication using shared key cryptosystems with the concept of digital enveloping using a session key. In the present work various algorithms are presented for encryption and authentication based on Hilbert matrix using a session key.
A Polylogarithmic-Competitive Algorithm for the k-Server Problem
Venue: arXiv cs.DS 2011
Year: 2011

We give the first polylogarithmic-competitive randomized online algorithm for the $k$-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of O(log^3 n log^2 k log log n) for any metric space on n points. Our algorithm improves upon the deterministic (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou [J.ACM'95] whenever n is sub-exponential in k.
Fault Tolerant Matrix Pencil Method for Direction of Arrival Estimation
Venue: arXiv cs.OH 2011
Year: 2011

Continuing to estimate the Direction-of-arrival (DOA) of the signals impinging on the antenna array, even when a few elements of the underlying Uniform Linear Antenna Array (ULA) fail to work will be of practical interest in RADAR, SONAR and Wireless Radio Communication Systems. This paper proposes a new technique to estimate the DOAs when a few elements are malfunctioning. The technique combines Singular Value Thresholding (SVT) based Matrix Completion (MC) procedure with the Direct Data Domain (D^3) based Matrix Pencil (MP) Method. When the element failure is observed, first, the MC is performed to recover the missing data from failed elements, and then the MP method is used to estimate the DOAs. We also, propose a very simple technique to detect the location of elements failed, which is required to perform MC procedure. We provide simulation studies to demonstrate the performance and usefulness of the proposed technique. The results indicate a better performance, of the proposed DOA estimation scheme under different antenna failure scenarios.
A Behavior-based Approach for Multi-agent Q-learning for Autonomous Exploration
Venue: arXiv cs.RO 2011
Year: 2011

The use of mobile robots is being popular over the world mainly for autonomous explorations in hazardous/ toxic or unknown environments. This exploration will be more effective and efficient if the explorations in unknown environment can be aided with the learning from past experiences. Currently reinforcement learning is getting more acceptances for implementing learning in robots from the system-environment interactions. This learning can be implemented using the concept of both single-agent and multiagent. This paper describes such a multiagent approach for implementing a type of reinforcement learning using a priority based behaviour-based architecture. This proposed methodology has been successfully tested in both indoor and outdoor environments.
Putting Instruction Sequences into Effect
Venue: arXiv cs.PL 2011
Year: 2011

An attempt is made to define the concept of execution of an instruction sequence. It is found to be a special case of directly putting into effect of an instruction sequence. Directly putting into effect of an instruction sequences comprises interpretation as well as execution. Directly putting into effect is a special case of putting into effect with other special cases classified as indirectly putting into effect.
Uncertainty in Soft Temporal Constraint Problems:A General Framework and Controllability Algorithms for the Fuzzy Case
Venue: arXiv cs.AI 2011
Year: 2011

In real-life temporal scenarios, uncertainty and preferences are often essential and coexisting aspects. We present a formalism where quantitative temporal constraints with both preferences and uncertainty can be defined. We show how three classical notions of controllability (that is, strong, weak, and dynamic), which have been developed for uncertain temporal problems, can be generalized to handle preferences as well. After defining this general framework, we focus on problems where preferences follow the fuzzy approach, and with properties that assure tractability. For such problems, we propose algorithms to check the presence of the controllability properties. In particular, we show that in such a setting dealing simultaneously with preferences and uncertainty does not increase the complexity of controllability testing. We also develop a dynamic execution algorithm, of polynomial complexity, that produces temporal plans under uncertainty that are optimal with respect to fuzzy preferences.
Optimal Power Allocation for Renewable Energy Source
Venue: arXiv cs.SY 2011
Year: 2011

Battery powered transmitters face energy constraint, replenishing their energy by a renewable energy source (like solar or wind power) can lead to longer lifetime. We consider here the problem of finding the optimal power allocation under random channel conditions for a wireless transmitter, such that rate of information transfer is maximized. Here a rechargeable battery, which is periodically charged by renewable source, is used to power the transmitter. All of above is formulated as a Markov Decision Process. Structural properties like the monotonicity of the optimal value and policy derived in this paper will be of vital importance in understanding the kind of algorithms and approximations needed in real-life scenarios. The effect of curse of dimensionality which is prevalent in Dynamic programming problems can thus be reduced. We show our results under the most general of assumptions.