OpenRaiser/Intern-Atlas huggingface dataset:
Some Spreadsheet Poka-Yoke
Venue: arXiv cs.HC 2009
Year: 2009

Whilst not all spreadsheet defects are structural in nature, poor layout choices can compromise spreadsheet quality. These defects may be avoided at the development stage by some simple mistake prevention and detection devices. Poka-Yoke (Japanese for Mistake Proofing), which owes its genesis to the Toyota Production System (the standard for manufacturing excellence throughout the world) offers some principles that may be applied to reducing spreadsheet defects. In this paper we examine spreadsheet structure and how it can lead to defects and illustrate some basic spreadsheet Poka-Yokes to reduce them. These include guidelines on how to arrange areas of cells so that whole rows and columns can be inserted anywhere without causing errors, and rules for when to use relative and absolute references with respect to what type of area is being referred to.
Optimal Joint Target Detection and Parameter Estimation By MIMO Radar
Venue: arXiv cs.IT 2009
Year: 2009

We consider multiple-input multiple-output (MIMO) radar systems with widely-spaced antennas. Such antenna configuration facilitates capturing the inherent diversity gain due to independent signal dispersion by the target scatterers. We consider a new MIMO radar framework for detecting a target that lies in an unknown location. This is in contrast with conventional MIMO radars which break the space into small cells and aim at detecting the presence of a target in a specified cell. We treat this problem through offering a novel composite hypothesis testing framework for target detection when (i) one or more parameters of the target are unknown and we are interested in estimating them, and (ii) only a finite number of observations are available. The test offered optimizes a metric which accounts for both detection and estimation accuracies. In this paper as the parameter of interest we focus on the vector of time-delays that the waveforms undergo from being emitted by the transmit antennas until being observed by the receive antennas. The analytical and empirical results establish that for the proposed joint target detection and time-delay estimation framework, MIMO radars exhibit significant gains over phased-array radars for extended targets which consist of multiple independent scatterers. For point targets modeled as single scatterers, however, the detection/estimation accuracies of MIMO and phased-array radars for this specific setup (joint target detection and time-delay estimation) are comparable.
Enhanced Algorithm for Link to System level Interface Mapping
Venue: arXiv cs.IT 2009
Year: 2009

The current SINR mechanism does not provide the base station (BS) with any knowledge on the frequency selectivity of channel from mobile service station(MSS). This knowledge is important since, contrary to the AWGN channel, in a frequency selective channel there is no longer a 1 to 1 relation between amount of increase in power and amount of improvement in effective SINR 1. Furthermore, the relation is dependent on MCS level. This lack of knowledge in the BS side results in larger fade margins, which translates directly to reduction in capacity. In this paper we propose a enhanced algorithm on the EESM model with weighted beta (β) that provides the BS with sufficient knowledge on the channel-dependent relationship between power increase, MCS change and improvement in effective SINR.
2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties
Venue: arXiv cs.GT 2009
Year: 2009

The solution to a Nash or a nonsymmetric bargaining game is obtained by maximizing a concave function over a convex set, i.e., it is the solution to a convex program. We show that each 2-player game whose convex program has linear constraints, admits a rational solution and such a solution can be found in polynomial time using only an LP solver. If in addition, the game is succinct, i.e., the coefficients in its convex program are ``small'', then its solution can be found in strongly polynomial time. We also give a non-succinct linear game whose solution can be found in strongly polynomial time.
Checks and Controls in Spreadsheets
Venue: arXiv cs.HC 2009
Year: 2009

Spreadsheets that are informally created are harder to test than they should be. Simple cross-foot checks or being easily readable are modest but attainable goals for every spreadsheet developer. This paper lists some tips on building self-checking into a spreadsheet in order to provide more confidence to the reader that a spreadsheet is robust.
Embedded Spreadsheet Modelling
Venue: arXiv cs.HC 2009
Year: 2009

