OpenRaiser/Intern-Atlas huggingface dataset:
AROMA: Automatic Generation of Radio Maps for Localization Systems
Venue: arXiv cs.NI 2010
Year: 2010

WLAN localization has become an active research field recently. Due to the wide WLAN deployment, WLAN localization provides ubiquitous coverage and adds to the value of the wireless network by providing the location of its users without using any additional hardware. However, WLAN localization systems usually require constructing a radio map, which is a major barrier of WLAN localization systems' deployment. The radio map stores information about the signal strength from different signal strength streams at selected locations in the site of interest. Typical construction of a radio map involves measurements and calibrations making it a tedious and time-consuming operation. In this paper, we present the AROMA system that automatically constructs accurate active and passive radio maps for both device-based and device-free WLAN localization systems. AROMA has three main goals: high accuracy, low computational requirements, and minimum user overhead. To achieve high accuracy, AROMA uses 3D ray tracing enhanced with the uniform theory of diffraction (UTD) to model the electric field behavior and the human shadowing effect. AROMA also automates a number of routine tasks, such as importing building models and automatic sampling of the area of interest, to reduce the user's overhead. Finally, AROMA uses a number of optimization techniques to reduce the computational requirements. We present our system architecture and describe the details of its different components that allow AROMA to achieve its goals. We evaluate AROMA in two different testbeds. Our experiments show that the predicted signal strength differs from the measurements by a maximum average absolute error of 3.18 dBm achieving a maximum localization error of 2.44m for both the device-based and device-free cases.
On the Minimal Uncompletable Word Problem
Venue: arXiv cs.FL 2010
Year: 2010

Let S be a finite set of words over an alphabet Sigma. The set S is said to be complete if every word w over the alphabet Sigma is a factor of some element of S*, i.e. w belongs to Fact(S*). Otherwise if S is not complete, we are interested in finding bounds on the minimal length of words in Sigma* which are not elements of Fact(S*) in terms of the maximal length of words in S.
Persistence Diagrams and the Heat Equation Homotopy
Venue: arXiv cs.CG 2010
Year: 2010

Persistence homology is a tool used to measure topological features that are present in data sets and functions. Persistence pairs births and deaths of these features as we iterate through the sublevel sets of the data or function of interest. I am concerned with using persistence to characterize the difference between two functions f, g : M -> R, where M is a topological space. Furthermore, I formulate a homotopy from g to f by applying the heat equation to the difference function g-f. By stacking the persistence diagrams associated with this homotopy, we create a vineyard of curves that connect the points in the diagram for f with the points in the diagram for g. I look at the diagrams where M is a square, a sphere, a torus, and a Klein bottle. Looking at these four topologies, we notice trends (and differences) as the persistence diagrams change with respect to time.
Image Retrieval Techniques based on Image Features, A State of Art approach for CBIR
Venue: arXiv cs.MM 2010
Year: 2010

The purpose of this Paper is to describe our research on different feature extraction and matching techniques in designing a Content Based Image Retrieval (CBIR) system. Due to the enormous increase in image database sizes, as well as its vast deployment in various applications, the need for CBIR development arose. Firstly, this paper outlines a description of the primitive feature extraction techniques like, texture, colour, and shape. Once these features are extracted and used as the basis for a similarity check between images, the various matching techniques are discussed. Furthermore, the results of its performance are illustrated by a detailed example.
On the Stability of Empirical Risk Minimization in the Presence of Multiple Risk Minimizers
Venue: arXiv cs.LG 2010
Year: 2010

Recently Kutin and Niyogi investigated several notions of algorithmic stability--a property of a learning map conceptually similar to continuity--showing that training-stability is sufficient for consistency of Empirical Risk Minimization while distribution-free CV-stability is necessary and sufficient for having finite VC-dimension. This paper concerns a phase transition in the training stability of ERM, conjectured by the same authors. Kutin and Niyogi proved that ERM on finite hypothesis spaces containing a unique risk minimizer has training stability that scales exponentially with sample size, and conjectured that the existence of multiple risk minimizers prevents even super-quadratic convergence. We prove this result for the strictly weaker notion of CV-stability, positively resolving the conjecture.
Optimization with More than One Budget
Venue: arXiv cs.DS 2010
Year: 2010

