OpenRaiser/Intern-Atlas huggingface dataset:
Priority Queues with Multiple Time Fingers
Venue: arXiv cs.DS 2010
Year: 2010

A priority queue is presented that supports the operations insert and find-min in worst-case constant time, and delete and delete-min on element x in worst-case O(lg(min{w_x, q_x}+2)) time, where w_x (respectively q_x) is the number of elements inserted after x (respectively before x) and are still present at the time of the deletion of x. Our priority queue then has both the working-set and the queueish properties, and more strongly it satisfies these properties in the worst-case sense. We also define a new distribution-sensitive property---the time-finger property, which encapsulates and generalizes both the working-set and queueish properties, and present a priority queue that satisfies this property. In addition, we prove a strong implication that the working-set property is equivalent to the unified bound (which is the minimum per operation among the static finger, static optimality, and the working-set bounds). This latter result is of tremendous interest by itself as it had gone unnoticed since the introduction of such bounds by Sleater and Tarjan [JACM 1985]. Accordingly, our priority queue satisfies other distribution-sensitive properties as the static finger, static optimality, and the unified bound.
A Mobile Application for Smart House Remote Control System
Venue: arXiv cs.OH 2010
Year: 2010

At the start of the second decade of 21th century, the time has come to make the Smart Houses a reality for regular use. The different parts of a Smart House are researched but there are still distances from an applicable system, using the modern technology. In this paper we present an overview of the Smart House subsystems necessary for controlling the house using a mobile application efficiently and securely. The sequence diagram of the mobile application connecting to the server application and also the use-cases possible are presented. The challenges faced in designing the mobile application and illustrating the updated house top plane view in that application, are discussed and solutions are adapted for it. Finally the designed mobile application was implemented and the important sections of it were described, such as the interactive house top view map which indicates the status of the devices using predefined icons. The facilities to manage the scheduled tasks and defined rules are also implemented in this mobile application that was developed for use in Windows Mobile platform. This application has the capability of connecting to the main server using GPRS mobile internet and SMS. This system is expected to be an important step towards a unified system structure that can be used efficiently in near future regular houses.
Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town?
Venue: arXiv cs.CG 2010
Year: 2010

An n-town, for a natural number n, is a group of n buildings, each occupying a distinct position on a 2-dimensional integer grid. If we measure the distance between two buildings along the axis-parallel street grid, then an n-town has optimal shape if the sum of all pairwise Manhattan distances is minimized. This problem has been studied for cities, i.e., the limiting case of very large n. For cities, it is known that the optimal shape can be described by a differential equation, for which no closed-form is known. We show that optimal n-towns can be computed in O(n^7.5) time. This is also practically useful, as it allows us to compute optimal solutions up to n=80.
Face Detection with Effective Feature Extraction
Venue: arXiv cs.CV 2010
Year: 2010

There is an abundant literature on face detection due to its important role in many vision applications. Since Viola and Jones proposed the first real-time AdaBoost based face detector, Haar-like features have been adopted as the method of choice for frontal face detection. In this work, we show that simple features other than Haar-like features can also be applied for training an effective face detector. Since, single feature is not discriminative enough to separate faces from difficult non-faces, we further improve the generalization performance of our simple features by introducing feature co-occurrences. We demonstrate that our proposed features yield a performance improvement compared to Haar-like features. In addition, our findings indicate that features play a crucial role in the ability of the system to generalize.
Fast Pseudo-Random Fingerprints
Venue: arXiv cs.DS 2010
Year: 2010

We propose a method to exponentially speed up computation of various fingerprints, such as the ones used to compute similarity and rarity in massive data sets. Rather then maintaining the full stream of $b$ items of a universe $[u]$, such methods only maintain a concise fingerprint of the stream, and perform computations using the fingerprints. The computations are done approximately, and the required fingerprint size $k$ depends on the desired accuracy $ε$ and confidence $δ$. Our technique maintains a single bit per hash function, rather than a single integer, thus requiring a fingerprint of length $k = O(\frac{\ln \frac{1}δ}{ε^2})$ bits, rather than $O(\log u \cdot \frac{\ln \frac{1}δ}{ε^2})$ bits required by previous approaches. The main advantage of the fingerprints we propose is that rather than computing the fingerprint of a stream of $b$ items in time of $O(b \cdot k)$, we can compute it in time $O(b \log k)$. Thus this allows an exponential speedup for the fingerprint construction, or alternatively allows achieving a much higher accuracy while preserving computation time. Our methods rely on a specific family of pseudo-random hashes for which we can quickly locate hashes resulting in small values.
Synthesis of Binary k-Stage Machines
Venue: arXiv cs.CR 2010
Year: 2010

