OpenRaiser/Intern-Atlas huggingface dataset:
Synchrony vs Causality in the Asynchronous Pi-Calculus
Venue: arXiv cs.LO 2011
Year: 2011

We study the relation between process calculi that differ in their either synchronous or asynchronous interaction mechanism. Concretely, we are interested in the conditions under which synchronous interaction can be implemented using just asynchronous interactions in the pi-calculus. We assume a number of minimal conditions referring to the work of Gorla: a "good" encoding must be compositional and preserve and reflect computations, deadlocks, divergence, and success. Under these conditions, we show that it is not possible to encode synchronous interactions without introducing additional causal dependencies in the translation.
A Logic with Reverse Modalities for History-preserving Bisimulations
Venue: arXiv cs.LO 2011
Year: 2011

We introduce event identifier logic (EIL) which extends Hennessy-Milner logic by the addition of (1) reverse as well as forward modalities, and (2) identifiers to keep track of events. We show that this logic corresponds to hereditary history-preserving (HH) bisimulation equivalence within a particular true-concurrency model, namely stable configuration structures. We furthermore show how natural sublogics of EIL correspond to coarser equivalences. In particular we provide logical characterisations of weak history-preserving (WH) and history-preserving (H) bisimulation. Logics corresponding to HH and H bisimulation have been given previously, but not to WH bisimulation (when autoconcurrency is allowed), as far as we are aware. We also present characteristic formulas which characterise individual structures with respect to history-preserving equivalences.
Language Support for Declarative Future Commitments
Venue: arXiv cs.PL 2011
Year: 2011

Sequential programming and work-flow programming are two useful, but radically different, ways of describing computational processing. Of the two, it is sequential programming that we teach all programmers and support by programming languages, whether in procedural, objectoriented, or functional paradigms. We teach workflow as a secondary style of problem decomposition for use in special situations, like distributed or networked processing. Both styles offer complementary advantages, but the fact that they employ radically different models for ownership of continuations interferes with our ability to integrate them in a way that allows them to be taught and used in a single programming language. This paper describes a programming language construct, declarative future commitments, that permit better integration of the two.
Mechanism Design via Consensus Estimates, Cross Checking, and Profit Extraction
Venue: arXiv cs.GT 2011
Year: 2011

There is only one technique for prior-free optimal mechanism design that generalizes beyond the structurally benevolent setting of digital goods. This technique uses random sampling to estimate the distribution of agent values and then employs the Bayesian optimal mechanism for this estimated distribution on the remaining players. Though quite general, even for digital goods, this random sampling auction has a complicated analysis and is known to be suboptimal. To overcome these issues we generalize the consensus technique from Goldberg and Hartline (2003) to structurally rich environments that include, e.g., single-minded combinatorial auctions.
Publication patterns of award-winning forest scientists and implications for the ERA journal ranking
Venue: arXiv cs.DL 2011
Year: 2011

Publication patterns of 79 forest scientists awarded major international forestry prizes during 1990-2010 were compared with the journal classification and ranking promoted as part of the 'Excellence in Research for Australia' (ERA) by the Australian Research Council. The data revealed that these scientists exhibited an elite publication performance during the decade before and two decades following their first major award. An analysis of their 1703 articles in 431 journals revealed substantial differences between the journal choices of these elite scientists and the ERA classification and ranking of journals. Implications from these findings are that additional cross-classifications should be added for many journals, and there should be an adjustment to the ranking of several journals relevant to the ERA Field of Research classified as 0705 Forestry Sciences.
A structural model of intuitive probability
Venue: arXiv cs.OH 2011
Year: 2011

Though the ability of human beings to deal with probabilities has been put into question, the assessment of rarity is a crucial competence underlying much of human decision-making and is pervasive in spontaneous narrative behaviour. This paper proposes a new model of rarity and randomness assessment, designed to be cognitively plausible. Intuitive randomness is defined as a function of structural complexity. It is thus possible to assign probability to events without being obliged to consider the set of alternatives. The model is tested on Lottery sequences and compared with subjects' preferences.
Making Use of Advances in Answer-Set Programming for Abstract Argumentation Systems
Venue: arXiv cs.AI 2011
Year: 2011

