OpenRaiser/Intern-Atlas huggingface dataset:
Measuring the Meaning of Words in Contexts: An automated analysis of controversies about Monarch butterflies, Frankenfoods, and stem cells
Venue: arXiv cs.CL 2009
Year: 2009

Co-words have been considered as carriers of meaning across different domains in studies of science, technology, and society. Words and co-words, however, obtain meaning in sentences, and sentences obtain meaning in their contexts of use. At the science/society interface, words can be expected to have different meanings: the codes of communication that provide meaning to words differ on the varying sides of the interface. Furthermore, meanings and interfaces may change over time. Given this structuring of meaning across interfaces and over time, we distinguish between metaphors and diaphors as reflexive mechanisms that facilitate the translation between contexts. Our empirical focus is on three recent scientific controversies: Monarch butterflies, Frankenfoods, and stem-cell therapies. This study explores new avenues that relate the study of co-word analysis in context with the sociological quest for the analysis and processing of meaning.
Classification and Powerlaws: The Logarithmic Transformation
Venue: arXiv cs.IR 2009
Year: 2009

Logarithmic transformation of the data has been recommended by the literature in the case of highly skewed distributions such as those commonly found in information science. The purpose of the transformation is to make the data conform to the lognormal law of error for inferential purposes. How does this transformation affect the analysis? We factor analyze and visualize the citation environment of the Journal of the American Chemical Society (JACS) before and after a logarithmic transformation. The transformation strongly reduces the variance necessary for classificatory purposes and therefore is counterproductive to the purposes of the descriptive statistics. We recommend against the logarithmic transformation when sets cannot be defined unambiguously. The intellectual organization of the sciences is reflected in the curvilinear parts of the citation distributions, while negative powerlaws fit excellently to the tails of the distributions.
Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness
Venue: arXiv cs.CC 2009
Year: 2009

We study the computational power of polynomial threshold functions, that is, threshold functions of real polynomials over the boolean cube. We provide two new results bounding the computational power of this model. Our first result shows that low-degree polynomial threshold functions cannot approximate any function with many influential variables. We provide a couple of examples where this technique yields tight approximation bounds. Our second result relates to constructing pseudorandom generators fooling low-degree polynomial threshold functions. This problem has received attention recently, where Diakonikolas et al proved that $k$-wise independence suffices to fool linear threshold functions. We prove that any low-degree polynomial threshold function, which can be represented as a function of a small number of linear threshold functions, can also be fooled by $k$-wise independence. We view this as an important step towards fooling general polynomial threshold functions, and we discuss a plausible approach achieving this goal based on our techniques. Our results combine tools from real approximation theory, hyper-contractive inequalities and probabilistic methods. In particular, we develop several new tools in approximation theory which may be of independent interest.
AnAmeter: The First Steps to Evaluating Adaptation
Venue: arXiv cs.HC 2009
Year: 2009

This paper presents the online AnAmeter framework that helps characterize the different types of adaptations a system features by helping the evaluator fill in a simple form. The provided information is then processed to obtain a quantitative evaluation of three parameters called global, semi-global and local adaptation degrees. By characterizing and quantifying adaptation, AnAmeter provides the first steps towards the evaluation of the quality of a system's adaptation. AnAmeter is an open tool available as freeware on the web and has been applied to a selection of well known systems. To build this evaluation grid we also collected a number of systems that cover the full range of adaptation types.
Artificial Neural Network-based error compensation procedure for low-cost encoders
Venue: arXiv cs.NE 2009
Year: 2009

An Artificial Neural Network-based error compensation method is proposed for improving the accuracy of resolver-based 16-bit encoders by compensating for their respective systematic error profiles. The error compensation procedure, for a particular encoder, involves obtaining its error profile by calibrating it on a precision rotary table, training the neural network by using a part of this data and then determining the corrected encoder angle by subtracting the ANN-predicted error from the measured value of the encoder angle. Since it is not guaranteed that all the resolvers will have exactly similar error profiles because of the inherent differences in their construction on a micro scale, the ANN has been trained on one error profile at a time and the corresponding weight file is then used only for compensating the systematic error of this particular encoder. The systematic nature of the error profile for each of the encoders has also been validated by repeated calibration of the encoders over a period of time and it was found that the error profiles of a particular encoder recorded at different epochs show near reproducible behavior. The ANN-based error compensation procedure has been implemented for 4 encoders by training the ANN with their respective error profiles and the results indicate that the accuracy of encoders can be improved by nearly an order of magnitude from quoted values of ~6 arc-min to ~0.65 arc-min when their corresponding ANN-generated weight files are used for determining the corrected encoder angle.
Making the road by searching - A search engine based on Swarm Information Foraging
Venue: arXiv cs.IR 2009
Year: 2009