An algorithm for constructing a shortest binary k-stage machine generating a given binary sequence is presented. This algorithm can be considered as an extension of Berlekamp-Massey algorithm to the non-linear case.
Simultaneous Event Execution in Heterogeneous Wireless Sensor Networks
Venue: arXiv cs.DC 2010
Year: 2010

We present a synchronization algorithm to let nodes in a sensor network simultaneously execute a task at a given point in time. In contrast to other time synchronization algorithms we do not provide a global time basis that is shared on all nodes. Instead, any node in the network can spontaneously initiate a process that allows the simultaneous execution of arbitrary tasks. We show that our approach is beneficial in scenarios where a global time is not needed, as it requires little communication compared with other time synchronization algorithms. We also show that our algorithm works in heterogeneous systems where the hardware provides highly varying clock accuracy. Moreover, heterogeneity does not only affect the hardware, but also the communication channels. We deal with different connection types---from highly unreliable and fluctuating wireless channels to reliable and fast wired connections.
Some Theorems on the Algorithmic Approach to Probability Theory and Information Theory
Venue: arXiv cs.IT 2010
Year: 2010

This is a 1971 dissertation. Only its extended abstract was published at the time. While some results appeared in other publications, a number of details remained unpublished and may still have relevance.
Usability testing: a review of some methodological and technical aspects of the method
Venue: arXiv cs.HC 2010
Year: 2010

The aim of this paper is to review some work conducted in the field of user testing that aims at specifying or clarifying the test procedures and at defining and developing tools to help conduct user tests. The topics that have been selected were considered relevant for evaluating applications in the field of medical and health care informatics. These topics are: the number of participants that should take part in a user test, the test procedure, remote usability evaluation, usability testing tools, and evaluating mobile applications.
Multiple Access Channels with Cooperative Encoders and Channel State Information
Venue: arXiv cs.IT 2010
Year: 2010

The two-user Multiple Access Channel (MAC) with cooperative encoders and Channel State Information (CSI) is considered where two different scenarios are investigated: A two-user MAC with common message (MACCM) and a two-user MAC with conferencing encoders (MACCE). For both situations, the two cases where the CSI is known to the encoders either non-causally or causally are studied. Achievable rate regions are established for both discrete memoryless channels and Gaussian channels with additive interference. The achievable rate regions derived for the Gaussian models with additive interference known non-causally to the encoders are shown to coincide with the capacity region of the same channel with no interference. Therefore, the capacity region for such channels is established.
Network Flows for Functions
Venue: arXiv cs.NI 2010
Year: 2010

We consider in-network computation of an arbitrary function over an arbitrary communication network. A network with capacity constraints on the links is given. Some nodes in the network generate data, e.g., like sensor nodes in a sensor network. An arbitrary function of this distributed data is to be obtained at a terminal node. The structure of the function is described by a given computation schema, which in turn is represented by a directed tree. We design computing and communicating schemes to obtain the function at the terminal at the maximum rate. For this, we formulate linear programs to determine network flows that maximize the computation rate. We then develop fast combinatorial primal-dual algorithm to obtain $ε$-approximate solutions to these linear programs. We then briefly describe extensions of our techniques to the cases of multiple terminals wanting different functions, multiple computation schemas for a function, computation with a given desired precision, and to networks with energy constraints at nodes.
Exact Analysis of Pattern Matching Algorithms with Probabilistic Arithmetic Automata
Venue: arXiv cs.DS 2010
Year: 2010

We propose a framework for the exact probabilistic analysis of window-based pattern matching algorithms, such as Boyer-Moore, Horspool, Backward DAWG Matching, Backward Oracle Matching, and more. In particular, we show how to efficiently obtain the distribution of such an algorithm's running time cost for any given pattern in a random text model, which can be quite general, from simple uniform models to higher-order Markov models or hidden Markov models (HMMs). Furthermore, we provide a technique to compute the exact distribution of \emph{differences} in running time cost of two algorithms. In contrast to previous work, our approach is neither limited to simple text models, nor to asymptotic statements, nor to moment computations such as expectation and variance. Methodically, we use extensions of finite automata which we call deterministic arithmetic automata (DAAs) and probabilistic arithmetic automata (PAAs) [13]. To our knowledge, this is the first time that substring- or suffix-based pattern matching algorithms are analyzed exactly. Experimentally, we compare Horspool's algorithm, Backward DAWG Matching, and Backward Oracle Matching on prototypical patterns of short length and provide statistics on the size of minimal DAAs for these computations.
Optimal Power Allocation for Secrecy Fading Channels Under Spectrum-Sharing Constraints
Venue: arXiv cs.IT 2010
Year: 2010