Dung's famous abstract argumentation frameworks represent the core formalism for many problems and applications in the field of argumentation which significantly evolved within the last decade. Recent work in the field has thus focused on implementations for these frameworks, whereby one of the main approaches is to use Answer-Set Programming (ASP). While some of the argumentation semantics can be nicely expressed within the ASP language, others required rather cumbersome encoding techniques. Recent advances in ASP systems, in particular, the metasp optimization frontend for the ASP-package gringo/claspD provides direct commands to filter answer sets satisfying certain subset-minimality (or -maximality) constraints. This allows for much simpler encodings compared to the ones in standard ASP language. In this paper, we experimentally compare the original encodings (for the argumentation semantics based on preferred, semi-stable, and respectively, stage extensions) with new metasp encodings. Moreover, we provide novel encodings for the recently introduced resolution-based grounded semantics. Our experimental results indicate that the metasp approach works well in those cases where the complexity of the encoded problem is adequately mirrored within the metasp approach.
Synthesis of anisotropic suboptimal controllers by convex optimization
Venue: arXiv cs.SY 2011
Year: 2011

This paper considers a disturbance attenuation problem for a linear discrete time invariant system under random disturbances with imprecisely known probability distributions. The statistical uncertainty is measured in terms of relative entropy using the mean anisotropy functional. The disturbance attenuation capabilities of the system are quantified by the anisotropic norm which is a stochastic counterpart of the H-infinity norm. The designed anisotropic suboptimal controller generally is a dynamic fixed-order output-feedback compensator which is required to stabilize the closed-loop system and keep its anisotropic norm below a prescribed threshold value.
A $(k + 3)/2$-approximation algorithm for monotone submodular maximization over a $k$-exchange system
Venue: arXiv cs.DS 2011
Year: 2011

We consider the problem of maximizing a monotone submodular function in a $k$-exchange system. These systems, introduced by Feldman et al., generalize the matroid k-parity problem in a wide class of matroids and capture many other combinatorial optimization problems. Feldman et al. show that a simple non-oblivious local search algorithm attains a $(k + 1)/2$ approximation ratio for the problem of linear maximization in a $k$-exchange system. Here, we extend this approach to the case of monotone submodular objective functions. We give a deterministic, non-oblivious local search algorithm that attains an approximation ratio of $(k + 3)/2$ for the problem of maximizing a monotone submodular function in a $k$-exchange system.
Improved Linear Programming Bounds on Sizes of Constant-Weight Codes
Venue: arXiv cs.IT 2011
Year: 2011

Let $A(n,d,w)$ be the largest possible size of an $(n,d,w)$ constant-weight binary code. By adding new constraints to Delsarte linear programming, we obtain twenty three new upper bounds on $A(n,d,w)$ for $n \leq 28$. The used techniques allow us to give a simple proof of an important theorem of Delsarte which makes linear programming possible for binary codes.
To Switch or Not To Switch: Understanding Social Influence in Recommender Systems
Venue: arXiv cs.CY 2011
Year: 2011

We designed and ran an experiment to test how often people's choices are reversed by others' recommendations when facing different levels of confirmation and conformity pressures. In our experiment participants were first asked to provide their preferences between pairs of items. They were then asked to make second choices about the same pairs with knowledge of others' preferences. Our results show that others people's opinions significantly sway people's own choices. The influence is stronger when people are required to make their second decision sometime later (22.4%) than immediately (14.1%). Moreover, people are most likely to reverse their choices when facing a moderate number of opposing opinions. Finally, the time people spend making the first decision significantly predicts whether they will reverse their decisions later on, while demographics such as age and gender do not. These results have implications for consumer behavior research as well as online marketing strategies.
Quality Evaluation of Conceptual Level Object Multidimensional Data Model
Venue: arXiv cs.OH 2011
Year: 2011

