OpenRaiser/Intern-Atlas huggingface dataset:
The Estimation of Subjective Probabilities via Categorical Judgments of Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

Theoretically as well as experimentally it is investigated how people represent their knowledge in order to make decisions or to share their knowledge with others. Experiment 1 probes into the ways how people 6ather information about the frequencies of events and how the requested response mode, that is, numerical vs. verbal estimates interferes with this knowledge. The least interference occurs if the subjects are allowed to give verbal responses. From this it is concluded that processing knowledge about uncertainty categorically, that is, by means of verbal expressions, imposes less mental work load on the decision matter than numerical processing. Possibility theory is used as a framework for modeling the individual usage of verbal categories for grades of uncertainty. The 'elastic' constraints on the verbal expressions for every sing1e subject are determined in Experiment 2 by means of sequential calibration. In further experiments it is shown that the superiority of the verbal processing of knowledge about uncertainty guise generally reduces persistent biases reported in the literature: conservatism (Experiment 3) and neg1igence of regression (Experiment 4). The reanalysis of Hormann's data reveal that in verbal Judgments people exhibit sensitivity for base rates and are not prone to the conjunction fallacy. In a final experiment (5) about predictions in a real-life situation it turns out that in a numerical forecasting task subjects restricted themselves to those parts of their knowledge which are numerical. On the other hand subjects in a verbal forecasting task accessed verbally as well as numerically stated knowledge. Forecasting is structurally related to the estimation of probabilities for rare events insofar as supporting and contradicting arguments have to be evaluated and the choice of the final Judgment has to be Justified according to the evidence brought forward. In order to assist people in such choice situations a formal model for the interactive checking of arguments has been developed. The model transforms the normal-language quantifiers used in the arguments into fuzzy numbers and evaluates the given train of arguments by means of fuzzy numerica1 operations. Ambiguities in the meanings of quantifiers are resolved interactively.
A Cure for Pathological Behavior in Games that Use Minimax
Venue: arXiv cs.AI 2013
Year: 2013

The traditional approach to choosing moves in game-playing programs is the minimax procedure. The general belief underlying its use is that increasing search depth improves play. Recent research has shown that given certain simplifying assumptions about a game tree's structure, this belief is erroneous: searching deeper decreases the probability of making a correct move. This phenomenon is called game tree pathology. Among these simplifying assumptions is uniform depth of win/loss (terminal) nodes, a condition which is not true for most real games. Analytic studies in [10] have shown that if every node in a pathological game tree is made terminal with probability exceeding a certain threshold, the resulting tree is nonpathological. This paper considers a new evaluation function which recognizes increasing densities of forced wins at deeper levels in the tree. This property raises two points that strengthen the hypothesis that uniform win depth causes pathology. First, it proves mathematically that as search deepens, an evaluation function that does not explicitly check for certain forced win patterns becomes decreasingly likely to force wins. This failing predicts the pathological behavior of the original evaluation function. Second, it shows empirically that despite recognizing fewer mid-game wins than the theoretically predicted minimum, the new function is nonpathological.
Friendship Paradox Redux: Your Friends Are More Interesting Than You
Venue: arXiv cs.SI 2013
Year: 2013

Feld's friendship paradox states that "your friends have more friends than you, on average." This paradox arises because extremely popular people, despite being rare, are overrepresented when averaging over friends. Using a sample of the Twitter firehose, we confirm that the friendship paradox holds for >98% of Twitter users. Because of the directed nature of the follower graph on Twitter, we are further able to confirm more detailed forms of the friendship paradox: everyone you follow or who follows you has more friends and followers than you. This is likely caused by a correlation we demonstrate between Twitter activity, number of friends, and number of followers. In addition, we discover two new paradoxes: the virality paradox that states "your friends receive more viral content than you, on average," and the activity paradox, which states "your friends are more active than you, on average." The latter paradox is important in regulating online communication. It may result in users having difficulty maintaining optimal incoming information rates, because following additional users causes the volume of incoming tweets to increase super-linearly. While users may compensate for increased information flow by increasing their own activity, users become information overloaded when they receive more information than they are able or willing to process. We compare the average size of cascades that are sent and received by overloaded and underloaded users. And we show that overloaded users post and receive larger cascades and they are poor detector of small cascades.
Replay Attack Prevention in Kerberos Authentication Protocol Using Triple Password
Venue: arXiv cs.CR 2013
Year: 2013

Replay attack and password attacks are serious issues in the Kerberos authentication protocol. Many ideas have been proposed to prevent these attacks but they increase complexity of the total Kerberos environment. In this paper we present an improved method which prevents replay attacks and password attacks by using Triple password scheme. Three passwords are stored on Authentication Server and Authentication Server sends two passwords to Ticket Granting Server (one for Application Server) by encrypting with the secret key shared between Authentication server and Ticket Granting server. Similarly,Ticket Granting Server sends one password to Application Server by encrypting with the secret key shared between TGS and application server. Meanwhile, Service-Granting-Ticket is transferred to users by encrypting it with the password that TGS just received from AS. It helps to prevent Replay attack.
Cooperative localization by dual foot-mounted inertial sensors and inter-agent ranging
Venue: arXiv cs.RO 2013
Year: 2013