A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Some classical polynomial-time optimization problems, such as spanning tree and forest, shortest path, (perfect) matching, independent set (basis) in a matroid or in the intersection of two matroids, become NP-hard even with one budget constraint. Still, for most of these problems deterministic and randomized polynomial-time approximation schemes are known. In the case of two or more budgets, typically only multi-criteria approximation schemes are available, which return slightly infeasible solutions. Not much is known however for the case of strict budget constraints: filling this gap is the main goal of this paper. We show that shortest path, perfect matching, and spanning tree (and hence matroid basis and matroid intersection basis) are inapproximable already with two budget constraints. For the remaining problems, whose set of solutions forms an independence system, we present deterministic and randomized polynomial-time approximation schemes for a constant number k of budget constraints. Our results are based on a variety of techniques: 1. We present a simple and powerful mechanism to transform multi-criteria approximation schemes into pure approximation schemes. 2. We show that points in low dimensional faces of any matroid polytope are almost integral, an interesting result on its own. This gives a deterministic approximation scheme for k-budgeted matroid independent set. 3. We present a deterministic approximation scheme for 2-budgeted matching. The backbone of this result is a purely topological property of curves in R^2.
Performance Evaluation of TCP over Mobile Ad hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

With the proliferation of mobile computing devices, the demand for continuous network connectivity regardless of physical location has spurred interest in the use of mobile ad hoc networks. Since Transmission Control Protocol (TCP) is the standard network protocol for communication in the internet, any wireless network with Internet service need to be compatible with TCP. TCP is tuned to perform well in traditional wired networks, where packet losses occur mostly because of congestion. However, TCP connections in Ad-hoc mobile networks are plagued by problems such as high bit error rates, frequent route changes, multipath routing and temporary network partitions. The throughput of TCP over such connection is not satisfactory, because TCP misinterprets the packet loss or delay as congestion and invokes congestion control and avoidance algorithm. In this research, the performance of TCP in Adhoc mobile network with high Bit Error rate (BER) and mobility is studied and investigated. Simulation model is implemented and experiments are performed using the Network Simulatior 2 (NS2).
Constructive Algorithms for Discrepancy Minimization
Venue: arXiv cs.DS 2010
Year: 2010

Given a set system (V,S), V={1,...,n} and S={S1,...,Sm}, the minimum discrepancy problem is to find a 2-coloring of V, such that each set is colored as evenly as possible. In this paper we give the first polynomial time algorithms for discrepancy minimization that achieve bounds similar to those known existentially using the so-called Entropy Method. We also give a first approximation-like result for discrepancy. The main idea in our algorithms is to produce a coloring over time by letting the color of the elements perform a random walk (with tiny increments) starting from 0 until they reach $-1$ or $+1$. At each time step the random hops for various elements are correlated using the solution to a semidefinite program, where this program is determined by the current state and the entropy method.
Medical Image Compression using Wavelet Decomposition for Prediction Method
Venue: arXiv cs.CV 2010
Year: 2010

In this paper offers a simple and lossless compression method for compression of medical images. Method is based on wavelet decomposition of the medical images followed by the correlation analysis of coefficients. The correlation analyses are the basis of prediction equation for each sub band. Predictor variable selection is performed through coefficient graphic method to avoid multicollinearity problem and to achieve high prediction accuracy and compression rate. The method is applied on MRI and CT images. Results show that the proposed approach gives a high compression rate for MRI and CT images comparing with state of the art methods.
A MAC Layer Based Defense Architecture for Reduction of Quality (RoQ) Attacks in Wireless LAN
Venue: arXiv cs.CR 2010
Year: 2010