The advancement of technology facilitates explosive growth of mobile usage in the last decade. Numerous applications have been developed to support its usage. However, gap in technology exists in obtaining correct and trusted values for evaluation indexes of the precise amount of usage. The claims of loss in revenue by the service providers could be more due to unexpected behaviour of the hardware. A similar mistrust is often observed in the users of the services. A trustworthy subscription scheme is in demand for consumers whereas revenue needs to be assured of the service providers. Multiple Authorizations by Multiple Owners (MAMO) has already been introduced as a technology to build trust in the third party billing system. In this paper, MAMO is extended to ensure trustworthiness of the parameters for subscription. Along with call transaction data are reconciled to assure the proper revenue generation.
Getting Beyond the State of the Art of Information Retrieval with Quantum Theory
Venue: arXiv cs.IR 2011
Year: 2011

According to the probability ranking principle, the document set with the highest values of probability of relevance optimizes information retrieval effectiveness given the probabilities are estimated as accurately as possible. The key point of this principle is the separation of the document set into two subsets with a given level of fallout and with the highest recall. If subsets of set measures are replaced by subspaces and space measures, we obtain an alternative theory stemming from Quantum Theory. That theory is named after vector probability because vectors represent event like sets do in classical probability. The paper shows that the separation into vector subspaces is more effective than the separation into subsets with the same available evidence. The result is proved mathematically and verified experimentally. In general, the paper suggests that quantum theory is not only a source of rhetoric inspiration, but is a sufficient condition to improve retrieval effectiveness in a principled way.
A Performance Study of Data Mining Techniques: Multiple Linear Regression vs. Factor Analysis
Venue: arXiv cs.DB 2011
Year: 2011

The growing volume of data usually creates an interesting challenge for the need of data analysis tools that discover regularities in these data. Data mining has emerged as disciplines that contribute tools for data analysis, discovery of hidden knowledge, and autonomous decision making in many application domains. The purpose of this study is to compare the performance of two data mining techniques viz., factor analysis and multiple linear regression for different sample sizes on three unique sets of data. The performance of the two data mining techniques is compared on following parameters like mean square error (MSE), R-square, R-Square adjusted, condition number, root mean square error(RMSE), number of variables included in the prediction model, modified coefficient of efficiency, F-value, and test of normality. These parameters have been computed using various data mining tools like SPSS, XLstat, Stata, and MS-Excel. It is seen that for all the given dataset, factor analysis outperform multiple linear regression. But the absolute value of prediction accuracy varied between the three datasets indicating that the data distribution and data characteristics play a major role in choosing the correct prediction technique.
Web Pages Clustering: A New Approach
Venue: arXiv cs.IR 2011
Year: 2011

The rapid growth of web has resulted in vast volume of information. Information availability at a rapid speed to the user is vital. English language (or any for that matter) has lot of ambiguity in the usage of words. So there is no guarantee that a keyword based search engine will provide the required results. This paper introduces the use of dictionary (standardised) to obtain the context with which a keyword is used and in turn cluster the results based on this context. These ideas can be merged with a metasearch engine to enhance the search efficiency.
Consistent Reconstruction of the Input of an Oversampled Filter Bank From Noisy Subbands
Venue: arXiv cs.NI 2011
Year: 2011

This paper introduces a reconstruction approach for the input signal of an oversampled filter bank (OFB) when the sub-bands generated at its output are quantized and transmitted over a noisy channel. This approach exploits the redundancy introduced by the OFB and the fact that the quantization noise is bounded. A maximum-likelihood estimate of the input signal is evaluated, which only considers the vectors of quantization indexes corresponding to subband signals that could have been generated by the OFB and that are compliant with the quantization errors. When considering an OFB with an oversampling ratio of 3/2 and a transmission of quantized subbands on an AWGN channel, compared to a classical decoder, the performance gains are up to 9 dB in terms of SNR for the reconstructed signal, and 3 dB in terms of channel SNR.
On the Stability of Linear Discrete-Time Fuzzy Systems
Venue: arXiv cs.SY 2011
Year: 2011

