OpenRaiser/Intern-Atlas huggingface dataset:
Social Networks and Stable Matchings in the Job Market
Venue: arXiv cs.GT 2009
Year: 2009

For most people, social contacts play an integral part in finding a new job. As observed by Granovetter's seminal study, the proportion of jobs obtained through social contacts is usually large compared to those obtained through postings or agencies. At the same time, job markets are a natural example of two-sided matching markets. An important solution concept in such markets is that of stable matchings, and the use of the celebrated Gale-Shapley algorithm to compute them. So far, the literature has evolved separately, either focusing on the implications of information flowing through a social network, or on developing a mathematical theory of job markets through the use of two-sided matching techniques. In this paper we provide a model of the job market that brings both aspects of job markets together. To model the social scientists' observations, we assume that workers learn only about positions in firms through social contacts. Given that information structure, we study both static properties of what we call locally stable matchings (i.e., stable matchings subject to informational constraints given by a social network) and dynamic properties through a reinterpretation of Gale-Shapley's algorithm as myopic best response dynamics. We prove that, in general, the set of locally stable matching strictly contains that of stable matchings and it is in fact NP-complete to determine if they are identical. We also show that the lattice structure of stable matchings is in general absent. Finally, we focus on myopic best response dynamics inspired by the Gale-Shapley algorithm. We study the efficiency loss due to the informational constraints, providing both lower and upper bounds.
Pessimistic Testing
Venue: arXiv cs.SE 2009
Year: 2009

We propose a new approach to testing conformance to a nondeterministic specification, in which testing proceeds only as long as increased test coverage is guaranteed.
Embedding into the rectilinear plane in optimal O*(n^2)
Venue: arXiv cs.CG 2009
Year: 2009

We present an optimal O*(n^2) time algorithm for deciding if a metric space (X,d) on n points can be isometrically embedded into the plane endowed with the l_1-metric. It improves the O*(n^2 log^2 n) time algorithm of J. Edmonds (2008). Together with some ingredients introduced by J. Edmonds, our algorithm uses the concept of tight span and the injectivity of the l_1-plane. A different O*(n^2) time algorithm was recently proposed by D. Eppstein (2009).
Mutual Mobile Membranes with Timers
Venue: arXiv cs.FL 2009
Year: 2009

A feature of current membrane systems is the fact that objects and membranes are persistent. However, this is not true in the real world. In fact, cells and intracellular proteins have a well-defined lifetime. Inspired from these biological facts, we define a model of systems of mobile membranes in which each membrane and each object has a timer representing their lifetime. We show that systems of mutual mobile membranes with and without timers have the same computational power. An encoding of timed safe mobile ambients into systems of mutual mobile membranes with timers offers a relationship between two formalisms used in describing biological systems.
A Constraint-directed Local Search Approach to Nurse Rostering Problems
Venue: arXiv cs.AI 2009
Year: 2009

In this paper, we investigate the hybridization of constraint programming and local search techniques within a large neighbourhood search scheme for solving highly constrained nurse rostering problems. As identified by the research, a crucial part of the large neighbourhood search is the selection of the fragment (neighbourhood, i.e. the set of variables), to be relaxed and re-optimized iteratively. The success of the large neighbourhood search depends on the adequacy of this identified neighbourhood with regard to the problematic part of the solution assignment and the choice of the neighbourhood size. We investigate three strategies to choose the fragment of different sizes within the large neighbourhood search scheme. The first two strategies are tailored concerning the problem properties. The third strategy is more general, using the information of the cost from the soft constraint violations and their propagation as the indicator to choose the variables added into the fragment. The three strategies are analyzed and compared upon a benchmark nurse rostering problem. Promising results demonstrate the possibility of future work in the hybrid approach.
Visual object categorization with new keypoint-based adaBoost features
Venue: arXiv cs.CV 2009
Year: 2009

We present promising results for visual object categorization, obtained with adaBoost using new original ?keypoints-based features?. These weak-classifiers produce a boolean response based on presence or absence in the tested image of a ?keypoint? (a kind of SURF interest point) with a descriptor sufficiently similar (i.e. within a given distance) to a reference descriptor characterizing the feature. A first experiment was conducted on a public image dataset containing lateral-viewed cars, yielding 95% recall with 95% precision on test set. Preliminary tests on a small subset of a pedestrians database also gives promising 97% recall with 92 % precision, which shows the generality of our new family of features. Moreover, analysis of the positions of adaBoost-selected keypoints show that they correspond to a specific part of the object category (such as ?wheel? or ?side skirt? in the case of lateral-cars) and thus have a ?semantic? meaning. We also made a first test on video for detecting vehicles from adaBoostselected keypoints filtered in real-time from all detected keypoints.
Simpler Proofs by Symbolic Perturbation
Venue: arXiv cs.DS 2009
Year: 2009