Search engines are nowadays one of the most important entry points for Internet users and a central tool to solve most of their information needs. Still, there exist a substantial amount of users' searches which obtain unsatisfactory results. Needless to say, several lines of research aim to increase the relevancy of the results users retrieve. In this paper the authors frame this problem within the much broader (and older) one of information overload. They argue that users' dissatisfaction with search engines is a currently common manifestation of such a problem, and propose a different angle from which to tackle with it. As it will be discussed, their approach shares goals with a current hot research topic (namely, learning to rank for information retrieval) but, unlike the techniques commonly applied in that field, their technique cannot be exactly considered machine learning and, additionally, it can be used to change the search engine's response in real-time, driven by the users behavior. Their proposal adapts concepts from Swarm Intelligence (in particular, Ant Algorithms) from an Information Foraging point of view. It will be shown that the technique is not only feasible, but also an elegant solution to the stated problem; what's more, it achieves promising results, both increasing the performance of a major search engine for informational queries, and substantially reducing the time users require to answer complex information needs.
Wyner-Ziv Coding over Broadcast Channels: Digital Schemes
Venue: arXiv cs.IT 2009
Year: 2009

This paper addresses lossy transmission of a common source over a broadcast channel when there is correlated side information at the receivers, with emphasis on the quadratic Gaussian and binary Hamming cases. A digital scheme that combines ideas from the lossless version of the problem, i.e., Slepian-Wolf coding over broadcast channels, and dirty paper coding, is presented and analyzed. This scheme uses layered coding where the common layer information is intended for both receivers and the refinement information is destined only for one receiver. For the quadratic Gaussian case, a quantity characterizing the overall quality of each receiver is identified in terms of channel and side information parameters. It is shown that it is more advantageous to send the refinement information to the receiver with "better" overall quality. In the case where all receivers have the same overall quality, the presented scheme becomes optimal. Unlike its lossless counterpart, however, the problem eludes a complete characterization.
Message Passing Algorithms for Compressed Sensing: II. Analysis and Validation
Venue: arXiv cs.IT 2009
Year: 2009

In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements \cite{DMM}. The new algorithms are broadly referred to as AMP, for approximate message passing. This is the second of two conference papers describing the derivation of these algorithms, connection with related literature, extensions of original framework, and new empirical evidence. This paper describes the state evolution formalism for analyzing these algorithms, and some of the conclusions that can be drawn from this formalism. We carried out extensive numerical simulations to confirm these predictions. We present here a few representative results.
Secure Multidimensional Queries in Tiered Sensor Networks
Venue: arXiv cs.NI 2009
Year: 2009

In this paper, aiming at securing range query, top-k query, and skyline query in tiered sensor networks, we propose the Secure Range Query (SRQ), Secure Top-$k$ Query (STQ), and Secure Skyline Query (SSQ) schemes, respectively. In particular, SRQ, by using our proposed \emph{prime aggregation} technique, has the lowest communication overhead among prior works, while STQ and SSQ, to our knowledge, are the first proposals in tiered sensor networks for securing top-$k$ and skyline queries, respectively. Moreover, the relatively unexplored issue of the security impact of sensor node compromises on multidimensional queries is studied; two attacks incurred from the sensor node compromises, \emph{collusion attack} and \emph{false-incrimination attack}, are investigated in this paper. After developing a novel technique called \emph{subtree sampling}, we also explore methods of efficiently mitigating the threat of sensor node compromises. Performance analyses regarding the probability for detecting incomplete query-results and communication cost of the proposed schemes are also studied.
Constrained Function Based En-Route Filtering for Sensor Networks
Venue: arXiv cs.NI 2009
Year: 2009

Sensor networks are vulnerable to \emph{false data injection attack} and \emph{path-based DoS} (PDoS) attack. While conventional authentication schemes are insufficient for solving these security conflicts, an \emph{en-route filtering} scheme acts as a defense against these two attacks. To construct an efficient en-route filtering scheme, this paper first presents a Constrained Function based message Authentication (CFA) scheme, which can be thought of as a hash function directly supporting the en-route filtering functionality. Together with the \emph{redundancy property} of sensor networks, which means that an event can be simultaneously observed by multiple sensor nodes, the devised CFA scheme is used to construct a CFA-based en-route filtering (CFAEF) scheme. In contrast to most of the existing methods, which rely on complicated security associations among sensor nodes, our design, which directly exploits an en-route filtering hash function, appears to be novel. We examine the CFA and CFAEF schemes from both the theoretical and numerical aspects to demonstrate their efficiency and effectiveness.
Circuit Lower Bounds, Help Functions, and the Remote Point Problem
Venue: arXiv cs.CC 2009
Year: 2009