In the spectrum-sharing technology, a secondary user may utilize the primary user's licensed band as long as its interference to the primary user is below a tolerable value. In this paper, we consider a scenario in which a secondary user is operating in the presence of both a primary user and an eavesdropper. Hence, the secondary user has both interference limitations and security considerations. In such a scenario, we study the secrecy capacity limits of opportunistic spectrum-sharing channels in fading environments and investigate the optimal power allocation for the secondary user under average and peak received power constraints at the primary user with global channel side information (CSI). Also, in the absence of the eavesdropper's CSI, we study optimal power allocation under an average power constraint and propose a suboptimal on/off power control method.
Deterministic Compressed Sensing Matrices from Additive Character Sequences
Venue: arXiv cs.IT 2010
Year: 2010

Compressed sensing is a novel technique where one can recover sparse signals from the undersampled measurements. In this correspondence, a $K \times N$ measurement matrix for compressed sensing is deterministically constructed via additive character sequences. The Weil bound is then used to show that the matrix has asymptotically optimal coherence for $N=K^2$, and to present a sufficient condition on the sparsity level for unique sparse recovery. Also, the restricted isometry property (RIP) is statistically studied for the deterministic matrix. Using additive character sequences with small alphabets, the compressed sensing matrix can be efficiently implemented by linear feedback shift registers. Numerical results show that the deterministic compressed sensing matrix guarantees reliable matching pursuit recovery performance for both noiseless and noisy measurements.
An Investigation of the Advantages of Organization-Centered Multi-Agent Systems
Venue: arXiv cs.MA 2010
Year: 2010

Whereas classical multi-agent systems have the agent in center, there have recently been a development towards focusing more on the organization of the system. This allows the designer to focus on what the system goals are, without considering how the goals should be fulfilled. This paper investigates whether taking this approach has any clear advantages to the classical way of implementing multi-agent systems. The investigation is done by implementing each type of system in the same environment in order to realize what advantages and disadvantages each approach has.
List decoding for nested lattices and applications to relay channels
Venue: arXiv cs.IT 2010
Year: 2010

We demonstrate a decoding scheme for nested lattice codes which is able to decode a list of a particular size which contains the transmitted codeword with high probability. This list decoder is analogous to that used in random coding arguments in achievability schemes of relay channels, and allows for the effective combination of information from the relay and source node. Using this list decoding result, we demonstrate 1) that lattice codes may achieve the capacity of the physically degraded AWGN relay channel, 2) an achievable rate region for the two-way relay channel with direct links using lattice codes, and 3) that we may improve the constant gap to capacity for specific cases of the two-way relay channel with direct links.
Difference Antenna Selection and Power Allocation for Wireless Cognitive Systems
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we propose an antenna selection method in a wireless cognitive radio (CR) system, namely difference selection, whereby a single transmit antenna is selected at the secondary transmitter out of $M$ possible antennas such that the weighted difference between the channel gains of the data link and the interference link is maximized. We analyze mutual information and outage probability of the secondary transmission in a CR system with difference antenna selection, and propose a method of optimizing these performance metrics of the secondary data link subject to practical constraints on the peak secondary transmit power and the average interference power as seen by the primary receiver. The optimization is performed over two parameters: the peak secondary transmit power and the difference selection weight $δ\in [0, 1]$. We show that, difference selection using the optimized parameters determined by the proposed method can be, in many cases of interest, superior to a so called ratio selection method disclosed in the literature, although ratio selection has been shown to be optimal, when impractically, the secondary transmission power constraint is not applied. We address the effects that the constraints have on mutual information and outage probability, and discuss the practical implications of the results.
A Microwave Imaging and Enhancement Technique from Noisy Synthetic Data
Venue: arXiv cs.CV 2010
Year: 2010

An inverse iterative algorithm for microwave imaging based on moment method solution is presented here. The iterative scheme has been developed on constrained optimization technique and is certain to converge. Different mesh size for the model has been used here to overcome the Inverse Crime. The synthetic data at the receivers is contaminated with different percentage of noise. The ill-posedness of the problem is solved by Levenberg-Marquardt method. The algorithm is applied to synthetic data and the reconstructed image is then further enhanced through the Image enhancement technique
Oblivious Buy-at-Bulk in Planar Graphs
Venue: arXiv cs.DS 2010
Year: 2010

In the oblivious buy-at-bulk network design problem in a graph, the task is to compute a fixed set of paths for every pair of source-destinations in the graph, such that any set of demands can be routed along these paths. The demands could be aggregated at intermediate edges where the fusion-cost is specified by a canonical (non-negative concave) function $f$. We give a novel algorithm for planar graphs which is oblivious with respect to the demands, and is also oblivious with respect to the fusion function $f$. The algorithm is deterministic and computes the fixed set of paths in polynomial time, and guarantees a $O(\log n)$ approximation ratio for any set of demands and any canonical fusion function $f$, where $n$ is the number of nodes. The algorithm is asymptotically optimal, since it is known that this problem cannot be approximated with better than $Ω(\log n)$ ratio. To our knowledge, this is the first tight analysis for planar graphs, and improves the approximation ratio by a factor of $\log n$ with respect to previously known results.
Derandomization and Group Testing
Venue: arXiv cs.IT 2010
Year: 2010