In analyses of algorithms, a substantial amount of effort has often to be spent on the discussion of special cases. For example, when the analysis considers the cases X<Y and X>Y separately, one might have to be especially careful about what happens when X=Y. On the other hand, experience tells us that when a yet unregarded special case of this kind is discovered, one nearly always finds a way to handle it. This is typically done by modifying the analysis and/or the algorithm very slightly. In this article we substantiate this observation theoretically. We concentrate on deterministic algorithms for weighted combinatorial optimization problems. A problem instance of this kind is defined by its structure and a vector of weights. The concept of a null case is introduced as set of problem instances whose weight vectors constitute a nowhere open set (or null set) in the space of all possible weight configurations. An algorithm is called robust if any null case can be disregarded in the analysis of both its solution quality and resource requirements. We show that achieving robustness is only a matter of breaking ties the right way. More specifically, we show that the concept of symbolic perturbation known from the area of geometric algorithms guarantees that no surprises will happen in null cases. We argue that for a huge class of combinatorial optimization algorithms it is easy to verify that they implicitly use symbolic perturbation for breaking ties and thus can be analyzed under the assumption that some arbitrary null case never occurs. Finally, we prove that there exists a symbolic perturbation tie breaking policy for any algorithm.
Capacity Bounds for Two-Hop Interference Networks
Venue: arXiv cs.IT 2009
Year: 2009

This paper considers a two-hop interference network, where two users transmit independent messages to their respective receivers with the help of two relay nodes. The transmitters do not have direct links to the receivers; instead, two relay nodes serve as intermediaries between the transmitters and receivers. Each hop, one from the transmitters to the relays and the other from the relays to the receivers, is modeled as a Gaussian interference channel, thus the network is essentially a cascade of two interference channels. For this network, achievable symmetric rates for different parameter regimes under decode-and- forward relaying and amplify-and-forward relaying are proposed and the corresponding coding schemes are carefully studied. Numerical results are also provided.
Justifying additive-noise-model based causal discovery via algorithmic information theory
Venue: arXiv cs.IT 2009
Year: 2009

A recent method for causal discovery is in many cases able to infer whether X causes Y or Y causes X for just two observed variables X and Y. It is based on the observation that there exist (non-Gaussian) joint distributions P(X,Y) for which Y may be written as a function of X up to an additive noise term that is independent of X and no such model exists from Y to X. Whenever this is the case, one prefers the causal model X--> Y. Here we justify this method by showing that the causal hypothesis Y--> X is unlikely because it requires a specific tuning between P(Y) and P(X|Y) to generate a distribution that admits an additive noise model from X to Y. To quantify the amount of tuning required we derive lower bounds on the algorithmic information shared by P(Y) and P(X|Y). This way, our justification is consistent with recent approaches for using algorithmic information theory for causal reasoning. We extend this principle to the case where P(X,Y) almost admits an additive noise model. Our results suggest that the above conclusion is more reliable if the complexity of P(Y) is high.
Circular tests for HSM machine tools: Bore machining application
Venue: arXiv cs.RO 2009
Year: 2009

Today's High-Speed Machining (HSM) machine tool combines productivity and part quality. The difficulty inherent in HSM operations lies in understanding the impact of machine tool behaviour on machining time and part quality. Analysis of some of the relevant ISO standards (230-1998, 10791-1998) and a complementary protocol for better understanding HSM technology are presented in the first part of this paper. These ISO standards are devoted to the procedures implemented in order to study the behavior of machine tool. As these procedures do not integrate HSM technology, the need for HSM machine tool tests becomes critical to improving the trade-off between machining time and part quality. A new protocol for analysing the HSM technology impact during circular interpolation is presented in the second part of the paper. This protocol which allows evaluating kinematic machine tool behaviour during circular interpolation was designed from tests without machining. These tests are discussed and their results analysed in the paper. During the circular interpolation, axis capacities (such as acceleration or Jerk) related to certain setting parameters of the numerical control unit have a significant impact on the value of the feed rate. Consequently, a kinematic model for a circular-interpolated trajectory was developed on the basis of these parameters. Moreover, the link between part accuracy and kinematic machine tool behaviour was established. The kinematic model was ultimately validated on a bore machining simulation.
The intersection of two halfspaces has high threshold degree
Venue: arXiv cs.CC 2009
Year: 2009