In this paper the linear and stationary Discrete-time systems with state variables and dynamic coefficients represented by fuzzy numbers are studied, providing some stability criteria, and characterizing the bounds of the set of solutions in the case of positive systems.
The $k$-error linear complexity distribution for $2^n$-periodic binary sequences
Venue: arXiv cs.CR 2011
Year: 2011

The linear complexity and the $k$-error linear complexity of a sequence have been used as important security measures for key stream sequence strength in linear feedback shift register design. By studying the linear complexity of binary sequences with period $2^n$, one could convert the computation of $k$-error linear complexity into finding error sequences with minimal Hamming weight. Based on Games-Chan algorithm, the $k$-error linear complexity distribution of $2^n$-periodic binary sequences is investigated in this paper. First, for $k=2,3$, the complete counting functions on the $k$-error linear complexity of $2^n$-periodic balanced binary sequences (with linear complexity less than $2^n$) are characterized. Second, for $k=3,4$, the complete counting functions on the $k$-error linear complexity of $2^n$-periodic binary sequences with linear complexity $2^n$ are presented. Third, as a consequence of these results, the counting functions for the number of $2^n$-periodic binary sequences with the $k$-error linear complexity for $k = 2$ and 3 are obtained. Further more, an important result in a recent paper is proved to be not completely correct.
Translating Answer-Set Programs into Bit-Vector Logic
Venue: arXiv cs.AI 2011
Year: 2011

Answer set programming (ASP) is a paradigm for declarative problem solving where problems are first formalized as rule sets, i.e., answer-set programs, in a uniform way and then solved by computing answer sets for programs. The satisfiability modulo theories (SMT) framework follows a similar modelling philosophy but the syntax is based on extensions of propositional logic rather than rules. Quite recently, a translation from answer-set programs into difference logic was provided---enabling the use of particular SMT solvers for the computation of answer sets. In this paper, the translation is revised for another SMT fragment, namely that based on fixed-width bit-vector theories. Thus, even further SMT solvers can be harnessed for the task of computing answer sets. The results of a preliminary experimental comparison are also reported. They suggest a level of performance which is similar to that achieved via difference logic.
Characterization and exploitation of community structure in cover song networks
Venue: arXiv cs.IR 2011
Year: 2011

The use of community detection algorithms is explored within the framework of cover song identification, i.e. the automatic detection of different audio renditions of the same underlying musical piece. Until now, this task has been posed as a typical query-by-example task, where one submits a query song and the system retrieves a list of possible matches ranked by their similarity to the query. In this work, we propose a new approach which uses song communities to provide more relevant answers to a given query. Starting from the output of a state-of-the-art system, songs are embedded in a complex weighted network whose links represent similarity (related musical content). Communities inside the network are then recognized as groups of covers and this information is used to enhance the results of the system. In particular, we show that this approach increases both the coherence and the accuracy of the system. Furthermore, we provide insight into the internal organization of individual cover song communities, showing that there is a tendency for the original song to be central within the community. We postulate that the methods and results presented here could be relevant to other query-by-example tasks.
Buffer Map Message Compression Based on Relevant Window in P2P Streaming Media System
Venue: arXiv cs.MM 2011
Year: 2011

