nils-herrmann/clean_scirepeval huggingface dataset:
Computational Lower Bounds for Sparse PCA

In the context of sparse principal component detection, we bring evidence towards the existence of a statistical price to pay for computational efficiency. We measure the performance of a test by the smallest signal strength that it can detect and we propose a computationally efficient method based on semidefinite programming. We also prove that the statistical performance of this test cannot be strictly improved by any computationally efficient method. Our results can be viewed as complexity theoretic lower bounds conditionally on the assumptions that some instances of the planted clique problem cannot be solved in randomized polynomial time.
Coalitional manipulation for Schulze's rule

Schulze's rule is used in the elections of a large number of organizations including Wikimedia and Debian. Part of the reason for its popularity is the large number of axiomatic properties, like monotonicity and Condorcet consistency, which it satisfies. We identify a potential shortcoming of Schulze's rule: it is computationally vulnerable to manipulation. In particular, we prove that computing an unweighted coalitional manipulation (UCM) is polynomial for any number of manipulators. This result holds for both the unique winner and the co-winner versions of UCM. . We also prove that computing a weighted coalitional manipulation (WCM) is polynomial for a bounded number of candidates. Finally, we discuss the relation between the unique winner UCM problem and the co-winner UCM problem and argue that they have substantially different necessary and sufficient conditions for the existence of a successful manipulation.
Collective allocation of science funding: from funding agencies to scientific agency

Public agencies like the U.S. National Science Foundation (NSF) and the National Institutes of Health (NIH) award tens of billions of dollars in annual science funding. How can this money be distributed as efficiently as possible to best promote scientific innovation and productivity? The present system relies primarily on peer review of project proposals. In 2010 alone, NSF convened more than 15,000 scientists to review 55,542 proposals 1 . Although considered the scientific gold standard 2 , peer review requires significant overhead costs 3, 4 , and may be subject to biases, inconsistencies, and oversights 5‐17 . We investigate a class of funding models in which all participants receive an equal portion of yearly funding, but are then required to anonymously donate a fraction of their funding to peers. The funding thus flows from one participant to the next, each acting as if he or she were a funding agency themselves. Here we show through a simulation conducted over large-scale citation data (37M articles, 770M citations) that such a distributed system for science may yield funding patterns similar to existing NIH and NSF distributions, but may do so at much lower overhead while exhibiting a range of other desirable features. Self-correcting mechanisms in scientific peer evaluation can yield an efficient and fair distribution of funding. The proposed model can be applied
Exploiting functional dependencies in qualitative probabilistic reasoning

Functional dependencies restrict the potential interactions among variables connected in a probabilistic network. This restriction can be exploited in qualitative probabilistic reasoning by introducing deterministic variables and modifying the inference rules to produce stronger conclusions in the presence of functional relations. I describe how to accomplish these modifications in qualitative probabilistic networks by exhibiting the update procedures for graphical transformations involving probabilistic and deterministic variables and combinations. A simple example demonstrates that the augmented scheme can reduce qualitative ambiguity that would arise without the special treatment of functional dependency. Analysis of qualitative synergy reveals that new higher-order relations are required to reason effectively about synergistic interactions among deterministic variables.
Qualitative Propagation and Scenario-based Explanation of Probabilistic Reasoning

Comprehensible explanations of probabilistic reasoning are a prerequisite for wider acceptance of Bayesian methods in expert systems and decision support systems. A study of human reasoning under uncertainty suggests two different strategies for explaining probabilistic reasoning: The first, qualitative belief propagation, traces the qualitative effect of evidence through a belief network from one variable to the next. This propagation algorithm is an alternative to the graph reduction algorithms of Wellman (1988) for inference in qualitative probabilistic networks. It is based on a qualitative analysis of intercausal reasoning, which is a generalization of Pearl's "explaining away", and an alternative to Wellman's definition of qualitative synergy. The other, Scenario-based reasoning, involves the generation of alternative causal "stories" accounting for the evidence. Comparing a few of the most probable scenarios provides an approximate way to explain the results of probabilistic reasoning. Both schemes employ causal as well as probabilistic knowledge. Probabilities may be presented as phrases and/or numbers. Users can control the style, abstraction and completeness of explanations.
Managing Uncertainty in Rule Based Cognitive Models