The threshold degree of a Boolean function f:{0,1}^n->{-1,+1} is the least degree of a real polynomial p such that f(x)=sgn p(x). We construct two halfspaces on {0,1}^n whose intersection has threshold degree Theta(sqrt n), an exponential improvement on previous lower bounds. This solves an open problem due to Klivans (2002) and rules out the use of perceptron-based techniques for PAC learning the intersection of two halfspaces, a central unresolved challenge in computational learning. We also prove that the intersection of two majority functions has threshold degree Omega(log n), which is tight and settles a conjecture of O'Donnell and Servedio (2003). Our proof consists of two parts. First, we show that for any nonconstant Boolean functions f and g, the intersection f(x)^g(y) has threshold degree O(d) if and only if ||f-F||_infty + ||g-G||_infty < 1 for some rational functions F, G of degree O(d). Second, we settle the least degree required for approximating a halfspace and a majority function to any given accuracy by rational functions. Our technique further allows us to make progress on Aaronson's challenge (2008) and contribute strong direct product theorems for polynomial representations of composed Boolean functions of the form F(f_1,...,f_n). In particular, we give an improved lower bound on the approximate degree of the AND-OR tree.
Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property
Venue: arXiv cs.IT 2009
Year: 2009

Compressed Sensing aims to capture attributes of $k$-sparse signals using very few measurements. In the standard Compressed Sensing paradigm, the $\m\times \n$ measurement matrix $\A$ is required to act as a near isometry on the set of all $k$-sparse signals (Restricted Isometry Property or RIP). Although it is known that certain probabilistic processes generate $\m \times \n$ matrices that satisfy RIP with high probability, there is no practical algorithm for verifying whether a given sensing matrix $\A$ has this property, crucial for the feasibility of the standard recovery algorithms. In contrast this paper provides simple criteria that guarantee that a deterministic sensing matrix satisfying these criteria acts as a near isometry on an overwhelming majority of $k$-sparse signals; in particular, most such signals have a unique representation in the measurement domain. Probability still plays a critical role, but it enters the signal model rather than the construction of the sensing matrix. We require the columns of the sensing matrix to form a group under pointwise multiplication. The construction allows recovery methods for which the expected performance is sub-linear in $\n$, and only quadratic in $\m$; the focus on expected performance is more typical of mainstream signal processing than the worst-case analysis that prevails in standard Compressed Sensing. Our framework encompasses many families of deterministic sensing matrices, including those formed from discrete chirps, Delsarte-Goethals codes, and extended BCH codes.
Modulation Codes for Flash Memory Based on Load-Balancing Theory
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider modulation codes for practical multilevel flash memory storage systems with cell levels. Instead of maximizing the lifetime of the device [Ajiang-isit07-01, Ajiang-isit07-02, Yaakobi_verdy_siegel_wolf_allerton08, Finucane_Liu_Mitzenmacher_aller08], we maximize the average amount of information stored per cell-level, which is defined as storage efficiency. Using this framework, we show that the worst-case criterion [Ajiang-isit07-01, Ajiang-isit07-02, Yaakobi_verdy_siegel_wolf_allerton08] and the average-case criterion [Finucane_Liu_Mitzenmacher_aller08] are two extreme cases of our objective function. A self-randomized modulation code is proposed which is asymptotically optimal, as, for an arbitrary input alphabet and i.i.d. input distribution. In practical flash memory systems, the number of cell-levels is only moderately large. So the asymptotic performance as may not tell the whole story. Using the tools from load-balancing theory, we analyze the storage efficiency of the self-randomized modulation code. The result shows that only a fraction of the cells are utilized when the number of cell-levels is only moderately large. We also propose a load-balancing modulation code, based on a phenomenon known as "the power of two random choices" [Mitzenmacher96thepower], to improve the storage efficiency of practical systems. Theoretical analysis and simulation results show that our load-balancing modulation codes can provide significant gain to practical flash memory storage systems. Though pseudo-random, our approach achieves the same load-balancing performance, for i.i.d. inputs, as a purely random approach based on the power of two random choices.
A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP
Venue: arXiv cs.DS 2009
Year: 2009

We show that the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem with general demands has integrality gap $(\log n)^{Ω(1)}$. This is achieved by exhibiting $n$-point metric spaces of negative type whose $L_1$ distortion is $(\log n)^{Ω(1)}$. Our result is based on quantitative bounds on the rate of degeneration of Lipschitz maps from the Heisenberg group to $L_1$ when restricted to cosets of the center.
A Framework For Intelligent Multi Agent System Based Neural Network Classification Model
Venue: arXiv cs.NE 2009
Year: 2009

TIntelligent multi agent systems have great potentials to use in different purposes and research areas. One of the important issues to apply intelligent multi agent systems in real world and virtual environment is to develop a framework that support machine learning model to reflect the whole complexity of the real world. In this paper, we proposed a framework of intelligent agent based neural network classification model to solve the problem of gap between two applicable flows of intelligent multi agent technology and learning model from real environment. We consider the new Supervised Multilayers Feed Forward Neural Network (SMFFNN) model as an intelligent classification for learning model in the framework. The framework earns the information from the respective environment and its behavior can be recognized by the weights. Therefore, the SMFFNN model that lies in the framework will give more benefits in finding the suitable information and the real weights from the environment which result for better recognition. The framework is applicable to different domains successfully and for the potential case study, the clinical organization and its domain is considered for the proposed framework
The Role of Spreadsheets in the Allied Irish Bank / Allfirst Currency Trading Fraud
Venue: arXiv cs.CY 2009
Year: 2009

