Abstract. How small can a set of vertices in the [Formula: see text]-dimensional hypercube [Formula: see text] be if it meets every copy of [Formula: see text]? The asymptotic density of such a set (for [Formula: see text] fixed and [Formula: see text] large) is denoted by [Formula: see text]. It is easy to see that [Formula: see text], and it is known that [Formula: see text] for [Formula: see text], but it was recently shown that [Formula: see text] for [Formula: see text]. In this paper, we show that the latter phenomenon also holds for [Formula: see text] and [Formula: see text].

If G is a group, we say a subset S of G is product-free if the equation xy=z has no solutions with x,y,z ∈ S.In 1985, Babai and Sós [] asked, for a finite group G, how large a subset S⊆ G can be if it is product-free. The main tool (hitherto) for studying this problem has been the notion of a quasirandom group. For D ∈ ℕ, a group G is said to be D-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of G is at least D. Gowers showed that in a D-quasirandom finite group G, the maximal size of a product-free set is at most |G|/D1/3. This disproved a longstanding conjecture of Babai and Sós from 1985. For the special unitary group, G=(n), Gowers observed that his argument yields an upper bound of n−1/3 on the measure of a measurable product-free subset. In this paper, we improve Gowers’ upper bound to exp(−cn1/3), where c>0 is an absolute constant. In fact, we establish something stronger, namely, product-mixing for measurable subsets of (n) with measure at least exp(−cn1/3); for this product-mixing result, the n1/3 in the exponent is sharp. Our approach involves introducing novel hypercontractive inequalities, which imply that the non-Abelian Fourier spectrum of the indicator function of a small set concentrates on high-dimensional irreducible representations. Our hypercontractive inequalities are obtained via methods from representation theory, harmonic analysis, random matrix theory and differential geometry. We generalize our hypercontractive inequalities from (n) to an arbitrary D-quasirandom compact connected Lie group for D at least an absolute constant, thereby extending our results on product-free sets to such groups. We also demonstrate various other applications of our inequalities to geometry (viz., non-Abelian Brunn-Minkowski type inequalities), mixing times, and the theory of growth in compact Lie groups. A subsequent work due to Arunachalam, Girish and Lifshitz uses our inequalities to establish new separation results between classical and quantum communication complexity.

We prove an analogue of Bonami’s (hypercontractive) lemma for complex-valued functions on L (𝑉 ,𝑊 ), where 𝑉 and 𝑊 are vector spaces over a finite field. This inequality is useful for functions on L (𝑉 ,𝑊 ) whose ‘generalised influences’ are small, in an appropriate sense. It leads to a significant shortening of the proof of a recent seminal result by Khot, Minzer and Safra that pseudorandom sets in Grassmann graphs have near-perfect expansion, which (in combination with the work of Dinur, Khot, Kindler, Minzer and Safra) implies the 2-2 Games conjecture (the variant, that is, with imperfect completeness)

Abstract This article is the fifth in a series of articles from our study examining information‐seeking behavior in relation to information‐retrieval (IR) interaction. This article focuses on the examination of the interaction variables within Saracevic's ( 1989 ) triadic IR model. The analysis involved an examination of the information‐searching behavior of academic researchers during a mediated interaction with an IR system, particularly concentrating on the interaction between the information seeker, the search intermediary, and the IR system. To explore the variables during mediated search interaction, two small‐scale studies of mediated on‐line searching were conducted at the University of Sheffield. The studies involved mainly qualitative data analysis of interview transcripts and on‐line search results, together with quantitative data analysis of questionnaire results. The studies specifically investigated: (1) aspects of the mediated search process, (2) relevant information sources, and (3) interaction measures derived from search logs and tape transcripts, and related interaction measures. Findings include: (1) a number of different types of interactions were identified, (2) the presearching interactions between information seeker and intermediary aided the information seeker to identify their idea and problem, and (3) most information seekers in this study were at the problem definition stage or problem resolution stage following the search process. From this research, it is clear that the interaction did affect the search process. The intermediary helped the users to identify their search terms more clearly and focus on the references obtained. In most cases, the users and intermediary considered the communication process very effective, and the interactions that took place during the on‐line search were found to affect the users' perceptions of the problem, personal knowledge, and relevance judgments. The interaction process aided the users to obtain very useful results with help from the intermediary. In general, the users gave a positive evaluation of the retrieved answers in terms of focus, completeness, novelty, and degree of nonrelevancy.