Recently an alternative of DDoS attacks called shrew attacks or Reduction of Quality (RoQ) has been identified which is very much difficult to detect. The RoQ attacks can use source and destination IP address spoofing, and they do not have distinct periodicity, and may not filter the attack packets precisely. In this paper, we propose to design the MAC layer based defense architecture for RoQ attacks in Wireless LAN which includes the detection and response stages. The attackers are detected by checking the RTS CTS packets from the MAC layer and the corresponding attack flows are blocked or rejected. By our simulation results, we show that our proposed technique achieves reduces the attack throughput there by increasing the received bandwidth and reducing the packet loss of legitimate users.
Robust Mechanisms for Risk-Averse Sellers
Venue: arXiv cs.GT 2010
Year: 2010

The existing literature on optimal auctions focuses on optimizing the expected revenue of the seller, and is appropriate for risk-neutral sellers. In this paper, we identify good mechanisms for risk-averse sellers. As is standard in the economics literature, we model the risk-aversion of a seller by endowing the seller with a monotone concave utility function. We then seek robust mechanisms that are approximately optimal for all sellers, no matter what their levels of risk-aversion are. We have two main results for multi-unit auctions with unit-demand bidders whose valuations are drawn i.i.d. from a regular distribution. First, we identify a posted-price mechanism called the Hedge mechanism, which gives a universal constant factor approximation; we also show for the unlimited supply case that this mechanism is in a sense the best possible. Second, we show that the VCG mechanism gives a universal constant factor approximation when the number of bidders is even only a small multiple of the number of items. Along the way we point out that Myerson's characterization of the optimal mechanisms fails to extend to utility-maximization for risk-averse sellers, and establish interesting properties of regular distributions and monotone hazard rate distributions.
Aiming Perfectly in the Dark - Blind Interference Alignment through Staggered Antenna Switching
Venue: arXiv cs.IT 2010
Year: 2010

We propose a blind interference alignment scheme for the vector broadcast channel where the transmitter is equipped with M antennas and there are K receivers, each equipped with a reconfigurable antenna capable of switching among M preset modes. Without any knowledge of the channel coefficient values at the transmitters and with only mild assumptions on the channel coherence structure we show that MK/M+K-1 degrees of freedom are achievable. The key to the blind interference alignment scheme is the ability of the receivers to switch between reconfigurable antenna modes to create short term channel fluctuation patterns that are exploited by the transmitter. The achievable scheme does not require cooperation between transmit antennas and is therefore applicable to the MxK X network as well. Only finite symbol extensions are used, and no channel knowledge at the receivers is required to null the interference.
Dynamic Cognitive Process Application of Blooms Taxonomy for Complex Software Design in the Cognitive Domain
Venue: arXiv cs.SE 2010
Year: 2010

Software design in Software Engineering is a critical and dynamic cognitive process. Accurate and flawless system design will lead to fast coding and early completion of a software project. Blooms taxonomy classifies cognitive domain into six dynamic levels such as Knowledge at base level to Comprehension, Application, Analysis, Synthesis and Evaluation at the highest level in the order of increasing complexity. A case study indicated in this paper is a gira system, which is a gprs based Intranet Remote Administration which monitors and controls the intranet from a mobile device. This paper investigates from this case study that the System Design stage in Software Engineering uses all the six levels of Blooms Taxonomy. The application of the highest levels of Blooms Taxonomy such as Synthesis and Evaluation in the design of gira indicates that Software Design in Software Development Life Cycle is a complex and critical cognitive process.
PageRank: Standing on the shoulders of giants
Venue: arXiv cs.IR 2010
Year: 2010