The rapid development of derandomization theory, which is a fundamental area in theoretical computer science, has recently led to many surprising applications outside its initial intention. We will review some recent such developments related to combinatorial group testing. In its most basic setting, the aim of group testing is to identify a set of "positive" individuals in a population of items by taking groups of items and asking whether there is a positive in each group. In particular, we will discuss explicit constructions of optimal or nearly-optimal group testing schemes using "randomness-conducting" functions. Among such developments are constructions of error-correcting group testing schemes using randomness extractors and condensers, as well as threshold group testing schemes from lossless condensers.
Statistical Modelling of ft to Process Parameters in 30 nm Gate Length Finfets
Venue: arXiv cs.OH 2010
Year: 2010

This paper investigates the effect of process variations on unity gain frequency (ft) in 30 nm gate length FinFET by performing extensive TCAD simulations. Six different geometrical parameters, channel doping, source/drain doping and gate electrode work function are studied for their sensitivity on ft. It is found that ft is more sensitive to gate length, underlap, gate-oxide thickness, channel and Source/Drain doping and less sensitive to source/drain width and length, and work function variations. Statistical modelling has been performed for ft through design of experiment with respect to sensitive parameters. The model has been validated through a comparison between random set of experimental data simulations and predicted values obtained from the model.
Performance of wireless network coding: motivating small encoding numbers
Venue: arXiv cs.NI 2010
Year: 2010

This paper focuses on a particular transmission scheme called local network coding, which has been reported to provide significant performance gains in practical wireless networks. The performance of this scheme strongly depends on the network topology and thus on the locations of the wireless nodes. Also, it has been shown previously that finding the encoding strategy, which achieves maximum performance, requires complex calculations to be undertaken by the wireless node in real-time. Both deterministic and random point pattern are explored and using the Boolean connectivity model we provide upper bounds for the maximum coding number, i.e., the number of packets that can be combined such that the corresponding receivers are able to decode. For the models studied, this upper bound is of order of $\sqrt{N}$, where $N$ denotes the (mean) number of neighbors. Moreover, achievable coding numbers are provided for grid-like networks. We also calculate the multiplicative constants that determine the gain in case of a small network. Building on the above results, we provide an analytic expression for the upper bound of the efficiency of local network coding. The conveyed message is that it is favorable to reduce computational complexity by relying only on small encoding numbers since the resulting expected throughput loss is negligible.
On Equivalence Between Network Topologies
Venue: arXiv cs.IT 2010
Year: 2010

One major open problem in network coding is to characterize the capacity region of a general multi-source multi-demand network. There are some existing computational tools for bounding the capacity of general networks, but their computational complexity grows very quickly with the size of the network. This motivates us to propose a new hierarchical approach which finds upper and lower bounding networks of smaller size for a given network. This approach sequentially replaces components of the network with simpler structures, i.e., with fewer links or nodes, so that the resulting network is more amenable to computational analysis and its capacity provides an upper or lower bound on the capacity of the original network. The accuracy of the resulting bounds can be bounded as a function of the link capacities. Surprisingly, we are able to simplify some families of network structures without any loss in accuracy.
A note on hierarchies and bureaucracies
Venue: arXiv cs.GT 2010
Year: 2010

In this note, we argue that there is a bug in [Tirole, J., "Hierarchies and bureaucracies: On the role of collusion in organizations," {\em Journal of Law, Economics and Organization}, vol.2, 181-214, 1986].
Preserving Privacy in Sequential Data Release against Background Knowledge Attacks
Venue: arXiv cs.DB 2010
Year: 2010

A large amount of transaction data containing associations between individuals and sensitive information flows everyday into data stores. Examples include web queries, credit card transactions, medical exam records, transit database records. The serial release of these data to partner institutions or data analysis centers is a common situation. In this paper we show that, in most domains, correlations among sensitive values associated to the same individuals in different releases can be easily mined, and used to violate users' privacy by adversaries observing multiple data releases. We provide a formal model for privacy attacks based on this sequential background knowledge, as well as on background knowledge on the probability distribution of sensitive values over different individuals. We show how sequential background knowledge can be actually obtained by an adversary, and used to identify with high confidence the sensitive values associated with an individual. A defense algorithm based on Jensen-Shannon divergence is proposed, and extensive experiments show the superiority of the proposed technique with respect to other applicable solutions. To the best of our knowledge, this is the first work that systematically investigates the role of sequential background knowledge in serial release of transaction data.