Abstract This is the fourth in a series resulting from a joint research project directed by Professor Tom Wilson in the United Kingdom and Dr. Amanda Spink in the United States. The analysis reported here sought to test a number of hypotheses linking global/analytic cognitive styles and aspects of researchers' problem‐solving and related information‐seeking behavior. One hundred and eleven postdoctoral researchers were assessed for Witkin's field dependence/independence using Riding's Cognitive Styles Analysis and for Pask's holist/serialist biases using items from Ford's Study Processes Questionnaire. These measures were correlated with the researchers' perceptions of aspects of their problem‐solving and information‐seeking behavior, and with those of the search intermediary who performed literature searches on their behalf. A number of statistically significant correlations were found. Field‐independent researchers were more analytic and active than their field‐dependent counterparts. Holists engaged more in exploratory and serendipitous behavior, and were more idiosyncratic in their communication than serialists.

Abstract Our project has investigated the processes of mediated information retrieval (IR) searching during human information‐seeking processes to characterize aspects of this process, including information seekers' changing situational contexts; information problems; uncertainty reduction; successive searching, cognitive styles; and cognitive and affective states. The research has involved observational, longitudinal data collection in the United States and United Kingdom. Three questionnaires were used for pre‐ and postsearch interviews: reference interview, information seeker postsearch, and search intermediary postsearch questionnaires. In addition, the Sheffield team employed a fourth set of instruments in a follow‐up interview some 2 months after the search. A total of 198 information seekers participated in a mediated on‐line search with a professional intermediary using the Dialog Information Service. Each mediated search process was audio taped and search transaction log recorded. The findings are presented in four parts. Part I presents the background, theoretical framework, models, and research design used during the research. Part II is devoted to exploring changes in information seekers' uncertainty during the mediated process. Part III provides results related to successive searching. Part IV reports findings related to cognitive styles, individual differences, age and gender. Additional articles that discuss further findings from this complex research project, including: (1) an integrated model of information seeking and searching, (2) assessment of mediated searching, and (3) intermediary‐information seeker communication, are in preparation and will be published separately.

Abstract Our project has investigated the processes of mediated information retrieval (IR) searching during human information‐seeking processes to characterize aspects of this process, including information seekers' changing situational contexts; information problems; uncertainty reduction; successive searching, cognitive styles; and cognitive and affective states. The research has involved observational, longitudinal data collection in the United States and the United Kingdom. Three questionnaires were used for pre‐ and postsearch interviews: reference interview, information‐seeker postsearch, and search intermediary postsearch questionnaires. In addition, the Sheffield team employed a fourth set of instruments in a follow‐up interview some 2 months after the search. A total of 198 information seekers participated in a mediated on‐line search with a professional intermediary using the Dialog Information Service. Each mediated search process was audiotaped and search transaction logs recorded. The findings are presented in four parts. Part I presents the background, theoretical framework, models, and research design used during the research. Part II is devoted to exploring changes in information seekers' uncertainty during the mediated process. Part III provides results related to successive searching. Part IV reports findings related to cognitive styles, individual differences, age and gender. Additional articles that discuss further findings from this complex research project, including: (1) an integrated model of information seeking and searching, (2) assessment of mediated searching, and (3) intermediary information‐seeker communication, are in preparation and will be published separately.