We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced by Alon, Panigrahy, and Yekhanin (RANDOM '09)). More precisely, proving lower bounds for ABPs with help polynomials is related to the Remote Point Problem w.r.t. the rank metric, and for constant-depth circuits with help functions it is related to the Remote Point Problem w.r.t. the Hamming metric. For algebraic branching programs with help polynomials with some degree restrictions we show exponential size lower bounds for explicit polynomials.
Designing fuzzy rule based classifier using self-organizing feature map for analysis of multispectral satellite images
Venue: arXiv cs.CV 2009
Year: 2009

We propose a novel scheme for designing fuzzy rule based classifier. An SOFM based method is used for generating a set of prototypes which is used to generate a set of fuzzy rules. Each rule represents a region in the feature space that we call the context of the rule. The rules are tuned with respect to their context. We justified that the reasoning scheme may be different in different context leading to context sensitive inferencing. To realize context sensitive inferencing we used a softmin operator with a tunable parameter. The proposed scheme is tested on several multispectral satellite image data sets and the performance is found to be much better than the results reported in the literature.
The Role of Feedback in Two-way Secure Communications
Venue: arXiv cs.IT 2009
Year: 2009

Most practical communication links are bi-directional. In these models, since the source node also receives signals, its encoder has the option of computing its output based on the signals it received in the past. On the other hand, from a practical point of view, it would also be desirable to identify the cases where such an encoder design may not improve communication rates. This question is particularly interesting for the case where the transmitted messages and the feedback signals are subject to eavesdropping. In this work, we investigate the question of how much impact the feedback has on the secrecy capacity by studying two fundamental models. First, we consider the Gaussian two-way wiretap channel and derive an outer bound for its secrecy capacity region. We show that the secrecy rate loss can be unbounded when feedback signals are not utilized except for a special case we identify, and thus conclude that utilizing feedback can be highly beneficial in general. Second, we consider a half-duplex Gaussian two-way relay channel where the relay node is also an eavesdropper, and find that the impact of feedback is less pronounced compared to the previous scenario. Specifically, the loss in secrecy rate, when ignoring the feedback, is quantified to be less than 0.5 bit per channel use when the relay power goes to infinity. This achievable rate region is obtained with simple time sharing along with cooperative jamming, which, with its simplicity and near optimum performance, is a viable alternative to an encoder that utilizes feedback signals.
Near-ML Signal Detection in Large-Dimension Linear Vector Channels Using Reactive Tabu Search
Venue: arXiv cs.IT 2009
Year: 2009

Low-complexity near-optimal signal detection in large dimensional communication systems is a challenge. In this paper, we present a reactive tabu search (RTS) algorithm, a heuristic based combinatorial optimization technique, to achieve low-complexity near-maximum likelihood (ML) signal detection in linear vector channels with large dimensions. Two practically important large-dimension linear vector channels are considered: i) multiple-input multiple-output (MIMO) channels with large number (tens) of transmit and receive antennas, and ii) severely delay-spread MIMO inter-symbol interference (ISI) channels with large number (tens to hundreds) of multipath components. These channels are of interest because the former offers the benefit of increased spectral efficiency (several tens of bps/Hz) and the latter offers the benefit of high time-diversity orders. Our simulation results show that, while algorithms including variants of sphere decoding do not scale well for large dimensions, the proposed RTS algorithm scales well for signal detection in large dimensions while achieving increasingly closer to ML performance for increasing number of dimensions.
MIMO Radar Using Compressive Sampling
Venue: arXiv cs.IT 2009
Year: 2009

A MIMO radar system is proposed for obtaining angle and Doppler information on potential targets. Transmitters and receivers are nodes of a small scale wireless network and are assumed to be randomly scattered on a disk. The transmit nodes transmit uncorrelated waveforms. Each receive node applies compressive sampling to the received signal to obtain a small number of samples, which the node subsequently forwards to a fusion center. Assuming that the targets are sparsely located in the angle- Doppler space, based on the samples forwarded by the receive nodes the fusion center formulates an l1-optimization problem, the solution of which yields target angle and Doppler information. The proposed approach achieves the superior resolution of MIMO radar with far fewer samples than required by other approaches. This implies power savings during the communication phase between the receive nodes and the fusion center. Performance in the presence of a jammer is analyzed for the case of slowly moving targets. Issues related to forming the basis matrix that spans the angle-Doppler space, and for selecting a grid for that space are discussed. Extensive simulation results are provided to demonstrate the performance of the proposed approach at difference jammer and noise levels.
New Solutions to the Firing Squad Synchronization Problems for Neural and Hyperdag P Systems
Venue: arXiv cs.CE 2009
Year: 2009