The implementation challenges of cooperative localization by dual foot-mounted inertial sensors and inter-agent ranging are discussed and work on the subject is reviewed. System architecture and sensor fusion are identified as key challenges. A partially decentralized system architecture based on step-wise inertial navigation and step-wise dead reckoning is presented. This architecture is argued to reduce the computational cost and required communication bandwidth by around two orders of magnitude while only giving negligible information loss in comparison with a naive centralized implementation. This makes a joint global state estimation feasible for up to a platoon-sized group of agents. Furthermore, robust and low-cost sensor fusion for the considered setup, based on state space transformation and marginalization, is presented. The transformation and marginalization are used to give the necessary flexibility for presented sampling based updates for the inter-agent ranging and ranging free fusion of the two feet of an individual agent. Finally, characteristics of the suggested implementation are demonstrated with simulations and a real-time system implementation.
Sets Represented as the Length-n Factors of a Word
Venue: arXiv cs.FL 2013
Year: 2013

In this paper we consider the following problems: how many different subsets of Sigma^n can occur as set of all length-n factors of a finite word? If a subset is representable, how long a word do we need to represent it? How many such subsets are represented by words of length t? For the first problem, we give upper and lower bounds of the form alpha^(2^n) in the binary case. For the second problem, we give a weak upper bound and some experimental data. For the third problem, we give a closed-form formula in the case where n <= t < 2n. Algorithmic variants of these problems have previously been studied under the name "shortest common superstring".
From Declarative Model to Solution: Scheduling Scenario Synthesis
Venue: arXiv cs.SE 2013
Year: 2013

This paper presents deductive programming for scheduling scenario generation. Modeling for solution is achieved through program transformations. First, declarative model for scheduling problem domain is introduced. After that model is interpreted as scheduling domain language and as predicate transition Petri net. Generated reachability tree presents search space with solutions. At the end results are discussed and analyzed.
From Cookies to Cooks: Insights on Dietary Patterns via Analysis of Web Usage Logs
Venue: arXiv cs.CY 2013
Year: 2013

Nutrition is a key factor in people's overall health. Hence, understanding the nature and dynamics of population-wide dietary preferences over time and space can be valuable in public health. To date, studies have leveraged small samples of participants via food intake logs or treatment data. We propose a complementary source of population data on nutrition obtained via Web logs. Our main contribution is a spatiotemporal analysis of population-wide dietary preferences through the lens of logs gathered by a widely distributed Web-browser add-on, using the access volume of recipes that users seek via search as a proxy for actual food consumption. We discover that variation in dietary preferences as expressed via recipe access has two main periodic components, one yearly and the other weekly, and that there exist characteristic regional differences in terms of diet within the United States. In a second study, we identify users who show evidence of having made an acute decision to lose weight. We characterize the shifts in interests that they express in their search queries and focus on changes in their recipe queries in particular. Last, we correlate nutritional time series obtained from recipe queries with time-aligned data on hospital admissions, aimed at understanding how behavioral data captured in Web logs might be harnessed to identify potential relationships between diet and acute health problems. In this preliminary study, we focus on patterns of sodium identified in recipes over time and patterns of admission for congestive heart failure, a chronic illness that can be exacerbated by increases in sodium intake.
Faster Private Release of Marginals on Small Databases
Venue: arXiv cs.DS 2013
Year: 2013

We study the problem of answering \emph{$k$-way marginal} queries on a database $D \in (\{0,1\}^d)^n$, while preserving differential privacy. The answer to a $k$-way marginal query is the fraction of the database's records $x \in \{0,1\}^d$ with a given value in each of a given set of up to $k$ columns. Marginal queries enable a rich class of statistical analyses on a dataset, and designing efficient algorithms for privately answering marginal queries has been identified as an important open problem in private data analysis. For any $k$, we give a differentially private online algorithm that runs in time $$ \min{\exp(d^{1-Ω(1/\sqrt{k})}), \exp(d / \log^{.99} d)\} $$ per query and answers any (possibly superpolynomially long and adaptively chosen) sequence of $k$-way marginal queries up to error at most $\pm .01$ on every query, provided $n \gtrsim d^{.51} $. To the best of our knowledge, this is the first algorithm capable of privately answering marginal queries with a non-trivial worst-case accuracy guarantee on a database of size $\poly(d, k)$ in time $\exp(o(d))$. Our algorithms are a variant of the private multiplicative weights algorithm (Hardt and Rothblum, FOCS '10), but using a different low-weight representation of the database. We derive our low-weight representation using approximations to the OR function by low-degree polynomials with coefficients of bounded $L_1$-norm. We also prove a strong limitation on our approach that is of independent approximation-theoretic interest. Specifically, we show that for any $k = o(\log d)$, any polynomial with coefficients of $L_1$-norm $poly(d)$ that pointwise approximates the $d$-variate OR function on all inputs of Hamming weight at most $k$ must have degree $d^{1-O(1/\sqrt{k})}$.
Minimum Variance Estimation of a Sparse Vector within the Linear Gaussian Model: An RKHS Approach
Venue: arXiv cs.IT 2013
Year: 2013