PageRank is a Web page ranking technique that has been a fundamental ingredient in the development and success of the Google search engine. The method is still one of the many signals that Google uses to determine which pages are most important. The main idea behind PageRank is to determine the importance of a Web page in terms of the importance assigned to the pages hyperlinking to it. In fact, this thesis is not new, and has been previously successfully exploited in different contexts. We review the PageRank method and link it to some renowned previous techniques that we have found in the fields of Web information retrieval, bibliometrics, sociometry, and econometrics.
A Bisimulation-based Method for Proving the Validity of Equations in GSOS Languages
Venue: arXiv cs.LO 2010
Year: 2010

This paper presents a bisimulation-based method for establishing the soundness of equations between terms constructed using operations whose semantics is specified by rules in the GSOS format of Bloom, Istrail and Meyer. The method is inspired by de Simone's FH-bisimilarity and uses transition rules as schematic transitions in a bisimulation-like relation between open terms. The soundness of the method is proven and examples showing its applicability are provided. The proposed bisimulation-based proof method is incomplete, but the article offers some completeness results for restricted classes of GSOS specifications.
Causality in the Semantics of Esterel: Revisited
Venue: arXiv cs.LO 2010
Year: 2010

We re-examine the challenges concerning causality in the semantics of Esterel and show that they pertain to the known issues in the semantics of Structured Operational Semantics with negative premises. We show that the solutions offered for the semantics of SOS also provide answers to the semantic challenges of Esterel and that they satisfy the intuitive requirements set by the language designers.
Analysis of Boolean Equation Systems through Structure Graphs
Venue: arXiv cs.LO 2010
Year: 2010

We analyse the problem of solving Boolean equation systems through the use of structure graphs. The latter are obtained through an elegant set of Plotkin-style deduction rules. Our main contribution is that we show that equation systems with bisimilar structure graphs have the same solution. We show that our work conservatively extends earlier work, conducted by Keiren and Willemse, in which dependency graphs were used to analyse a subclass of Boolean equation systems, viz., equation systems in standard recursive form. We illustrate our approach by a small example, demonstrating the effect of simplifying an equation system through minimisation of its structure graph.
GPRS Video Streaming Surveillance System GVSS
Venue: arXiv cs.CR 2010
Year: 2010

Future security measures will create comfortable living environments that are embedded with a wide range of intelligent functionalities including home computing, entertainment, health care and security. These place stringent requirements on the home networking architecture which integrates various existing technologies for monitoring and control for future high security needs. This paper discusses the design and implementation of a gvss gprs Video Streaming Surveillance System system, which integrates various existing technologies for providing security for smart home environments. This system provides security for office, home and other buildings where high security is required.This allows the mobile user to track the activities from a particular location. The system will send snapshots of the video and stores them in different formats. It is also possible to display the time with the image when it was captured in the gprs enabled mobiles. This system is implemented using J2me Technology
Factorization of Non-Commutative Polynomials
Venue: arXiv cs.MS 2010
Year: 2010

We describe an algorithm for the factorization of non-commutative polynomials over a field. The first sketch of this algorithm appeared in an unpublished manuscript (literally hand written notes) by James H. Davenport more than 20 years ago. This version of the algorithm contains some improvements with respect to the original sketch. An improved version of the algorithm has been fully implemented in the Axiom computer algebra system.
The Framework for Implementing ECommerce: The Role of Bank and Telecom in Bangladesh
Venue: arXiv cs.CY 2010
Year: 2010

In this paper, we describe an effective framework for adapting electronic commerce or e-commerce services in developing countries like Bangladesh. The internet has opened up a new horizon for commerce, namely electronic commerce (e-commerce). It entails the use of the internet in the marketing, identification, payment and delivery of goods and services. At present internet facilities are available in Bangladesh. Slowly, but steadily these facilities are holding a strong position in every aspects of our life. E-commerce is one of those sectors which need more attention if we want to be a part of global business. Bangladesh is far-far away to adapt the main stream of e-commerce application. Though government is shouting to take the challenges of e-commerce, but they do not take the right step, that is why e-commerce dose not make any real contribution in our socio-economic life. Here we propose a model which may develop the e-commerce infrastructure of Bangladesh.
Spectral properties of the Google matrix of the World Wide Web and other directed networks
Venue: arXiv cs.IR 2010
Year: 2010