An experiment replicated and extended recent findings on psychologically realistic ways of modeling propagation of uncertainty in rule based reasoning. Within a single production rule, the antecedent evidence can be summarized by taking the maximum of disjunctively connected antecedents and the minimum of conjunctively connected antecedents. The maximum certainty factor attached to each of the rule's conclusions can be sealed down by multiplication with this summarized antecedent certainty. Heckerman's modified certainty factor technique can be used to combine certainties for common conclusions across production rules.
Integrating probabilistic, taxonomic and causal knowledge in abductive diagnosis

We propose an abductive diagnosis theory that integrates probabilistic, causal and taxonomic knowledge. Probabilistic knowledge allows us to select the most likely explanation; causal knowledge allows us to make reasonable independence assumptions; taxonomic knowledge allows causation to be modeled at different levels of detail, and allows observations be described in different levels of precision. Unlike most other approaches where a causal explanation is a hypothesis that one or more causative events occurred, we define an explanation of a set of observations to be an occurrence of a chain of causation events. These causation events constitute a scenario where all the observations are true. We show that the probabilities of the scenarios can be computed from the conditional probabilities of the causation events. Abductive reasoning is inherently complex even if only modest expressive power is allowed. However, our abduction algorithm is exponential only in the number of observations to be explained, and is polynomial in the size of the knowledge base. This contrasts with many other abduction procedures that are exponential in the size of the knowledge base.
What is an Optimal Diagnosis?

Within diagnostic reasoning there have been a number of proposed definitions of a diagnosis, and thus of the most likely diagnosis, including most probable posterior hypothesis, most probable interpretation, most probable covering hypothesis, etc. Most of these approaches assume that the most likely diagnosis must be computed, and that a definition of what should be computed can be made a priori, independent of what the diagnosis is used for. We argue that the diagnostic problem, as currently posed, is incomplete: it does not consider how the diagnosis is to be used, or the utility associated with the treatment of the abnormalities. In this paper we analyze several well-known definitions of diagnosis, showing that the different definitions of the most likely diagnosis have different qualitative meanings, even given the same input data. We argue that the most appropriate definition of (optimal) diagnosis needs to take into account the utility of outcomes and what the diagnosis is used for.
Dark Matter Detection in Focus Point Supersymmetry

We determine the prospects for direct and indirect detection of thermal relic neutralinos in supersymmetric theories with multi-TeV squarks and sleptons. We consider the concrete example of the focus point region of minimal supergravity, but our results are generically valid for all models with decoupled scalars and mixed Bino-Higgsino or Higgsino-like dark matter. We determine the parameter space consistent with a 125 GeV Higgs boson including 3-loop corrections in the calculation of the Higgs mass. These corrections increase m_h by 1–3 GeV, lowering the preferred scalar mass scale and decreasing the fine-tuning measure in these scenarios. We then systematically examine prospects for dark matter direct and indirect detection. Direct detection constraints do not exclude these models, especially for μ<0. At the same time, the scenario generically predicts spin-independent signals just beyond current bounds. We also consider indirect detection with neutrinos, gamma rays, antiprotons, and antideuterons. Current IceCube neutrino constraints are competitive with direct detection, implying bright prospects for complementary searches with both direct and indirect detection.
Comparative investigation of the freezing phenomena for quantum correlations under nondissipative decoherence

We show that the phenomenon of frozen discord, exhibited by specific classes of two-qubit states under local nondissipative decoherent evolutions, is a common feature of all known bona fide measures of general quantum correlations. All those measures, despite inducing typically inequivalent orderings on the set of nonclassically correlated states, return a constant value in the considered settings. Every communication protocol that relies on quantum correlations as a resource will run with a performance completely unaffected by noise in the specified dynamical conditions. We provide a geometric interpretation of this phenomenon.
Five Misunderstandings About Case-Study Research

This article examines five common misunderstandings about case-study research: (a) theoretical knowledge is more valuable than practical knowledge; (b) one cannot generalize from a single case, therefore, the single-case study cannot contribute to scientific development; (c) the case study is most useful for generating hypotheses, whereas other methods are more suitable for hypotheses testing and theory building; (d) the case study contains a bias toward verification; and (e) it is often difficult to summarize specific case studies. This article explains and corrects these misunderstandings one by one and concludes with the Kuhnian insight that a scientific discipline without a large number of thoroughly executed case studies is a discipline without systematic production of exemplars, and a discipline without exemplars is an ineffective one. Social science may be strengthened by the execution of a greater number of good case studies.
Advances in Quark Gluon Plasma