We consider minimum variance estimation within the sparse linear Gaussian model (SLGM). A sparse vector is to be estimated from a linearly transformed version embedded in Gaussian noise. Our analysis is based on the theory of reproducing kernel Hilbert spaces (RKHS). After a characterization of the RKHS associated with the SLGM, we derive novel lower bounds on the minimum variance achievable by estimators with a prescribed bias function. This includes the important case of unbiased estimation. The variance bounds are obtained via an orthogonal projection of the prescribed mean function onto a subspace of the RKHS associated with the SLGM. Furthermore, we specialize our bounds to compressed sensing measurement matrices and express them in terms of the restricted isometry and coherence parameters. For the special case of the SLGM given by the sparse signal in noise model (SSNM), we derive closed-form expressions of the minimum achievable variance (Barankin bound) and the corresponding locally minimum variance estimator. We also analyze the effects of exact and approximate sparsity information and show that the minimum achievable variance for exact sparsity is not a limiting case of that for approximate sparsity. Finally, we compare our bounds with the variance of three well-known estimators, namely, the maximum-likelihood estimator, the hard-thresholding estimator, and compressive reconstruction using the orthogonal matching pursuit.
Analyzing user behavior of the micro-blogging website Sinaweibo during hot social events
Venue: arXiv cs.SI 2013
Year: 2013

The spread and resonance of users' opinions on SinaWeibo, the most popular micro-blogging website in China, are tremendously influential, having significantly affected the processes of many real-world hot social events. We select 21 hot events that were widely discussed on SinaWeibo in 2011, and do some statistical analyses. Our main findings are that (i) male users are more likely to be involved, (ii) messages that contain pictures and those posted by verified users are more likely to be reposted, while those with URLs are less likely, (iii) gender factor, for most events, presents no significant difference in reposting likelihood.
Worst-case User Analysis in Poisson Voronoi Cells
Venue: arXiv cs.IT 2013
Year: 2013

In this letter, we focus on the performance of a worst-case mobile user (MU) in the downlink cellular network. We derive the coverage probability and the spectral efficiency of the worst-case MU using stochastic geometry. Through analytical and numerical results, we draw out interesting insights that the coverage probability and the spectral efficiency of the worst-case MU decrease down to 23% and 19% of those of a typical MU, respectively. By applying a coordinated scheduling (CS) scheme, we also investigate how much the performance of the worst-case MU is improved.
Reputation Algebra for Cloud-based Anonymous Data Storage Systems
Venue: arXiv cs.DC 2013
Year: 2013

Given a cloud-based anonymous data storage system, there are two ways for managing the nodes involved in file transfers. One of them is using reputations and the other uses a micropayment system. In reputation-based approach, each node has a reputation associated with it, which is used as a currency or feedback collection for file exchange operations. There have been several attempts over the years to develop a strong and efficient reputation system that provides credibility, fairness, and accountability. One such attempt was the Free Haven Project that provides a strong foundation for cloud-based anonymous data storage systems. The work proposed in this paper is motivated by the Free Haven Project aimed at developing a reputation system that facilitates dynamic operations such as adding servers, removing servers and changing role of authorities. The proposed system also provides algorithm for scoring and maintaining reputations of the servers in order to achieve credibility, accountability and fairness.
Iterative Detection with Soft Decision in Spectrally Efficient FDM Systems
Venue: arXiv cs.IT 2013
Year: 2013

In Spectrally Efficient Frequency Division Multiplexing systems the input data stream is divided into several adjacent subchannels where the distance of the subchannels is less than that of Orthogonal Frequency Division Multiplexing(OFDM)systems. Since the subcarriers are not orthogonal in SEFDM systems, they lead to interference at the receiver side. In this paper, an iterative method is proposed for interference compensation for SEFDM systems. In this method a soft mapping technique is used after each iteration block to improve its performance. The performance of the proposed method is comparable to that of Sphere Detection(SD)which is a nearly optimal detection method.
Simultaneous approximation for scheduling problems
Venue: arXiv cs.DS 2013
Year: 2013