Popular peer to peer streaming media systems such as PPLive and UUSee rely on periodic buffer-map exchange between peers for proper operation. The buffer-map exchange contains redundant information which causes non-negligible overhead. In this paper we present a theoretical framework to study how the overhead can be lowered. Differentiating from the traditional data compression approach, we do not treat each buffer-map as an isolated data block, but consider the correlations between the sequentially exchanged buffer-maps. Under this framework, two buffer-map compression schemes are proposed and the correctness of the schemes is proved mathematically. Moreover, we derive the theoretical limit of compression gain based on probability theory and information theory. Based on the system parameters of UUSee (a popular P2P streaming platform), our simulations show that the buffer-map sizes are reduced by 86% and 90% (from 456 bits down to only 66 bits and 46 bits) respectively after applying our schemes. Furthermore, by combining with the traditional compression methods (on individual blocks), the sizes are decreased by 91% and 95% (to 42 bits and 24 bits) respectively. Our study provides a guideline for developing practical compression algorithms.
An Efficient Codebook Initialization Approach for LBG Algorithm
Venue: arXiv cs.CV 2011
Year: 2011

In VQ based image compression technique has three major steps namely (i) Codebook Design, (ii) VQ Encoding Process and (iii) VQ Decoding Process. The performance of VQ based image compression technique depends upon the constructed codebook. A widely used technique for VQ codebook design is the Linde-Buzo-Gray (LBG) algorithm. However the performance of the standard LBG algorithm is highly dependent on the choice of the initial codebook. In this paper, we have proposed a simple and very effective approach for codebook initialization for LBG algorithm. The simulation results show that the proposed scheme is computationally efficient and gives expected performance as compared to the standard LBG algorithm.
Website Detection Using Remote Traffic Analysis
Venue: arXiv cs.CR 2011
Year: 2011

Recent work in traffic analysis has shown that traffic patterns leaked through side channels can be used to recover important semantic information. For instance, attackers can find out which website, or which page on a website, a user is accessing simply by monitoring the packet size distribution. We show that traffic analysis is even a greater threat to privacy than previously thought by introducing a new attack that can be carried out remotely. In particular, we show that, to perform traffic analysis, adversaries do not need to directly observe the traffic patterns. Instead, they can gain sufficient information by sending probes from a far-off vantage point that exploits a queuing side channel in routers. To demonstrate the threat of such remote traffic analysis, we study a remote website detection attack that works against home broadband users. Because the remotely observed traffic patterns are more noisy than those obtained using previous schemes based on direct local traffic monitoring, we take a dynamic time warping (DTW) based approach to detecting fingerprints from the same website. As a new twist on website fingerprinting, we consider a website detection attack, where the attacker aims to find out whether a user browses a particular web site, and its privacy implications. We show experimentally that, although the success of the attack is highly variable, depending on the target site, for some sites very low error rates. We also show how such website detection can be used to deanonymize message board users.
Differentially Private Online Learning
Venue: arXiv cs.LG 2011
Year: 2011

In this paper, we consider the problem of preserving privacy in the online learning setting. We study the problem in the online convex programming (OCP) framework---a popular online learning setting with several interesting theoretical and practical implications---while using differential privacy as the formal privacy measure. For this problem, we distill two critical attributes that a private OCP algorithm should have in order to provide reasonable privacy as well as utility guarantees: 1) linearly decreasing sensitivity, i.e., as new data points arrive their effect on the learning model decreases, 2) sub-linear regret bound---regret bound is a popular goodness/utility measure of an online learning algorithm. Given an OCP algorithm that satisfies these two conditions, we provide a general framework to convert the given algorithm into a privacy preserving OCP algorithm with good (sub-linear) regret. We then illustrate our approach by converting two popular online learning algorithms into their differentially private variants while guaranteeing sub-linear regret ($O(\sqrt{T})$). Next, we consider the special case of online linear regression problems, a practically important class of online learning problems, for which we generalize an approach by Dwork et al. to provide a differentially private algorithm with just $O(\log^{1.5} T)$ regret. Finally, we show that our online learning framework can be used to provide differentially private algorithms for offline learning as well. For the offline learning problem, our approach obtains better error bounds as well as can handle larger class of problems than the existing state-of-the-art methods Chaudhuri et al.