Abstract This article explores the relationship between the concept of uncertainty in information seeking, within a model of the problem‐solving process proposed by Wilson (1999a) and variables derived from other models and from the work of Ellis and Kuhlthau. The research has involved longitudinal data collection in the United States and United Kingdom employing three interview schedules (incorporating self‐completed questionnaires) used for pre‐ and postsearch interviews: and postsearch interviews with the information seeker and the search intermediary. In addition, the Sheffield team employed a fourth set of instruments in a follow‐up interview some 2 months after the search. Related search episodes, with a professional search intermediary using the Dialog Information Service and other sources were audiotaped, and search transaction logs were recorded. The mediated search clients were faculty and research students engaged in either personal or externally supported research projects. The article concludes that the problem solving model is recognized by such researchers as describing their activities and that the uncertainty concept, operationalized as here, serves as a useful variable in understanding information‐seeking behavior. It also concludes that Ellis's concept of “search characteristics” and Kuhlthau's information‐seeking stages are independent of the problem stage, and that a set of affective variables, based on those of Kuhlthau, appear to signify a generalized positive or negative affective orientation towards the course of the information problem solution.

The relationship between information science and information systems (IS) research is examined through analysis of the subject literature of each field and by citation and co-citation analysis of highly cited researchers in each field. The subfields of user studies (US) and information retrieval (IR) research were selected to represent information science research as these subject areas are central to information science and seemed also to represent areas in which there was most overlap of interest or subject matter. The two forms of analysis revealed that although there seemed considerable overlap or potential for overlap in research subjects that there was almost none in relation to the disciplinary fields as assessed by the co-citation analysis of the most highly cited authors in the three subject areas. An examination of the reasons for this is offered in relation to the nature of scientific disciplines, the socialization process of researchers in the different fields and with institutional pressures.

The problem of measurement in information retrieval research is traced to its source in the first retrieval tests. The problem is seen as presenting a chronic dilemma for the field. This dilemma has taken three forms as the discipline has evolved: (1) The dilemma of measurement in the archetypal approach: Stated relevance versus user relevance; (2) the dilemma of measurement in the probabilistic approach: Realism versus formalism; and (3) the dilemma of measurement in the Information Retrieval-Expert System (IR-ES) approach: Linear measures of relevance versus logarithmic measures of knowledge. It is argued that the dilemma of measurement has remained intractable even given the different assumptions of the different approaches for three connected reasons—the nature of the subject matter of the field; the nature of relevance judgment; and the nature of cognition and knowledge. Finally, it is concluded that the original vision of information retrieval research as a discipline founded on quantification proved restricting for its theoretical and methodological development and that increasing recognition of this is reflected in growing interest in qualitative methods in information retrieval research in relation to the cognitive, behavioral, and affective aspects of the information retrieval interaction. © 1996 John Wiley & Sons, Inc.

An important stage in the process of retrieval of objects from a hypertext database is the creation of a set of internodal links that are intended to represent the relationships existing between objects; this operation is often undertaken manually, just as index terms are often manually assigned to documents in a conventional retrieval system. In an earlier article (Ellis, D., Furner-Hines, J., & Willett, P., 1994b), the results were published of a study in which several different sets of links were inserted, each by a different person, between the paragraphs of each of a number of full-text documents. These results showed little similarity between the link-sets, a finding that was comparable with those of studies of inter-indexer consistency, which suggest that there is generally only a low level of agreement between the sets of index terms assigned to a document by different indexers. In this article, a description is provided of an investigation into the nature of the relationship existing between (i) the levels of inter-linker consistency obtaining among the group of hypertext databases used in our earlier experiments, and (ii) the levels of effectiveness of a number of searches carried out in those databases. An account is given of the implementation of the searches and of the methods used in the calculation of numerical values expressing their effectiveness. Analysis of the results of a comparison between recorded levels of consistency and those of effectiveness does not allow us to draw conclusions about the consistency-effectiveness relationship that are equivalent to those drawn in comparable studies of inter-indexer consistency. © 1996 John Wiley & Sons, Inc.