We propose two uniform solutions to an open question: the Firing Squad Synchronization Problem (FSSP), for hyperdag and symmetric neural P systems, with anonymous cells. Our solutions take e_c+5 and 6e_c+7 steps, respectively, where e_c is the eccentricity of the commander cell of the dag or digraph underlying these P systems. The first and fast solution is based on a novel proposal, which dynamically extends P systems with mobile channels. The second solution is substantially longer, but is solely based on classical rules and static channels. In contrast to the previous solutions, which work for tree-based P systems, our solutions synchronize to any subset of the underlying digraph; and do not require membrane polarizations or conditional rules, but require states, as typically used in hyperdag and neural P systems.
Querying Two Boundary Points for Shortest Paths in a Polygonal Domain
Venue: arXiv cs.CG 2009
Year: 2009

We consider a variant of two-point Euclidean shortest path query problem: given a polygonal domain, build a data structure for two-point shortest path query, provided that query points always lie on the boundary of the domain. As a main result, we show that a logarithmic-time query for shortest paths between boundary points can be performed using O~ (n^5) preprocessing time and O(n^5) space where n is the number of corners of the polygonal domain and the O~ notation suppresses the polylogarithmic factor. This is realized by observing a connection between Davenport-Schinzel sequences and our problem in the parameterized space. We also provide a tradeoff between space and query time; a sublinear time query is possible using O(n^{3+epsilon}) space. Our approach also extends to the case where query points should lie on a given set of line segments.
A Semantic Similarity Measure for Expressive Description Logics
Venue: arXiv cs.AI 2009
Year: 2009

A totally semantic measure is presented which is able to calculate a similarity value between concept descriptions and also between concept description and individual or between individuals expressed in an expressive description logic. It is applicable on symbolic descriptions although it uses a numeric approach for the calculus. Considering that Description Logics stand as the theoretic framework for the ontological knowledge representation and reasoning, the proposed measure can be effectively used for agglomerative and divisional clustering task applied to the semantic web domain.
Note on Max Lin-2 above Average
Venue: arXiv cs.DS 2009
Year: 2009

In the Max Lin-2 problem we are given a system $S$ of $m$ linear equations in $n$ variables over $\mathbb{F}_2$ in which Equation $j$ is assigned a positive integral weight $w_j$ for each $j$. We wish to find an assignment of values to the variables which maximizes the total weight of satisfied equations. This problem generalizes Max Cut. The expected weight of satisfied equations is $W/2$, where $W=w_1+... +w_m$; $W/2$ is a tight lower bound on the optimal solution of Max Lin-2. Mahajan et al. (J. Comput. Syst. Sci. 75, 2009) stated the following parameterized version of Max Lin-2: decide whether there is an assignment of values to the variables that satisfies equations of total weight at least $W/2+k$, where $k$ is the parameter. They asked whether this parameterized problem is fixed-parameter tractable, i.e., can be solved in time $f(k)(nm)^{O(1)}$, where $f(k)$ is an arbitrary computable function in $k$ only. Their question remains open, but using some probabilistic inequalities and, in one case, a Fourier analysis inequality, Gutin et al. (IWPEC 2009) proved that the problem is fixed-parameter tractable in three special cases. In this paper we significantly extend two of the three special cases using only tools from combinatorics. We show that one of our results can be used to obtain a combinatorial proof that another problem from Mahajan et al. (J. Comput. Syst. Sci. 75, 2009), Max $r$-SAT above the Average, is fixed-parameter tractable for each $r\ge 2.$ Note that Max $r$-SAT above the Average has been already shown to be fixed-parameter tractable by Alon et al. (SODA 2010), but the paper used the approach of Gutin et al. (IWPEC 2009).
Choreographies with Secure Boxes and Compromised Principals
Venue: arXiv cs.CR 2009
Year: 2009

We equip choreography-level session descriptions with a simple abstraction of a security infrastructure. Message components may be enclosed within (possibly nested) "boxes" annotated with the intended source and destination of those components. The boxes are to be implemented with cryptography. Strand spaces provide a semantics for these choreographies, in which some roles may be played by compromised principals. A skeleton is a partially ordered structure containing local behaviors (strands) executed by regular (non-compromised) principals. A skeleton is realized if it contains enough regular strands so that it could actually occur, in combination with any possible activity of compromised principals. It is delivery guaranteed (DG) realized if, in addition, every message transmitted to a regular participant is also delivered. We define a novel transition system on skeletons, in which the steps add regular strands. These steps solve tests, i.e. parts of the skeleton that could not occur without additional regular behavior. We prove three main results about the transition system. First, each minimal DG realized skeleton is reachable, using the transition system, from any skeleton it embeds. Second, if no step is possible from a skeleton A, then A is DG realized. Finally, if a DG realized B is accessible from A, then B is minimal. Thus, the transition system provides a systematic way to construct the possible behaviors of the choreography, in the presence of compromised principals.