Motivated by the problem to approximate all feasible schedules by one schedule in a given scheduling environment, we introduce in this paper the concepts of strong simultaneous approximation ratio (SAR) and weak simultaneous approximation ratio (WAR). Then we study the two parameters under various scheduling environments, such as, non-preemptive, preemptive or fractional scheduling on identical, related or unrelated machines.
Relative error due to a single bit-flip in floating-point arithmetic
Venue: arXiv cs.NA 2013
Year: 2013

We consider the error due to a single bit-flip in a floating point number. We assume IEEE 754 double precision arithmetic, which encodes binary floating point numbers in a 64-bit word. We assume that the bit-flip happens randomly so it has equi-probability (1/64) to hit any of the 64 bits. Since we want to mitigate the assumption on our initial floating-point number, we assume that it is uniformly picked among all normalized number. With this framework, we can summarize our findings as follows. The probability for a single bit flip to cause a relative error less than 10^-11 in a normalized floating-point number is above 25%; The probability for a single bit flip to cause a relative error less than 10^-6 in a normalized floating-point number is above 50%; Etc.
Joint operation in public key cryptography
Venue: arXiv cs.CR 2013
Year: 2013

We believe that there is no real data protection without our own tools. Therefore, our permanent aim is to have more of our own codes. In order to achieve that, it is necessary that a lot of young researchers become interested in cryptography. We believe that the encoding of cryptographic algorithms is an important step in that direction, and it is the main reason why in this paper we present a software implementation of finding the inverse element, the operation which is essentially related to both ECC (Elliptic Curve Cryptography) and the RSA schemes of digital signature.
Characterizing and curating conversation threads: Expansion, focus, volume, re-entry
Venue: arXiv cs.SI 2013
Year: 2013

Discussion threads form a central part of the experience on many Web sites, including social networking sites such as Facebook and Google Plus and knowledge creation sites such as Wikipedia. To help users manage the challenge of allocating their attention among the discussions that are relevant to them, there has been a growing need for the algorithmic curation of on-line conversations --- the development of automated methods to select a subset of discussions to present to a user. Here we consider two key sub-problems inherent in conversational curation: length prediction --- predicting the number of comments a discussion thread will receive --- and the novel task of re-entry prediction --- predicting whether a user who has participated in a thread will later contribute another comment to it. The first of these sub-problems arises in estimating how interesting a thread is, in the sense of generating a lot of conversation; the second can help determine whether users should be kept notified of the progress of a thread to which they have already contributed. We develop and evaluate a range of approaches for these tasks, based on an analysis of the network structure and arrival pattern among the participants, as well as a novel dichotomy in the structure of long threads. We find that for both tasks, learning-based approaches using these sources of information yield improvements for all the performance metrics we used.
Auction Algorithm for Production Models
Venue: arXiv cs.GT 2013
Year: 2013

We show an auction-based algorithm to compute market equilibrium prices in a production model, where consumers purchase items under separable nonlinear utility concave functions which satisfy W.G.S(Weak Gross Substitutes); producers produce items with multiple linear production constraints. Our algorithm differs from previous approaches in that the prices are allowed to both increase and decrease to handle changes in the production. This provides a t^atonnement style algorithm which converges and provides a PTAS. The algorithm can also be extended to arbitrary convex production regions and the Arrow-Debreu model. The convergence is dependent on the behavior of the marginal utility of the concave function.
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
Venue: arXiv cs.DS 2013
Year: 2013

We propose a new exact method for shortest-path distance queries on large-scale networks. Our method precomputes distance labels for vertices by performing a breadth-first search from every vertex. Seemingly too obvious and too inefficient at first glance, the key ingredient introduced here is pruning during breadth-first searches. While we can still answer the correct distance for any pair of vertices from the labels, it surprisingly reduces the search space and sizes of labels. Moreover, we show that we can perform 32 or 64 breadth-first searches simultaneously exploiting bitwise operations. We experimentally demonstrate that the combination of these two techniques is efficient and robust on various kinds of large-scale real-world networks. In particular, our method can handle social networks and web graphs with hundreds of millions of edges, which are two orders of magnitude larger than the limits of previous exact methods, with comparable query time to those of previous methods.
Robust Noise Filtering in Image Sequences
Venue: arXiv cs.CV 2013
Year: 2013

Image sequences filtering have recently become a very important technical problem especially with the advent of new technology in multimedia and video systems applications. Often image sequences are corrupted by some amount of noise introduced by the image sensor and therefore inherently present in the imaging process. The main problem in the image sequences is how to deal with spatio-temporal and non stationary signals. In this paper, we propose a robust method for noise removal of image sequence based on coupled spatial and temporal anisotropic diffusion. The idea is to achieve an adaptive smoothing in both spatial and temporal directions, by solving a nonlinear diffusion equation. This allows removing noise while preserving all spatial and temporal discontinuities