In larger accounting firms, specialist modellers typically sit in separate teams. This paper will look at the advantages of embedding a specialist modeller within a Corporate Finance Team.
Documenting Problem-Solving Knowledge: Proposed Annotation Design Guidelines and their Application to Spreadsheet Tools
Venue: arXiv cs.SE 2009
Year: 2009

End-user programmers create software to solve problems, yet the problem-solving knowledge generated in the process often remains tacit within the software artifact. One approach to exposing this knowledge is to enable the end-user to annotate the artifact as they create and use it. A 3-level model of annotation is presented and guidelines are proposed for the design of end-user programming environments supporting the explicit and literate annotation levels. These guidelines are then applied to the spreadsheet end-user programming paradigm.
A new approach to services differentiation between mobile terminals of a wireless LAN
Venue: arXiv cs.NI 2009
Year: 2009

This study aims to identify the advantages and disadvantages of several mechanisms for service differentiation in mobile terminals of a wireless LAN to establish a more better and more optimal. At the end of the analysis of available approaches for the quality of service of the IEEE 802.11 standard, the objective of this paper is to suggest a new method named DF-DCF Differentiated Frame DCF. The performance of the suggested method in a Network Simulator (NS) environment allowed its validation through a set of testing and simulation scenarios. Simulation results have shown that the DF-DCF method is better suited for mobile nodes in a wireless communication network.
Distributed Joint Source-Channel Coding for Functions over a Multiple Access Channel
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we provide sufficient conditions for lossy transmission of functions of correlated data over a multiple access channel (MAC). The conditions obtained can be shown as generalized version of Yamamoto's result. We also obtain efficient joint source-channel coding schemes for transmission of discrete and continuous alphabet sources to recover the function values. Keywords: Joint source-channel coding, Graph coloring, Lipschitz functions, Correlated sources.
Linearly Coupled Communication Games
Venue: arXiv cs.GT 2009
Year: 2009

This paper discusses a special type of multi-user communication scenario, in which users' utilities are linearly impacted by their competitors' actions. First, we explicitly characterize the Nash equilibrium and Pareto boundary of the achievable utility region. Second, the price of anarchy incurred by the non-collaborative Nash strategy is quantified. Third, to improve the performance in the non-cooperative scenarios, we investigate the properties of an alternative solution concept named conjectural equilibrium, in which individual users compensate for their lack of information by forming internal beliefs about their competitors. The global convergence of the best response and Jacobi update dynamics that achieve various conjectural equilibria are analyzed. It is shown that the Pareto boundaries of the investigated linearly coupled games can be sustained as stable conjectural equilibria if the belief functions are properly initialized. The investigated models apply to a variety of realistic applications encountered in the multiple access design, including wireless random access and flow control.
Approximating the Permanent with Belief Propagation
Venue: arXiv cs.LG 2009
Year: 2009

This work describes a method of approximating matrix permanents efficiently using belief propagation. We formulate a probability distribution whose partition function is exactly the permanent, then use Bethe free energy to approximate this partition function. After deriving some speedups to standard belief propagation, the resulting algorithm requires $(n^2)$ time per iteration. Finally, we demonstrate the advantages of using this approximation.
Spectral Graph Analysis of Quasi-Cyclic Codes
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we analyze the bound on the additive white Gaussian noise channel (AWGNC) pseudo-weight of a (c,d)-regular linear block code based on the two largest eigenvalues of H^T H. In particular, we analyze (c,d)-regular quasi-cyclic (QC) codes of length rL described by J x L block parity-check matrices with circulant block entries of size r x r. We proceed by showing how the problem of computing the eigenvalues of the rL x rL matrix H^T H can be reduced to the problem of computing eigenvalues for r matrices of size L x L. We also give a necessary condition for the bound to be attained for a circulant matrix H and show a few classes of cyclic codes satisfying this criterion.
Source and Channel Simulation Using Arbitrary Randomness
Venue: arXiv cs.IT 2009
Year: 2009

