1,720,971 research outputs found
Function Evaluation via Linear Programming Approach in the Priced Information Model
No full textWe determine the complexity of evaluating monotone Boolean functions in a variant of the decision tree model introduced in [Charikar et al. 2002]. In this model, reading different variables can incur different costs, and competitive analysis is employed to evaluate the performance of the algorithms. It is known that for a monotone Boolean function f, the size of the largest certificate, aka PROOF(f), is a lower bound for γ(f), the best possible competitiveness achievable by an algorithm on f. This bound has been proved to be achievable for some subclasses of the monotone Boolean functions, e.g., read once formulae, threshold trees. However, determining γ(f) for an arbitrary monotone Boolean function has so far remained a major open question, with the best known upper bound being essentially a factor of 2 away from the above lower bound.
We close the gap and prove that for any monotone Boolean function f, γ(f) = PROOF(f). In fact, we prove that γ(f) ≤ PROOF(f) holds for a class much larger than the set of monotone Boolean functions. This class also contains all Boolean functions
On the Competitive Ratio of Evaluating Priced Functions
Full text linkCicalese F, Laber E. On the Competitive Ratio of Evaluating Priced Functions. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006). 2006: 944-953
Correction to: Trading Off Worst and Expected Cost in Decision Tree Problems
No full textThis erratum fixes a technical problem in the paper published in Algorithmica, Volume 79, Number 3, November 2017, pp. 886-908. Theorem 1 of this paper gives upper bounds on both worst testing cost and expected testing cost of the decision tree built by Algorithm 1. Although the statement is correct, the proof presented in the paper has a problem. The proof relies on the analysis of a nonlinear program (NLP) given by Eqs. (5)-(9), which is not convex as mistakenly proved in Appendix A. 2. In this erratum we present a correct proof of Theorem 1. Instead of analyzing the NLP we analyze a related linear program
Teaching with limited information on the Learner's behaviour
No full textMachine Teaching studies how efficiently a Teacher can guide a Learner to a target hypothesis. We focus on the model of Machine Teaching with a black box learner introduced in [Dasgupta et al., ICML 2019], where the teaching is done interactively without having any knowledge of the Learner's algorithm and class of hypotheses, apart from the fact that it contains the target hypothesis h∗. We first refine some existing results for this model and, then, we study new variants of it. Motivated by the realistic possibility that h∗ is not available to the learner, we consider the case where the teacher can only aim at having the learner converge to a best available approximation of h∗. We also consider weaker black box learners, where, in each round, the choice of the consistent hypothesis returned to the Teacher is not adversarial, and in particular, we show that better provable bounds can be obtained for a type of Learner that moves to the next hypothesis smoothly, preferring hypotheses that are close to the current one; and for another type of Learner that can provide to the Teacher hypotheses chosen at random among those consistent with the examples received so far. Finally, we present an empirical evaluation of our basic interactive teacher on real datasets
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
