OpenRaiser/Intern-Atlas huggingface dataset:
On the Complexity of the Multivariate Resultant
Venue: arXiv cs.CC 2012
Year: 2012

The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of n homogeneous equations in n variables is satisfiable (the resultant is a polynomial in the system's coefficients which vanishes if and only if the system is satisfiable). In this paper, we investigate the complexity of computing the multivariate resultant. First, we study the complexity of testing the multivariate resultant for zero. Our main result is that this problem is NP-hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). In characteristic zero, we observe that this problem is in the Arthur-Merlin class AM if the generalized Riemann hypothesis holds true, while the best known upper bound in positive characteristic remains PSPACE. Second, we study the classical algorithms to compute the resultant. They usually rely on the computation of the determinant of an exponential-size matrix, known as Macaulay matrix. We show that this matrix belongs to a class of succinctly representable matrices, for which testing the determinant for zero is proved PSPACE-complete. This means that improving Canny's PSPACE upper bound requires either to look at the fine structure of the Macaulay matrix to find an ad hoc algorithm for computing its determinant, or to use altogether different techniques.
Clinching Auctions with Online Supply
Venue: arXiv cs.GT 2012
Year: 2012

Auctions for perishable goods such as internet ad inventory need to make real-time allocation and pricing decisions as the supply of the good arrives in an online manner, without knowing the entire supply in advance. These allocation and pricing decisions get complicated when buyers have some global constraints. In this work, we consider a multi-unit model where buyers have global {\em budget} constraints, and the supply arrives in an online manner. Our main contribution is to show that for this setting there is an individually-rational, incentive-compatible and Pareto-optimal auction that allocates these units and calculates prices on the fly, without knowledge of the total supply. We do so by showing that the Adaptive Clinching Auction satisfies a {\em supply-monotonicity} property. We also analyze and discuss, using examples, how the insights gained by the allocation and payment rule can be applied to design better ad allocation heuristics in practice. Finally, while our main technical result concerns multi-unit supply, we propose a formal model of online supply that captures scenarios beyond multi-unit supply and has applications to sponsored search. We conjecture that our results for multi-unit auctions can be extended to these more general models.
Symbolic Planning and Control Using Game Theory and Grammatical Inference
Venue: arXiv cs.RO 2012
Year: 2012

This paper presents an approach that brings together game theory with grammatical inference and discrete abstractions in order to synthesize control strategies for hybrid dynamical systems performing tasks in partially unknown but rule-governed adversarial environments. The combined formulation guarantees that a system specification is met if (a) the true model of the environment is in the class of models inferable from a positive presentation, (b) a characteristic sample is observed, and (c) the task specification is satisfiable given the capabilities of the system (agent) and the environment.
Design and Characterization of a Full-duplex Multi-antenna System for WiFi networks
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we present an experimental and simulation based study to evaluate the use of full-duplex as a mode in practical IEEE 802.11 networks. To enable the study, we designed a 20 MHz multi-antenna OFDM full-duplex physical layer and a full-duplex capable MAC protocol which is backward compatible with current 802.11. Our extensive over-the-air experiments, simulations and analysis demonstrate the following two results. First, the use of multiple antennas at the physical layer leads to a higher ergodic throughput than its hardware-equivalent multi-antenna half-duplex counterparts, for SNRs above the median SNR encountered in practical WiFi deployments. Second, the proposed MAC translates the physical layer rate gain into near doubling of throughput for multi-node single-AP networks. The two combined results allow us to conclude that there are potentially significant benefits gained from including a full-duplex mode in future WiFi standards.
Formats over Time: Exploring UK Web History
Venue: arXiv cs.DL 2012
Year: 2012

Is software obsolescence a significant risk? To explore this issue, we analysed a corpus of over 2.5 billion resources corresponding to the UK Web domain, as crawled between 1996 and 2010. Using the DROID and Apache Tika identification tools, we examined each resource and captured the results as extended MIME types, embedding version, software and hardware identifiers alongside the format information. The combined results form a detailed temporal format profile of the corpus, which we have made available as open data. We present the results of our initial analysis of this dataset. We look at image, HTML and PDF resources in some detail, showing how the usage of different formats, versions and software implementations has changed over time. Furthermore, we show that software obsolescence is rare on the web and uncover evidence indicating that network effects act to stabilise formats against obsolescence.
Providing an Object Allocation Algorithm in Distributed Databases Using Efficient Factors
Venue: arXiv cs.DB 2012
Year: 2012

Data replication is a common method used to improve the performance of data access in distributed database systems. In this paper, we present an object replication algorithm in distributed database systems (ORAD). We optimize the created replicated data in distributed database systems by using activity functions of previous algorithms, changing them with new technical ways and applying ORAD algorithm for making decisions. We propose ORAD algorithm with using effective factors and observe its results in several valid situations. Our objective is to propose an optimum method that replies read and write requests with less cost in distributed database systems. Finally, we implement ORAD and ADRW algorithms in a PC based network system and demonstrate that ORAD algorithm is superior to ADRW algorithm in the field of average request servicing cost.
An efficient algorithm for estimating state sequences in imprecise hidden Markov models
Venue: arXiv cs.AI 2012
Year: 2012

We present an efficient exact algorithm for estimating state sequences from outputs (or observations) in imprecise hidden Markov models (iHMM), where both the uncertainty linking one state to the next, and that linking a state to its output, are represented using coherent lower previsions. The notion of independence we associate with the credal network representing the iHMM is that of epistemic irrelevance. We consider as best estimates for state sequences the (Walley--Sen) maximal sequences for the posterior joint state model conditioned on the observed output sequence, associated with a gain function that is the indicator of the state sequence. This corresponds to (and generalises) finding the state sequence with the highest posterior probability in HMMs with precise transition and output probabilities (pHMMs). We argue that the computational complexity is at worst quadratic in the length of the Markov chain, cubic in the number of states, and essentially linear in the number of maximal state sequences. For binary iHMMs, we investigate experimentally how the number of maximal state sequences depends on the model parameters. We also present a simple toy application in optical character recognition, demonstrating that our algorithm can be used to robustify the inferences made by precise probability models.
A comparative study on face recognition techniques and neural network
Venue: arXiv cs.CV 2012
Year: 2012

In modern times, face recognition has become one of the key aspects of computer vision. There are at least two reasons for this trend; the first is the commercial and law enforcement applications, and the second is the availability of feasible technologies after years of research. Due to the very nature of the problem, computer scientists, neuro-scientists and psychologists all share a keen interest in this field. In plain words, it is a computer application for automatically identifying a person from a still image or video frame. One of the ways to accomplish this is by comparing selected features from the image and a facial database. There are hundreds if not thousand factors associated with this. In this paper some of the most common techniques available including applications of neural network in facial recognition are studied and compared with respect to their performance.
Saddle-Node Bifurcation Associated with Parasitic Inductor Resistance in Boost Converters
Venue: arXiv cs.SY 2012
Year: 2012

Saddle-node bifurcation occurs in a boost converter when parasitic inductor resistance is modeled. Closed-form critical conditions of the bifurcation are derived. If the parasitic inductor resistance is modeled, the saddle-node bifurcation occurs in the voltage mode control or in the current mode control with the voltage loop closed, but not in the current mode control with the voltage loop open. If the parasitic inductor resistance is not modeled, the saddle-node bifurcation does not occur, and one may be misled by the wrong dynamics and the wrong steady-state solutions. The saddle-node bifurcation still exists even in a boost converter with a popular type-III compensator. When the saddle-node bifurcation occurs, multiple steady-state solutions may coexist. The converter may operate with a voltage jump from one solution to another. Care should be taken in the compensator design to ensure that only the desired solution is stabilized. In industry practice, the solution with a higher duty cycle (and thus the saddle-node bifurcation) may be prevented by placing a limitation on the maximum duty cycle.
Modeling and Instability of Average Current Control
Venue: arXiv cs.SY 2012
Year: 2012

Dynamics and stability of average current control of DC-DC converters are analyzed by sampled-data modeling. Orbital stability is studied and it is found unrelated to the ripple size of the orbit. Compared with the averaged modeling, the sampled-data modeling is more accurate and systematic. An unstable range of compensator pole is found by simulations, and is predicted by sampled-data modeling and harmonic balance modeling.
Reply to Comments on Neuroelectrodynamics: Where are the Real Conceptual Pitfalls?
Venue: arXiv cs.NE 2012
Year: 2012

The fundamental, powerful process of computation in the brain has been widely misunderstood. The paper [1] associates the general failure to build intelligent thinking machines with current reductionist principles of temporal coding and advocates for a change in paradigm regarding the brain analogy. Since fragments of information are stored in proteins which can shift between several structures to perform their function, the biological substrate is actively involved in physical computation. The intrinsic nonlinear dynamics of action potentials and synaptic activities maintain physical interactions within and between neurons in the brain. During these events the required information is exchanged between molecular structures (proteins) which store fragments of information and the generated electric flux which carries and integrates information in the brain. The entire process of physical interaction explains how the brain actively creates or experiences meaning. This process of interaction during an action potential generation can be simply seen as the moment when the neuron solves a many-body problem. A neuroelectrodynamic theory shows that the neuron solves equations rather than exclusively computes functions. With the main focus on temporal patterns, the spike timing dogma (STD) has neglected important forms of computation which do occur inside neurons. In addition, artificial neural models have missed the most important part since the real super-computing power of the brain has its origins in computations that occur within neurons.
Diagrammatization of the Transmission Control Protocol
Venue: arXiv cs.NI 2012
Year: 2012

With the wide spread of Internet services, developers and users need a greater understanding of the technology of networking. Acquiring a clear understanding of communication protocols is an important step in understanding how a network functions; however, many protocols are complicated, and explaining them can be demanding. In addition, protocols are often explained in terms of traffic analysis and oriented toward technical staff and those already familiar with network protocols. This paper aims at proposing a diagrammatic methodology to represent protocols in general, with a focus on the Transmission Control Protocol and Secure Sockets Layer in particular. The purpose is to facilitate understanding of protocols for learning and communication purposes. The methodology is based on the notion of flow of primitive things in a system with six stages: creation, release, transfer, arrival, acceptance, and processing. Though the method presents a basic description of protocols without in-depth analysis of all aspects and mechanisms, the resultant conceptual description is a systematic specification that utilizes a few basic notions that assist in illustrating functionality and support comprehension.
Discrete Dithered Desynchronization
Venue: arXiv cs.NI 2012
Year: 2012

This paper introduces the Discrete Dithered Desynchronization (D3sync) algorithm which is a decentralized Time Division Multiple Access (TDMA) technique in which a set of network nodes computes iteratively a conflict-free schedule so that each node obtains a portion of a frame that is an integer multiple of a fixed slot size. The algorithm is inspired by the dynamics of Pulse Coupled Oscillators (PCO), but unlike its predecessors that divide arbitrarily the frame among the nodes in the network, the D3sync allocates discrete resources among the network nodes. Our paper proves the convergence of the D3sync algorithm and gives an upper bound on the convergence time of the algorithm.
Privacy Against Statistical Inference
Venue: arXiv cs.IT 2012
Year: 2012

We propose a general statistical inference framework to capture the privacy threat incurred by a user that releases data to a passive but curious adversary, given utility constraints. We show that applying this general framework to the setting where the adversary uses the self-information cost function naturally leads to a non-asymptotic information-theoretic approach for characterizing the best achievable privacy subject to utility constraints. Based on these results we introduce two privacy metrics, namely average information leakage and maximum information leakage. We prove that under both metrics the resulting design problem of finding the optimal mapping from the user's data to a privacy-preserving output can be cast as a modified rate-distortion problem which, in turn, can be formulated as a convex program. Finally, we compare our framework with differential privacy.
The Enemy Within: The Emerging Threats to Healthcare from Malicious Mobile Devices
Venue: arXiv cs.CR 2012
Year: 2012

With the proliferation of wireless networks, mobile devices and medical devices are increasingly being equipped with wireless interfaces, such as Bluetooth and WiFi to allow easy access to and control of the medical devices. Unfortunately, the very presence and usage of such interfaces also expose the medical devices to novel attacks from malicious parties. The emerging threat from malicious mobile devices is significant and severe, since attackers can steal confidential data from a patient's medical device. Also, attackers can compromise the medical device and either feed doctors bad data from it or issue potentially fatal commands to the device, which may even result in the death of the patient. As the mobile devices are often at close proximity to the patient (either in the hospital or home settings), attacks from such devices are hard to prevent. In this paper, we present a systematic analysis of this new threat from mobile devices on medical devices and healthcare infrastructure. We also perform a thorough security analysis of a major hospital and uncover potential vulnerabilities. Finally, we propose a set of potential solutions and defenses against such attacks.
Strong Coordination with Polar Codes
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we design explicit codes for strong coordination in two-node networks. Specifically, we consider a two-node network in which the action imposed by nature is binary and uniform, and the action to coordinate is obtained via a symmetric discrete memoryless channel. By observing that polar codes are useful for channel resolvability over binary symmetric channels, we prove that nested polar codes achieve a subset of the strong coordination capacity region, and therefore provide a constructive and low complexity solution for strong coordination.
Semisupervised Classifier Evaluation and Recalibration
Venue: arXiv cs.LG 2012
Year: 2012

How many labeled examples are needed to estimate a classifier's performance on a new dataset? We study the case where data is plentiful, but labels are expensive. We show that by making a few reasonable assumptions on the structure of the data, it is possible to estimate performance curves, with confidence bounds, using a small number of ground truth labels. Our approach, which we call Semisupervised Performance Evaluation (SPE), is based on a generative model for the classifier's confidence scores. In addition to estimating the performance of classifiers on new datasets, SPE can be used to recalibrate a classifier by re-estimating the class-conditional confidence distributions.
Annotating Answer-Set Programs in LANA?
Venue: arXiv cs.SE 2012
Year: 2012

While past research in answer-set programming (ASP) mainly focused on theory, ASP solver technology, and applications, the present work situates itself in the context of a quite recent research trend: development support for ASP. In particular, we propose to augment answer-set programs with additional meta-information formulated in a dedicated annotation language, called LANA. This language allows the grouping of rules into coherent blocks and to specify language signatures, types, pre- and postconditions, as well as unit tests for such blocks. While these annotations are invisible to an ASP solver, as they take the form of program comments, they can be interpreted by tools for documentation, testing, and verification purposes, as well as to eliminate sources of common programming errors by realising syntax checking or code completion features. To demonstrate its versatility, we introduce two such tools, viz. (i) ASPDOC, for generating an HTML documentation for a program based on the annotated information, and (ii) ASPUNIT, for running and monitoring unit tests on program blocks. LANA is also exploited in the SeaLion system, an integrated development environment for ASP based on Eclipse. To appear in Theory and Practice of Logic Programming
Extensions of the Minimum Cost Homomorphism Problem
Venue: arXiv cs.CC 2012
Year: 2012

Assume $D$ is a finite set and $R$ is a finite set of functions from $D$ to the natural numbers. An instance of the minimum $R$-cost homomorphism problem ($MinHom_R$) is a set of variables $V$ subject to specified constraints together with a positive weight $c_{vr}$ for each combination of $v \in V$ and $r \in R$. The aim is to find a function $f:V \rightarrow D$ such that $f$ satisfies all constraints and $\sum_{v \in V} \sum_{r \in R} c_{vr}r(f(v))$ is minimized. This problem unifies well-known optimization problems such as the minimum cost homomorphism problem and the maximum solution problem, and this makes it a computationally interesting fragment of the valued CSP framework for optimization problems. We parameterize $MinHom_R\left(Γ\right)$ by {\em constraint languages}, i.e. sets $Γ$ of relations that are allowed in constraints. A constraint language is called {\em conservative} if every unary relation is a member of it; such constraint languages play an important role in understanding the structure of constraint problems. The dichotomy conjecture for $MinHom_R$ is the following statement: if $Γ$ is a constraint language, then $MinHom_R\left(Γ\right)$ is either polynomial-time solvable or NP-complete. For $MinHom$ the dichotomy result has been recently obtained [Takhanov, STACS, 2010] and the goal of this paper is to expand this result to the case of $MinHom_R$ with conservative constraint language. For arbitrary $R$ this problem is still open, but assuming certain restrictions on $R$ we prove a dichotomy. As a consequence of this result we obtain a dichotomy for the conservative maximum solution problem.
Simulated Tom Thumb, the Rule Of Thumb for Autonomous Robots
Venue: arXiv cs.RO 2012
Year: 2012

For a mobile robot to be truly autonomous, it must solve the simultaneous localization and mapping (SLAM) problem. We develop a new metaheuristic algorithm called Simulated Tom Thumb (STT), based on the detailed adventure of the clever Tom Thumb and advances in researches relating to path planning based on potential functions. Investigations show that it is very promising and could be seen as an optimization of the powerful solution of SLAM with data association and learning capabilities. STT outperform JCBB. The performance is 100 % match.
Symbolic Representation of Algorithmic Game Semantics
Venue: arXiv cs.FL 2012
Year: 2012

In this paper we revisit the regular-language representation of game semantics of second-order recursion free Idealized Algol with infinite data types. By using symbolic values instead of concrete ones we generalize the standard notion of regular-language and automata representations to that of corresponding symbolic representations. In this way terms with infinite data types, such as integers, can be expressed as finite symbolic-automata although the standard automata interpretation is infinite. Moreover, significant reductions of the state space of game semantics models are obtained. This enables efficient verification of terms, which is illustrated with several examples.
The μ-Calculus Alternation Hierarchy Collapses over Structures with Restricted Connectivity
Venue: arXiv cs.LO 2012
Year: 2012

It is known that the alternation hierarchy of least and greatest fixpoint operators in the mu-calculus is strict. However, the strictness of the alternation hierarchy does not necessarily carry over when considering restricted classes of structures. A prominent instance is the class of infinite words over which the alternation-free fragment is already as expressive as the full mu-calculus. Our current understanding of when and why the mu-calculus alternation hierarchy is not strict is limited. This paper makes progress in answering these questions by showing that the alternation hierarchy of the mu-calculus collapses to the alternation-free fragment over some classes of structures, including infinite nested words and finite graphs with feedback vertex sets of a bounded size. Common to these classes is that the connectivity between the components in a structure from such a class is restricted in the sense that the removal of certain vertices from the structure's graph decomposes it into graphs in which all paths are of finite length. Our collapse results are obtained in an automata-theoretic setting. They subsume, generalize, and strengthen several prior results on the expressivity of the mu-calculus over restricted classes of structures.