Necessary and sufficient conditions for approximation of a general channel by a general source are proved. For the special case in which the channel input is deterministic, which corresponds to source simulation, we prove a stronger necessary condition. As the approximation criteria, vanishing variational distance between the original and the approximated quantity is used for both of the problems. Both necessary and sufficient conditions for the two problems are based on some individual properties of the sources and the channel and are relatively easy to evaluate. In particular, unlike prior results for this problem, our results do not require solving an optimization problem to test simulatability. The results are illustrated with several non-ergodic examples.
Phased-MIMO Radar: A Tradeoff Between Phased-Array and MIMO Radars
Venue: arXiv cs.IT 2009
Year: 2009

We propose a new technique for multiple-input multiple-output (MIMO) radar with colocated antennas which we call phased-MIMO radar. The new technique enjoys the advantages of MIMO radar without sacrificing the main advantage of phased-array radar which is the coherent processing gain at the transmitting side. The essence of the proposed technique is to partition the transmitting array into a number of subarrays that are allowed to overlap. Then, each subarray is used to coherently transmit a waveform which is orthogonal to the waveforms transmitted by other subarrays. Coherent processing gain can be achieved by designing a weight vector for each subarray to form a beam towards a certain direction in space. Moreover, the subarrays are combined jointly to form a MIMO radar resulting in higher resolution capabilities. The substantial improvements offered by the proposed phased-MIMO radar technique as compared to previous techniques are demonstrated analytically and by simulations through analysis of the corresponding beampatterns and achievable output signal-to-noise-plus-interference ratios. Both analytical and simulation results validate the effectiveness of the proposed phased-MIMO radar.
An Optimal Self-Stabilizing Firing Squad
Venue: arXiv cs.DC 2009
Year: 2009

Consider a fully connected network where up to $t$ processes may crash, and all processes start in an arbitrary memory state. The self-stabilizing firing squad problem consists of eventually guaranteeing simultaneous response to an external input. This is modeled by requiring that the non-crashed processes "fire" simultaneously if some correct process received an external "GO" input, and that they only fire as a response to some process receiving such an input. This paper presents FireAlg, the first self-stabilizing firing squad algorithm. The FireAlg algorithm is optimal in two respects: (a) Once the algorithm is in a safe state, it fires in response to a GO input as fast as any other algorithm does, and (b) Starting from an arbitrary state, it converges to a safe state as fast as any other algorithm does.
Interference Assisted Secret Communication
Venue: arXiv cs.IT 2009
Year: 2009

Wireless communication is susceptible to eavesdropping attacks because of its broadcast nature. This paper illustrates how interference can be used to counter eavesdropping and assist secrecy. In particular, a wire-tap channel with a helping interferer (WT-HI) is considered. Here, a transmitter sends a confidential message to its intended receiver in the presence of a passive eavesdropper and with the help of an independent interferer. The interferer, which does not know the confidential message, helps in ensuring the secrecy of the message by sending an independent signal. An achievable secrecy rate and several computable outer bounds on the secrecy capacity of the WT-HI are given for both discrete memoryless and Gaussian channels.
Low-complexity non-uniform demand multicast network coding problems
Venue: arXiv cs.IT 2009
Year: 2009

The non-uniform demand network coding problem is posed as a single-source and multiple-sink network transmission problem where the sinks may have heterogeneous demands. In contrast with multicast problems, non-uniform demand problems are concerned with the amounts of data received by each sink, rather than the specifics of the received data. In this work, we enumerate non-uniform network demand scenarios under which network coding solutions can be found in polynomial time. This is accomplished by relating the demand problem with the graph coloring problem, and then applying results from the strong perfect graph theorem to identify coloring problems which can be solved in polynomial time. This characterization of efficiently-solvable non-uniform demand problems is an important step in understanding such problems, as it allows us to better understand situations under which the NP-complete problem might be tractable.
Concurrent Knowledge-Extraction in the Public-Key Model
Venue: arXiv cs.CC 2009
Year: 2009