In the last 20 years, heavy-ion collisions have been a unique way to study the hadronic matter in the laboratory. Its phase diagram remains unknown, although many experimental and theoretical studies have been undertaken in the last decades. The Relativistic Heavy Ion Collider (RHIC) at BNL was the first ever built heavy-ion collider. RHIC delivered its first collisions in June 2000 boosting the heavy-ion community. Impressive amount of experimental results has been obtained. In November 2010, the Large Hadron Collider (LHC) at CERN delivered lead-lead collisions at unprecedented center-of-mass energies, 14 times larger than that at RHIC. Needless to say that the heavy-ion programs at RHIC and LHC promise fascinating and exciting results in the next decade. In the second part, a historical approach will be adopted, starting with the notion of limiting temperature of matter introduced by Hagedorn in the 60's and the discovery of the QCD asymptotic freedom in the 70's. The phase diagram of hadronic matter, conceived as nowadays, will be shown together with the most important predictions of lattice QCD calculations at finite temperature. In the third part, the heavy-ion collisions at ultra-relativistic energies will be proposed as a unique experimental method to study QGP in the laboratory, as suggested by the Bjorken model. In the last part of these lectures, I will present my biased review of the numerous experimental results obtained in the last decade at RHIC which lead to the concept of strong interacting QGP, and the first results obtained at LHC with the 2010 and 2011 PbPb runs. Finally, the last section is devoted to refer to other lectures about quark gluon plasma and heavy ion physics.
Temporal Reasoning with Probabilities

In this paper we explore representations of temporal knowledge based upon the formalism of Causal Probabilistic Networks (CPNs). Two different ?continuous-time? representations are proposed. In the first, the CPN includes variables representing ?event-occurrence times?, possibly on different time scales, and variables representing the ?state? of the system at these times. In the second, the CPN describes the influences between random variables with values in () representing dates, i.e. time-points associated with the occurrence of relevant events. However, structuring a system of inter-related dates as a network where all links commit to a single specific notion of cause and effect is in general far from trivial and leads to severe difficulties. We claim that we should recognize explicitly different kinds of relation between dates, such as ?cause?, ?inhibition?, ?competition?, etc., and propose a method whereby these relations are coherently embedded in a CPN using additional auxiliary nodes corresponding to "instrumental" variables. Also discussed, though not covered in detail, is the topic concerning how the quantitative specifications to be inserted in a temporal CPN can be learned from specific data.
Uncertainty and Incompleteness

Two major difficulties in using default logics are their intractability and the problem of selecting among multiple extensions. We propose an approach to these problems based on integrating nommonotonic reasoning with plausible reasoning based on triangular norms. A previously proposed system for reasoning with uncertainty (RUM) performs uncertain monotonic inferences on an acyclic graph. We have extended RUM to allow nommonotonic inferences and cycles within nonmonotonic rules. By restricting the size and complexity of the nommonotonic cycles we can still perform efficient inferences. Uncertainty measures provide a basis for deciding among multiple defaults. Different algorithms and heuristics for finding the optimal defaults are discussed.
Decision Making "Biases" and Support for Assumption-Based Higher-Order Reasoning

Unaided human decision making appears to systematically violate consistency constraints imposed by normative theories; these biases in turn appear to justify the application of formal decision-analytic models. It is argued that both claims are wrong. In particular, we will argue that the "confirmation bias" is premised on an overly narrow view of how conflicting evidence is and ought to be handled. Effective decision aiding should focus on supporting the contral processes by means of which knowledge is extended into novel situations and in which assumptions are adopted, utilized, and revised. The Non- Monotonic Probabilist represents initial work toward such an aid.
Automated Reasoning Using Possibilistic Logic: Semantics, Belief Revision, and Variable Certainty Weights

An approach to automated deduction under uncertainty, based on possibilistic logic, is described; for that purpose we deal with clauses weighted by a degree that is a lower bound of a necessity or a possibility measure, according to the nature of the uncertainty. Two resolution rules are used for coping with the different situations, and the classical refutation method can be generalized with these rules. Also, the lower bounds are allowed to be functions of variables involved in the clauses, which results in hypothetical reasoning capabilities. In cases where only lower bounds of necessity measures are involved, a semantics is proposed in which the completeness of the extended resolution principle is proved. The relation between our approach and the idea of minimizing abnormality is briefly discussed. Moreover, deduction from a partially inconsistent knowledge base can be managed in this approach and captures a form of nonmonotonicity.
How Much More Probable is "Much More Probable"? Verbal Expressions for Probability Updates