We study numerically the spectrum and eigenstate properties of the Google matrix of various examples of directed networks such as vocabulary networks of dictionaries and university World Wide Web networks. The spectra have gapless structure in the vicinity of the maximal eigenvalue for Google damping parameter $α$ equal to unity. The vocabulary networks have relatively homogeneous spectral density, while university networks have pronounced spectral structures which change from one university to another, reflecting specific properties of the networks. We also determine specific properties of eigenstates of the Google matrix, including the PageRank. The fidelity of the PageRank is proposed as a new characterization of its stability.
Algèbres de réalisabilité: un programme pour bien ordonner R
Venue: arXiv cs.LO 2010
Year: 2010

We give a method to transform into programs, classical proofs using a well ordering of the reals. The technics uses a generalization of Cohen's forcing and the theory of classical realizability introduced by the author.
On the complexity of stratified logics
Venue: arXiv cs.CC 2010
Year: 2010

Our primary motivation is the comparison of two different traditions used in ICC to characterize the class FPTIME of the polynomial time computable functions. On one side, FPTIME can be captured by Intuitionistic Light Affine Logic (ILAL), a logic derived from Linear Logic, characterized by the structural invariant Stratification. On the other side, FPTIME can be captured by Safe Recursion on Notation (SRN), an algebra of functions based on Predicative Recursion, a restriction of the standard recursion schema used to defiine primitive recursive functions. Stratifiication and Predicative Recursion seem to share common underlying principles, whose study is the main subject of this work.
General Hardness Amplification of Predicates and Puzzles
Venue: arXiv cs.CR 2010
Year: 2010

We give new proofs for the hardness amplification of efficiently samplable predicates and of weakly verifiable puzzles which generalize to new settings. More concretely, in the first part of the paper, we give a new proof of Yao's XOR-Lemma that additionally applies to related theorems in the cryptographic setting. Our proof seems simpler than previous ones, yet immediately generalizes to statements similar in spirit such as the extraction lemma used to obtain pseudo-random generators from one-way functions [Hastad, Impagliazzo, Levin, Luby, SIAM J. on Comp. 1999]. In the second part of the paper, we give a new proof of hardness amplification for weakly verifiable puzzles, which is more general than previous ones in that it gives the right bound even for an arbitrary monotone function applied to the checking circuit of the underlying puzzle. Both our proofs are applicable in many settings of interactive cryptographic protocols because they satisfy a property that we call "non-rewinding". In particular, we show that any weak cryptographic protocol whose security is given by the unpredictability of single bits can be strengthened with a natural information theoretic protocol. As an example, we show how these theorems solve the main open question from [Halevi and Rabin, TCC2008] concerning bit commitment.
A PCP Characterization of AM
Venue: arXiv cs.CC 2010
Year: 2010

We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class AM. This gives a `PCP characterization' of AM analogous to the PCP Theorem for NP. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, and for PSPACE; however, we suggest that the result for AM might be of particular significance for attempts to derandomize this class. To test this notion, we pose some `Randomized Optimization Hypotheses' related to our stochastic CSPs that (in light of our result) would imply collapse results for AM. Unfortunately, the hypotheses appear over-strong, and we present evidence against them. In the process we show that, if some language in NP is hard-on-average against circuits of size 2^{Omega(n)}, then there exist hard-on-average optimization problems of a particularly elegant form. All our proofs use a powerful form of PCPs known as Probabilistically Checkable Proofs of Proximity, and demonstrate their versatility. We also use known results on randomness-efficient soundness- and hardness-amplification. In particular, we make essential use of the Impagliazzo-Wigderson generator; our analysis relies on a recent Chernoff-type theorem for expander walks.