Knowledge extraction is a fundamental notion, modelling machine possession of values (witnesses) in a computational complexity sense. The notion provides an essential tool for cryptographic protocol design and analysis, enabling one to argue about the internal state of protocol players without ever looking at this supposedly secret state. However, when transactions are concurrent (e.g., over the Internet) with players possessing public-keys (as is common in cryptography), assuring that entities ``know'' what they claim to know, where adversaries may be well coordinated across different transactions, turns out to be much more subtle and in need of re-examination. Here, we investigate how to formally treat knowledge possession by parties (with registered public-keys) interacting over the Internet. Stated more technically, we look into the relative power of the notion of ``concurrent knowledge-extraction'' (CKE) in the concurrent zero-knowledge (CZK) bare public-key (BPK) model.
Minimum feature size preserving decompositions
Venue: arXiv cs.CG 2009
Year: 2009

The minimum feature size of a crossing-free straight line drawing is the minimum distance between a vertex and a non-incident edge. This quantity measures the resolution needed to display a figure or the tool size needed to mill the figure. The spread is the ratio of the diameter to the minimum feature size. While many algorithms (particularly in meshing) depend on the spread of the input, none explicitly consider finding a mesh whose spread is similar to the input. When a polygon is partitioned into smaller regions, such as triangles or quadrangles, the degradation is the ratio of original to final spread (the final spread is always greater). Here we present an algorithm to quadrangulate a simple n-gon, while achieving constant degradation. Note that although all faces have a quadrangular shape, the number of edges bounding each face may be larger. This method uses Theta(n) Steiner points and produces Theta(n) quadrangles. In fact to obtain constant degradation, Omega(n) Steiner points are required by any algorithm. We also show that, for some polygons, a constant factor cannot be achieved by any triangulation, even with an unbounded number of Steiner points. The specific lower bounds depend on whether Steiner vertices are used or not.
Semantic Robot Vision Challenge: Current State and Future Directions
Venue: arXiv cs.CV 2009
Year: 2009

The Semantic Robot Vision Competition provided an excellent opportunity for our research lab to integrate our many ideas under one umbrella, inspiring both collaboration and new research. The task, visual search for an unknown object, is relevant to both the vision and robotics communities. Moreover, since the interplay of robotics and vision is sometimes ignored, the competition provides a venue to integrate two communities. In this paper, we outline a number of modifications to the competition to both improve the state-of-the-art and increase participation.
Delay-Sensitive Distributed Power and Transmission Threshold Control for S-ALOHA Network with Finite State Markov Fading Channels
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider the delay-sensitive power and transmission threshold control design in S-ALOHA network with FSMC fading channels. The random access system consists of an access point with K competing users, each has access to the local channel state information (CSI) and queue state information (QSI) as well as the common feedback (ACK/NAK/Collision) from the access point. We seek to derive the delay-optimal control policy (composed of threshold and power control). The optimization problem belongs to the memoryless policy K-agent infinite horizon decentralized Markov decision process (DEC-MDP), and finding the optimal policy is shown to be computationally intractable. To obtain a feasible and low complexity solution, we recast the optimization problem into two subproblems, namely the power control and the threshold control problem. For a given threshold control policy, the power control problem is decomposed into a reduced state MDP for single user so that the overall complexity is O(NJ), where N and J are the buffer size and the cardinality of the CSI states. For the threshold control problem, we exploit some special structure of the collision channel and common feedback information to derive a low complexity solution. The delay performance of the proposed design is shown to have substantial gain relative to conventional throughput optimal approaches for S-ALOHA.
Techniques for Highly Multiobjective Optimisation: Some Nondominated Points are Better than Others
Venue: arXiv cs.NE 2009
Year: 2009