Bayesian inference systems should be able to explain their reasoning to users, translating from numerical to natural language. Previous empirical work has investigated the correspondence between absolute probabilities and linguistic phrases. This study extends that work to the correspondence between changes in probabilities (updates) and relative probability phrases, such as "much more likely" or "a little less likely." Subjects selected such phrases to best describe numerical probability updates. We examined three hypotheses about the correspondence, and found the most descriptively accurate of these three to be that each such phrase corresponds to a fixed difference in probability (rather than fixed ratio of probabilities or of odds). The empirically derived phrase selection function uses eight phrases and achieved a 72% accuracy in correspondence with the subjects' actual usage.
Positive and Negative Explanations of Uncertain Reasoning in the Framework of Possibility Theory

This paper presents an approach for developing the explanation capabilities of rule-based expert systems managing imprecise and uncertain knowledge. The treatment of uncertainty takes place in the framework of possibility theory where the available information concerning the value of a logical or numerical variable is represented by a possibility distribution which restricts its more or less possible values. We first discuss different kinds of queries asking for explanations before focusing on the two following types : i) how, a particular possibility distribution is obtained (emphasizing the main reasons only) ; ii) why in a computed possibility distribution, a particular value has received a possibility degree which is so high, so low or so contrary to the expectation. The approach is based on the exploitation of equations in max-min algebra. This formalism includes the limit case of certain and precise information.
Subgraph frequencies: mapping the empirical and extremal geography of large graph collections

A growing set of on-line applications are generating data that can be viewed as very large collections of small, dense social graphs --- these range from sets of social groups, events, or collaboration projects to the vast collection of graph neighborhoods in large social networks. A natural question is how to usefully define a domain-independent 'coordinate system' for such a collection of graphs, so that the set of possible structures can be compactly represented and understood within a common space. In this work, we draw on the theory of graph homomorphisms to formulate and analyze such a representation, based on computing the frequencies of small induced subgraphs within each graph. We find that the space of subgraph frequencies is governed both by its combinatorial properties --- based on extremal results that constrain all graphs --- as well as by its empirical properties --- manifested in the way that real social graphs appear to lie near a simple one-dimensional curve through this space. We develop flexible frameworks for studying each of these aspects. For capturing empirical properties, we characterize a simple stochastic generative model, a single-parameter extension of Erdos-Renyi random graphs, whose stationary distribution over subgraphs closely tracks the one-dimensional concentration of the real social graph families. For the extremal properties, we develop a tractable linear program for bounding the feasible space of subgraph frequencies by harnessing a toolkit of known extremal graph theory. Together, these two complementary frameworks shed light on a fundamental question pertaining to social graphs: what properties of social graphs are 'social' properties and what properties are 'graph' properties? We conclude with a brief demonstration of how the coordinate system we examine can also be used to perform classification tasks, distinguishing between structures arising from different types of social graphs.
Blind Men and the Elephant: Detecting Evolving Groups in Social News

We propose an automated and unsupervised methodology for a novel summarization of group behavior based on content preference. We show that graph theoretical community evolution (based on similarity of user preference for content) is effective in indexing these dynamics. Combined with text analysis that targets automatically-identified representative content for each community, our method produces a novel multi-layered representation of evolving group behavior. We demonstrate this methodology in the context of political discourse on a social news site with data that spans more than four years and find coexisting political leanings over extended periods and a disruptive external event that lead to a significant reorganization of existing patterns. Finally, where there exists no ground truth, we propose a new evaluation approach by using entropy measures as evidence of coherence along the evolution path of these groups. This methodology is valuable to designers and managers of online forums in need of granular analytics of user activity, as well as to researchers in social and political sciences who wish to extend their inquiries to large-scale data available on the web.
Why Mass Media Matter to Planning Research

This article asks how planning scholarship may effectively gain impact in planning practice through media exposure. In liberal democracies, the public sphere is dominated by mass media. Therefore, working with such media is a prerequisite for effective public impact of planning research. Using the example of megaproject planning, it is illustrated how so-called “phronetic planning research,” which explicitly incorporates in its methodology active and strategic collaboration with media, may be helpful in generating change in planning practice via the public sphere. Main lessons learned are as follows: (1) working with mass media is an extremely cost-effective way to increase the impact of planning scholarship on practice; (2) recent developments in information technology and social media have made impact via mass media even more effective; (3) research on “tension points,” that is, points of potential conflict, are particularly interesting to media and the public, and are especially likely to generate change in practice; and (4) tension points bite back; planning researchers should be prepared for, but not afraid of, this.