OpenRaiser/Intern-Atlas huggingface dataset:
An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles
Venue: arXiv cs.CG 2010
Year: 2010

In this paper, we study the following problem of reconstructing a simple polygon: Given a cyclically ordered vertex sequence of an unknown simple polygon P of n vertices and, for each vertex v of P, the sequence of angles defined by all the visible vertices of v in P, reconstruct the polygon P (up to similarity). An O(n^3 log n) time algorithm has been proposed for this problem. We present an improved algorithm with running time O(n^2), based on new observations on the geometric structures of the problem. Since the input size (i.e., the total number of input visibility angles) is O(n^2) in the worst case, our algorithm is worst-case optimal.
Is Witsenhausen's counterexample a relevant toy?
Venue: arXiv cs.IT 2010
Year: 2010

This paper answers a question raised by Doyle on the relevance of the Witsenhausen counterexample as a toy decentralized control problem. The question has two sides, the first of which focuses on the lack of an external channel in the counterexample. Using existing results, we argue that the core difficulty in the counterexample is retained even in the presence of such a channel. The second side questions the LQG formulation of the counterexample. We consider alternative formulations and show that the understanding developed for the LQG case guides the investigation for these other cases as well. Specifically, we consider 1) a variation on the original counterexample with general, but bounded, noise distributions, and 2) an adversarial extension with bounded disturbance and quadratic costs. For each of these formulations, we show that quantization-based nonlinear strategies outperform linear strategies by an arbitrarily large factor. Further, these nonlinear strategies also perform within a constant factor of the optimal, uniformly over all possible parameter choices (for fixed noise distributions in the Bayesian case). Fortuitously, the assumption of bounded noise results in a significant simplification of proofs as compared to those for the LQG formulation. Therefore, the results in this paper are also of pedagogical interest.
Popularity at Minimum Cost
Venue: arXiv cs.DS 2010
Year: 2010

We consider an extension of the {\em popular matching} problem in this paper. The input to the popular matching problem is a bipartite graph G = (A U B,E), where A is a set of people, B is a set of items, and each person a belonging to A ranks a subset of items in an order of preference, with ties allowed. The popular matching problem seeks to compute a matching M* between people and items such that there is no matching M where more people are happier with M than with M*. Such a matching M* is called a popular matching. However, there are simple instances where no popular matching exists. Here we consider the following natural extension to the above problem: associated with each item b belonging to B is a non-negative price cost(b), that is, for any item b, new copies of b can be added to the input graph by paying an amount of cost(b) per copy. When G does not admit a popular matching, the problem is to "augment" G at minimum cost such that the new graph admits a popular matching. We show that this problem is NP-hard; in fact, it is NP-hard to approximate it within a factor of sqrt{n1}/2, where n1 is the number of people. This problem has a simple polynomial time algorithm when each person has a preference list of length at most 2. However, if we consider the problem of "constructing" a graph at minimum cost that admits a popular matching that matches all people, then even with preference lists of length 2, the problem becomes NP-hard. On the other hand, when the number of copies of each item is "fixed", we show that the problem of computing a minimum cost popular matching or deciding that no popular matching exists can be solved in O(mn1) time, where m is the number of edges.
Joint Channel Probing and Proportional Fair Scheduling in Wireless Networks
Venue: arXiv cs.IT 2010
Year: 2010

The design of a scheduling scheme is crucial for the efficiency and user-fairness of wireless networks. Assuming that the quality of all user channels is available to a central controller, a simple scheme which maximizes the utility function defined as the sum logarithm throughput of all users has been shown to guarantee proportional fairness. However, to acquire the channel quality information may consume substantial amount of resources. In this work, it is assumed that probing the quality of each user's channel takes a fraction of the coherence time, so that the amount of time for data transmission is reduced. The multiuser diversity gain does not always increase as the number of users increases. In case the statistics of the channel quality is available to the controller, the problem of sequential channel probing for user scheduling is formulated as an optimal stopping time problem. A joint channel probing and proportional fair scheduling scheme is developed. This scheme is extended to the case where the channel statistics are not available to the controller, in which case a joint learning, probing and scheduling scheme is designed by studying a generalized bandit problem. Numerical results demonstrate that the proposed scheduling schemes can provide significant gain over existing schemes.
Understanding Fashion Cycles as a Social Choice
Venue: arXiv cs.GT 2010
Year: 2010