The research area of evolutionary multiobjective optimization (EMO) is reaching better understandings of the properties and capabilities of EMO algorithms, and accumulating much evidence of their worth in practical scenarios. An urgent emerging issue is that the favoured EMO algorithms scale poorly when problems have many (e.g. five or more) objectives. One of the chief reasons for this is believed to be that, in many-objective EMO search, populations are likely to be largely composed of nondominated solutions. In turn, this means that the commonly-used algorithms cannot distinguish between these for selective purposes. However, there are methods that can be used validly to rank points in a nondominated set, and may therefore usefully underpin selection in EMO search. Here we discuss and compare several such methods. Our main finding is that simple variants of the often-overlooked Average Ranking strategy usually outperform other methods tested, covering problems with 5-20 objectives and differing amounts of inter-objective correlation.
Component based platform for multimedia applications
Venue: arXiv cs.MM 2009
Year: 2009

We propose a platform for distributed multimedia applications which simplifies the development process and at the same time ensures application portability, flexibility and performance. The platform is implemented using the Netscape Portable Runtime (NSPR) and the Cross-Platform Component Object Model (XPCOM).
A Modeling Framework for Generating Security Protocol Specifications
Venue: arXiv cs.CR 2009
Year: 2009

We propose a modeling framework for generating security protocol specifications. The generated protocol specifications rely on the use of a sequential and a semantical component. The first component defines protocol properties such as preconditions, effects, message sequences and it is developed as a WSDL-S specification. The second component defines the semantic aspects corresponding to the messages included in the first component by the use of ontological constructions and it is developed as an OWL-based specification. Our approach was validated on 13 protocols from which we mention: the ISO9798 protocol, the CCITTX.509 data transfer protocol and the Kerberos symmetric key protocol.
On the Optimality of Beamforming for Multi-User MISO Interference Channels with Single-User Detection
Venue: arXiv cs.IT 2009
Year: 2009

For a multi-user interference channel with multi-antenna transmitters and single-antenna receivers, by restricting each receiver to a single-user detector, computing the largest achievable rate region amounts to solving a family of non-convex optimization problems. Recognizing the intrinsic connection between the signal power at the intended receiver and the interference power at the unintended receiver, the original family of non-convex optimization problems is converted into a new family of convex optimization problems. It is shown that, for such interference channels with each receiver implementing single-user detection, transmitter beamforming can achieve all boundary points of the achievable rate region.
Non-quadratic convex regularized reconstruction of MR images from spiral acquisitions
Venue: arXiv cs.CV 2009
Year: 2009

Combining fast MR acquisition sequences and high resolution imaging is a major issue in dynamic imaging. Reducing the acquisition time can be achieved by using non-Cartesian and sparse acquisitions. The reconstruction of MR images from these measurements is generally carried out using gridding that interpolates the missing data to obtain a dense Cartesian k-space filling. The MR image is then reconstructed using a conventional Fast Fourier Transform. The estimation of the missing data unavoidably introduces artifacts in the image that remain difficult to quantify. A general reconstruction method is proposed to take into account these limitations. It can be applied to any sampling trajectory in k-space, Cartesian or not, and specifically takes into account the exact location of the measured data, without making any interpolation of the missing data in k-space. Information about the expected characteristics of the imaged object is introduced to preserve the spatial resolution and improve the signal to noise ratio in a regularization framework. The reconstructed image is obtained by minimizing a non-quadratic convex objective function. An original rewriting of this criterion is shown to strongly improve the reconstruction efficiency. Results on simulated data and on a real spiral acquisition are presented and discussed.
WebNC: efficient sharing of web applications
Venue: arXiv cs.HC 2009
Year: 2009

WebNC is a system for efficiently sharing, retrieving and viewing web applications. Unlike existing screencasting and screensharing tools, WebNC is optimized to work with web pages where a lot of scrolling happens. WebNC uses a tile-based encoding to capture, transmit and deliver web applications, and relies only on dynamic HTML and JavaScript. The resulting webcasts require very little bandwidth and are viewable on any modern web browser including Firefox and Internet Explorer as well as browsers on the iPhone and Android platforms.