This brief paper outlines how spreadsheets were used as one of the vehicles for John Rusnak's fraud and the revenue control lessons this case gives us.
A real world network pricing game with less severe Braess' Paradox
Venue: arXiv cs.GT 2009
Year: 2009

Internet and graphs are very much related. The graphical structure of internet has been studied extensively to provide efficient solutions to routing and other problems. But most of these studies assume a central authority which controls and manages the internet. In the recent years game theoretic models have been proposed which do not require a central authority and the users are assumed to be routing their flows selfishly. The existence of Nash Equilibria, congestion and the amount of inefficiency caused by this selfish routing is a major concern in this field. A type of paradox in the selfish routing networks, Braess' Paradox, first discovered by Braess, is a major contributor to inefficiency. Several pricing mechanisms have also been provided which give a game theoretical model between users(consumers) and ISPs ({Internet Service Providers} or sellers) for the internet. We propose a novel pricing mechanism, based on real world Internet network architecture, which reduces the severity of Braess' Paradox in selfish routing game theoretic networks. It's a pricing mechanism between combinatorial users and ISPs. We prove that Nash equilibria exists in this network and provide bounds on inefficiency . We use graphical properties of internet to prove our result. Several interesting extensions and future work have also been discussed.
Assessment of a percutaneous iliosacral screw insertion simulator
Venue: arXiv cs.OH 2009
Year: 2009

BACKGROUND: Navigational simulator use for specialized training purposes is rather uncommon in orthopaedic and trauma surgery. However, it reveals providing a valuable tool to train orthopaedic surgeons and help them to plan complex surgical procedures. PURPOSE: This work's objective was to assess educational efficiency of a path simulator under fluoroscopic guidance applied to sacroiliac joint percutaneous screw fixation. MATERIALS AND METHODS: We evaluated 23 surgeons' accuracy inserting a guide-wire in a human cadaver experiment, following a pre-established procedure. These medical trainees were defined in three prospective respects: novice or skilled; with or without theoretical knowledge; with or without surgical procedure familiarity. Analysed criteria for each tested surgeon included the number of intraoperative X-rays taken in order to achieve the surgical procedure as well as an iatrogenic index reflecting the surgeon's ability to detect any hazardous trajectory at the time of performing said procedure. RESULTS: An average number of 13 X-rays was required for wire implantation by the G1 group. G2 group, assisted by the simulator use, required an average of 10 X-rays. A substantial difference was especially observed within the novice sub-group (N), with an average of 12.75 X-rays for the G1 category and an average of 8.5 X-rays for the G2 category. As far as the iatrogenic index is concerned, we were unable to observe any significant difference between the groups.
Searching for Minimum Storage Regenerating Codes
Venue: arXiv cs.IT 2009
Year: 2009

Regenerating codes allow distributed storage systems to recover from the loss of a storage node while transmitting the minimum possible amount of data across the network. We present a systematic computer search for optimal systematic regenerating codes. To search the space of potential codes, we reduce the potential search space in several ways. We impose an additional symmetry condition on codes that we consider. We specify codes in a simple alternative way, using additional recovered coefficients rather than transmission coefficients and place codes into equivalence classes to avoid redundant checking. Our main finding is a few optimal systematic minimum storage regenerating codes for $n=5$ and $k=3$, over several finite fields. No such codes were previously known and the matching of the information theoretic cut-set bound was an open problem.
A Component Based Heuristic Search Method with Evolutionary Eliminations
Venue: arXiv cs.AI 2009
Year: 2009

Nurse rostering is a complex scheduling problem that affects hospital personnel on a daily basis all over the world. This paper presents a new component-based approach with evolutionary eliminations, for a nurse scheduling problem arising at a major UK hospital. The main idea behind this technique is to decompose a schedule into its components (i.e. the allocated shift pattern of each nurse), and then to implement two evolutionary elimination strategies mimicking natural selection and natural mutation process on these components respectively to iteratively deliver better schedules. The worthiness of all components in the schedule has to be continuously demonstrated in order for them to remain there. This demonstration employs an evaluation function which evaluates how well each component contributes towards the final objective. Two elimination steps are then applied: the first elimination eliminates a number of components that are deemed not worthy to stay in the current schedule; the second elimination may also throw out, with a low level of probability, some worthy components. The eliminated components are replenished with new ones using a set of constructive heuristics using local optimality criteria. Computational results using 52 data instances demonstrate the applicability of the proposed approach in solving real-world problems.