We present a formal model for studying fashion trends, in terms of three parameters of fashionable items: (1) their innate utility; (2) individual boredom associated with repeated usage of an item; and (3) social influences associated with the preferences from other people. While there are several works that emphasize the effect of social influence in understanding fashion trends, in this paper we show how boredom plays a strong role in both individual and social choices. We show how boredom can be used to explain the cyclic choices in several scenarios such as an individual who has to pick a restaurant to visit every day, or a society that has to repeatedly `vote' on a single fashion style from a collection. We formally show that a society that votes for a single fashion style can be viewed as a single individual cycling through different choices. In our model, the utility of an item gets discounted by the amount of boredom that has accumulated over the past; this boredom increases with every use of the item and decays exponentially when not used. We address the problem of optimally choosing items for usage, so as to maximize over-all satisfaction, i.e., composite utility, over a period of time. First we show that the simple greedy heuristic of always choosing the item with the maximum current composite utility can be arbitrarily worse than the optimal. Second, we prove that even with just a single individual, determining the optimal strategy for choosing items is NP-hard. Third, we show that a simple modification to the greedy algorithm that simply doubles the boredom of each item is a provably close approximation to the optimal strategy. Finally, we present an experimental study over real-world data collected from query logs to compare our algorithms.
How do Range Names Hinder Novice Spreadsheet Debugging Performance?
Venue: arXiv cs.SE 2010
Year: 2010

Although experts diverge on how best to improve spreadsheet quality, it is generally agreed that more time needs to be spent testing spreadsheets. Ideally, experienced and trained spreadsheet engineers would carry this out, but quite often this is neither practical nor possible. Many spreadsheets are a legacy, developed by staff that have since moved on, or indeed modified by many staff no longer employed by the organisation. When such spreadsheets fall into the hands of inexperienced, non-experts, any features that reduce error visibility may become a risk. Range names are one such feature, and this paper, building on previous research, investigates in a more structured and controlled manner the effect they have on the debugging performance of novice spreadsheet users.
Pattern Unification for the Lambda Calculus with Linear and Affine Types
Venue: arXiv cs.LO 2010
Year: 2010

We define the pattern fragment for higher-order unification problems in linear and affine type theory and give a deterministic unification algorithm that computes most general unifiers.
Sharing Graphs
Venue: arXiv cs.CR 2010
Year: 2010

Almost all known secret sharing schemes work on numbers. Such methods will have difficulty in sharing graphs since the number of graphs increases exponentially with the number of nodes. We propose a secret sharing scheme for graphs where we use graph intersection for reconstructing the secret which is hidden as a sub graph in the shares. Our method does not rely on heavy computational operations such as modular arithmetic or polynomial interpolation but makes use of very basic operations like assignment and checking for equality, and graph intersection can also be performed visually. In certain cases, the secret could be reconstructed using just pencil and paper by authorised parties but cannot be broken by an adversary even with unbounded computational power. The method achieves perfect secrecy for (2, n) scheme and requires far fewer operations compared to Shamir's algorithm. The proposed method could be used to share objects such as matrices, sets, plain text and even a heterogeneous collection of these. Since we do not require a previously agreed upon encoding scheme, the method is very suitable for sharing heterogeneous collection of objects in a dynamic fashion.
Throughput Analysis of Buffer-Constrained Wireless Systems in the Finite Blocklength Regime
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, wireless systems operating under queueing constraints in the form of limitations on the buffer violation probabilities are considered. The throughput under such constraints is captured by the effective capacity formulation. It is assumed that finite blocklength codes are employed for transmission. Under this assumption, a recent result on the channel coding rate in the finite blocklength regime is incorporated into the analysis and the throughput achieved with such codes in the presence of queueing constraints and decoding errors is identified. Performance of different transmission strategies (e.g., variable-rate, variable-power, and fixed-rate transmissions) is studied. Interactions between the throughput, queueing constraints, coding blocklength, decoding error probabilities, and signal-to-noise ratio are investigated and several conclusions with important practical implications are drawn.
Tableaux for the Lambek-Grishin calculus
Venue: arXiv cs.CL 2010
Year: 2010

Categorial type logics, pioneered by Lambek, seek a proof-theoretic understanding of natural language syntax by identifying categories with formulas and derivations with proofs. We typically observe an intuitionistic bias: a structural configuration of hypotheses (a constituent) derives a single conclusion (the category assigned to it). Acting upon suggestions of Grishin to dualize the logical vocabulary, Moortgat proposed the Lambek-Grishin calculus (LG) with the aim of restoring symmetry between hypotheses and conclusions. We develop a theory of labeled modal tableaux for LG, inspired by the interpretation of its connectives as binary modal operators in the relational semantics of Kurtonina and Moortgat. As a linguistic application of our method, we show that grammars based on LG are context-free through use of an interpolation lemma. This result complements that of Melissen, who proved that LG augmented by mixed associativity and -commutativity was exceeds LTAG in expressive power.
Rebuilding for Array Codes in Distributed Storage Systems
Venue: arXiv cs.IT 2010
Year: 2010

In distributed storage systems that use coding, the issue of minimizing the communication required to rebuild a storage node after a failure arises. We consider the problem of repairing an erased node in a distributed storage system that uses an EVENODD code. EVENODD codes are maximum distance separable (MDS) array codes that are used to protect against erasures, and only require XOR operations for encoding and decoding. We show that when there are two redundancy nodes, to rebuild one erased systematic node, only 3/4 of the information needs to be transmitted. Interestingly, in many cases, the required disk I/O is also minimized.
Cooperative Feedback for MIMO Interference Channels
Venue: arXiv cs.IT 2010
Year: 2010

Multi-antenna precoding effectively mitigates the interference in wireless networks. However, the precoding efficiency can be significantly degraded by the overhead due to the required feedback of channel state information (CSI). This paper addresses such an issue by proposing a systematic method of designing precoders for the two-user multiple-input-multiple-output (MIMO) interference channels based on finite-rate CSI feedback from receivers to their interferers, called cooperative feedback. Specifically, each precoder is decomposed into inner and outer precoders for nulling interference and improving the data link array gain, respectively. The inner precoders are further designed to suppress residual interference resulting from finite-rate cooperative feedback. To regulate residual interference due to precoder quantization, additional scalar cooperative feedback signals are designed to control transmitters' power using different criteria including applying interference margins, maximizing sum throughput, and minimizing outage probability. Simulation shows that such additional feedback effectively alleviates performance degradation due to quantized precoder feedback.
Delay Modelling for Single Cell IEEE 802.11 WLANs Using a Random Polling System
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we consider the problem of modelling the average delay experienced by a packet in a single cell IEEE 802.11 DCF wireless local area network. The packet arrival process at each node i is assumed to be Poisson with rate parameter λ_i. Since the nodes are sharing a single channel, they have to contend with one another for a successful transmission. The mean delay for a packet has been approximated by modelling the system as a 1-limited Random Polling system with zero switchover time. We show that even for non-homogeneous packet arrival processes, the mean delay of packets across the queues are same and depends on the system utilization factor and the aggregate throughput of the MAC. Extensive simulations are conducted to verify the analytical results.
Construction of Frequency Hopping Sequence Set Based upon Generalized Cyclotomy
Venue: arXiv cs.IT 2010
Year: 2010

Frequency hopping (FH) sequences play a key role in frequency hopping spread spectrum communication systems. It is important to find FH sequences which have simultaneously good Hamming correlation, large family size and large period. In this paper, a new set of FH sequences with large period is proposed, and the Hamming correlation distribution of the new set is investigated. The construction of new FH sequences is based upon Whiteman's generalized cyclotomy. It is shown that the proposed FH sequence set is optimal with respect to the average Hamming correlation bound.
Influence is a Matter of Degree: New Algorithms for Activation Problems
Venue: arXiv cs.DM 2010
Year: 2010

We consider the target set selection problem. In this problem, a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least $k$ active neighbors ($k$ is identical for all vertices of the graph). Our goal is to find a set of minimum size whose activation will result with the entire graph being activated. Call such a set \emph{contagious}. We prove that if $G=(V,E)$ is an undirected graph, the size of a contagious set is bounded by $\sum_{v\in V}{\min \{1,\frac{k}{d(v)+1}\}}$ (where $d(v)$ is the degree of $v$). We present a simple and efficient algorithm that finds a contagious set that is not larger than the aforementioned bound and discuss algorithmic applications of this algorithm to finding contagious sets in dense graphs.
Structural Learning of Attack Vectors for Generating Mutated XSS Attacks
Venue: arXiv cs.SE 2010
Year: 2010

Web applications suffer from cross-site scripting (XSS) attacks that resulting from incomplete or incorrect input sanitization. Learning the structure of attack vectors could enrich the variety of manifestations in generated XSS attacks. In this study, we focus on generating more threatening XSS attacks for the state-of-the-art detection approaches that can find potential XSS vulnerabilities in Web applications, and propose a mechanism for structural learning of attack vectors with the aim of generating mutated XSS attacks in a fully automatic way. Mutated XSS attack generation depends on the analysis of attack vectors and the structural learning mechanism. For the kernel of the learning mechanism, we use a Hidden Markov model (HMM) as the structure of the attack vector model to capture the implicit manner of the attack vector, and this manner is benefited from the syntax meanings that are labeled by the proposed tokenizing mechanism. Bayes theorem is used to determine the number of hidden states in the model for generalizing the structure model. The paper has the contributions as following: (1) automatically learn the structure of attack vectors from practical data analysis to modeling a structure model of attack vectors, (2) mimic the manners and the elements of attack vectors to extend the ability of testing tool for identifying XSS vulnerabilities, (3) be helpful to verify the flaws of blacklist sanitization procedures of Web applications. We evaluated the proposed mechanism by Burp Intruder with a dataset collected from public XSS archives. The results show that mutated XSS attack generation can identify potential vulnerabilities.
Browser-based Analysis of Web Framework Applications
Venue: arXiv cs.SE 2010
Year: 2010

Although web applications evolved to mature solutions providing sophisticated user experience, they also became complex for the same reason. Complexity primarily affects the server-side generation of dynamic pages as they are aggregated from multiple sources and as there are lots of possible processing paths depending on parameters. Browser-based tests are an adequate instrument to detect errors within generated web pages considering the server-side process and path complexity a black box. However, these tests do not detect the cause of an error which has to be located manually instead. This paper proposes to generate metadata on the paths and parts involved during server-side processing to facilitate backtracking origins of detected errors at development time. While there are several possible points of interest to observe for backtracking, this paper focuses user interface components of web frameworks.
Realizing evaluation strategies by hierarchical graph rewriting
Venue: arXiv cs.LO 2010
Year: 2010

We discuss the realization of evaluation strategies for the concurrent constraint-based functional language CCFL within the translation schemata when compiling CCFL programs into the hierarchical graph rewriting language LMNtal. The support of LMNtal to express local computations and to describe the migration of processes and rules between local computation spaces allows a clear and simple encoding of typical evaluation strategies.
An algorithmic approximation of the infimum reachability probability for Probabilistic Finite Automata
Venue: arXiv cs.LO 2010
Year: 2010

Given a Probabilistic Finite Automata (PFA), a set of states S, and an error threshold e > 0, our algorithm approximates the infimum probability (quantifying over all infinite words) that the automata reaches S. Our result contrasts with the known result that the approximation problem is undecidable if we consider the supremum instead of the infimum. Since we study the probability of reaching a set of states, instead of the probability of ending in an accepting state, our work is more related to model checking than to formal languages.
Approximate Inference and Stochastic Optimal Control
Venue: arXiv cs.LG 2010
Year: 2010

We propose a novel reformulation of the stochastic optimal control problem as an approximate inference problem, demonstrating, that such a interpretation leads to new practical methods for the original problem. In particular we characterise a novel class of iterative solutions to the stochastic optimal control problem based on a natural relaxation of the exact dual formulation. These theoretical insights are applied to the Reinforcement Learning problem where they lead to new model free, off policy methods for discrete and continuous problems.
Optimization of ARQ Protocols in Interference Networks with QoS Constraints
Venue: arXiv cs.SY 2010
Year: 2010

We study optimal transmission strategies in interfering wireless networks, under Quality of Service constraints. A buffered, dynamic network with multiple sources is considered, and sources use a retransmission strategy in order to improve packet delivery probability. The optimization problem is formulated as a Markov Decision Process, where constraints and objective functions are ratios of time-averaged cost functions. The optimal strategy is found as the solution of a Linear Fractional Program, where the optimization variables are the steady-state probability of state-action pairs. Numerical results illustrate the dependence of optimal transmission/interference strategies on the constraints imposed on the network.
Emotional Reactions and the Pulse of Public Opinion: Measuring the Impact of Political Events on the Sentiment of Online Discussions
Venue: arXiv cs.CY 2010
Year: 2010

This paper analyses changes in public opinion by tracking political discussions in which people voluntarily engage online. Unlike polls or surveys, our approach does not elicit opinions but approximates what the public thinks by analysing the discussions in which they decide to take part. We measure the emotional content of online discussions in three dimensions (valence, arousal and dominance), paying special attention to deviation around average values, which we use as a proxy for disagreement and polarisation. We show that this measurement of public opinion helps predict presidential approval rates, suggesting that there is a point of connection between online discussions (often deemed not representative of the overall population) and offline polls. We also show that this measurement provides a deeper understanding of the individual mechanisms that drive aggregated shifts in public opinion. Our data spans a period that includes two US presidential elections, the attacks of September 11, and the start of military action in Afghanistan and Iraq.
Unary Coding for Neural Network Learning
Venue: arXiv cs.NE 2010
Year: 2010

This paper presents some properties of unary coding of significance for biological learning and instantaneously trained neural networks.
Comparative Investigation for Energy Consumption of Different Chipsets Based on Scheduling for Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

Rapid progress in microelectromechanical system (MEMS) and radio frequency (RF) design has enabled the development of low-power, inexpensive, and network-enabled microsensors. These sensor nodes are capable of capturing various physical information, such as temperature, pressure, motion of an object, etc as well as mapping such physical characteristics of the environment to quantitative measurements. A typical wireless sensor network (WSN) consists of hundreds to thousands of such sensor nodes linked by a wireless medium. In this paper, we present a comparative investigation of energy consumption for few commercially available chipsets such as TR1001, CC1000 and CC1010 based on different scheduling methods for two types of deployment strategies. We conducted our experiment within the OMNeT++ simulator.