nils-herrmann/clean_scirepeval huggingface dataset:
Thwarting Web Censorship with Untrusted Messenger Discovery

All existing anti-censorship systems for the Web rely on proxies to grant clients access to censored information. Therefore, they face the proxy discovery problem: how can clients discover the proxies without having the censor discover and block these proxies? To avoid widespread discovery and blocking, proxies must not be widely published and should be discovered in-band. In this paper, we present a proxy discovery mechanism called keyspace hopping that meets this goal. Similar in spirit to frequency hopping in wireless networks, keyspace hopping ensures that each client discovers only a small fraction of the total number of proxies. However, requiring clients to independently discover proxies from a large set makes it practically impossible to verify the trustworthiness of every proxy and creates the possibility of having untrusted proxies. To address this, we propose separating the proxy into two distinct components—the messenger, which the client discovers using keyspace hopping and which simply acts as a gateway to the Internet; and the portal, whose identity is widely-published and whose responsibility it is to interpret and serve the client’s requests for censored content. We show how this separation, as well as in-band proxy discovery, can be applied to a variety of anti-censorship systems.
On Coding for Non-Multicast Networks ∗

We consider the issue of coding for non-multicast networks. For multicast networks, it is known that linear operations over a field no larger than the number of receivers are sufficient to achieve all feasible connections. In the case of nonmulticast networks, necessary and sufficient conditions are known, if we restrict ourselves to linear codes over a finite field . However, no linearity sufficiency results exist for non-multicast networks. Indeed,  shows that linearity over a field is not sufficient in general. We present a coding theorem that provides necessary and sufficient conditions, in terms of receiver entropies, for an arbitrary set of connections to be achievable on any network. We conjecture that linearity is sufficient to satisfy the coding theorem, when linear operations are performed over vectors rather than scalars in a field. We illustrate the intuition of this conjecture with an example. This work is part of an ongoing cooperation with R. Koetter.
Text Bundling: Statistics Based Data-Reduction

As text corpora become larger, tradeoffs between speed and accuracy become critical: slow but accurate methods may not complete in a practical amount of time. In order to make the training data a manageable size, a data reduction technique may be necessary. Subsampling, for example, speeds up a classifier by randomly removing training points. In this paper, we describe an alternate method for reducing the number of training points by combining training points such that important statistical information is retained. Our algorithm keeps the same statistics that fast, linear-time text algorithms like Rocchio and Naive Bayes use. We provide empirical results that show our data reduction technique compares favorably to three other data reduction techniques on four standard text corpora.
Prerequisites for a Personalizable User Interface

Interfaces that support customization and can adapt to individuals’ specific use patterns may be more effective than ones designed to be “one size fits all”. However, to test whether such interfaces benefit users in actual everyday applications, a lot of underlying application infrastructure must be reimplemented to accommodate customization and adaptation. In this paper we discuss Haystack, a platform for building information applications in which user interface concepts such as commands, views, and widgets and even application data itself is described as a semantic network, providing a flexible environment for prototyping notions of customization. Haystack’s data model can host information that used to be managed by multiple applications, meaning that users can use Haystack to interact with their data under a single paradigm, and adaptability and customization capabilities can be provided across multiple domains at once.
Haystack: A Platform for Authoring End User Semantic Web Applications

The Semantic Web promises to open innumerable opportunities for automation and information retrieval by standardizing the protocols for metadata exchange. However, just as the success of the World Wide Web can be attributed to the ease of use and ubiquity of Web browsers, we believe that the unfolding of the Semantic Web vision depends on users getting powerful but easy-to-use tools for managing their information. But unlike HTML, which can be easily edited in any text editor, RDF is more complicated to author and does not have an obvious presentation mechanism. Previous work has concentrated on the ideas of generic RDF graph visualization and RDF Schema-based form generation. In this paper, we present a comprehensive platform for constructing end user applications that create, manipulate, and visualize arbitrary RDF-encoded information, adding another layer to the abstraction cake. We discuss a programming environment specifically designed for manipulating RDF and introduce user interface concepts on top that allow the developer to quickly assemble applications that are based on RDF data models. Also, because user interface specifications and program logic are themselves describable in RDF, applications built upon our framework enjoy properties such as network updatability, extensibility, and end user customizability - all desirable characteristics in the spirit of the Semantic Web.
User Interaction Experience for Semantic Web Information

The Semantic Web project  aims to add semantics to the existing World Wide Web. We propose an extension of the Web’s user interaction experience to take advantage of the added semantics. This user experience maintains the Web’s original navigation paradigm, although all URIs, not just URLs, can be used to address information objects. URIs form the superset of URLs and can name resources other than just those with retrievable contents. Information is displayed in webpage-like presentations in which each UI element is associated with the information object that the element represents. UI elements serve as proxies through which the user can manipulate information objects. Uniform support for direct manipulation complements the Web’s navigation paradigm to create an informationcentric environment for interacting with information. In addition, we advocate the use of small cooperative tools over large standalone applications to further promote this information-centric paradigm.
Chord: a scalable peer-to-peer lookup protocol for internet applications

A fundamental problem that confronts peer-to-peer applications is the efficient location of the node that stores a desired data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis and simulations show that Chord is scalable: Communication cost and the state maintained by each node scale logarithmically with the number of Chord nodes.
Learning Classes Correlated to a Hierarchy

Trees are a common way of organizing large amounts of information by placing items with similar characteristics near one another in the tree. We introduce a classification problem where a given tree structure gives us information on the best way to label nearby elements. We suggest there are many practical problems that fall under this domain. We propose a way to map the classification problem onto a standard Bayesian inference problem. We also give a fast, specialized inference algorithm that incrementally updates relevant probabilities. We apply this algorithm to web-classification problems and show that our algorithm empirically works well. Work funded by the Oxygen Partnership, NTT, and the Packard Foundation.
User Interfaces for Supporting Multiple Categorization

As the amount of information stored on and accessed by computer has increased over the past twenty years, the tools available for organizing and retrieving such information have become outdated. The folder paradigm has dominated existing user interfaces as the primary mechanism for organizing information for day-to-day use. This paradigm encourages many-to-one placement of documents into strictly hierarchical containers. In this paper we examine an alternative organization and navigation mechanism that promotes membership in multiple overlapping categories (as opposed to storage containment). In particular, we explore the user interface consequences of multiple categorization support being made conveniently available from within Web browsers. We have carried out user studies providing evidence that compared to the folder paradigm, multiple categorization not only improves organization and retrieval times but also matches more closely with the way users naturally think about organizing their information.
New Algorithms for Load Balancing in Peer-to-Peer Systems

Load balancing is a critical issue for the efficient operation of peer-to-peer networks. We give new protocols for several scenarios, whose provable performance guarantees are within a constant factor of optimal. First, we give an improved version of consistent hashing, a scheme used for item to node assignments in the Chord system. In its original form, it required every network node to operate O(log n) virtual nodes to achieve a balanced load, causing a corresponding increase in space and bandwidth usage. Our protocol eliminates the necessity of virtual nodes while maintaining a balanced load. Improving on related protocols, our scheme allows for the deletion of nodes and admits a simpler analysis, since the assignments do not depend on the history of the network. We then analyze several simple protocols for load sharing by movements of data from higher loaded to lower loaded nodes. These protocols can be extended to preserve the ordering of data items. As an application, we use the last protocol to give an efficient implementation of a distributed data structure for range searches on ordered data.
Tackling the Poor Assumptions of Naive Bayes Text Classifiers

Naive Bayes is often used as a baseline in text classification because it is fast and easy to implement. Its severe assumptions make such efficiency possible but also adversely affect the quality of its results. In this paper we propose simple, heuristic solutions to some of the problems with Naive Bayes classifiers, addressing both systemic issues as well as problems that arise because text is not actually generated according to a multinomial model. We find that our simple corrections result in a fast algorithm that is competitive with state-of-the-art text classification algorithms such as the Support Vector Machine.
Surviving the Information Explosion: How People Find Their Electronic Information

2 0 0 3 m a s s a c h u s e t t s i n s t i t u t e o f t e c h n o l o g y, c a m b r i d g e , m a 0 2 1 3 9 u s a — w w w. a i. m i t. e d u m a s s a c h u s e t t s i n s t i t u t e o f t e c h n o l o g y — a r t i f i c i a l i n t e l l i g e n c e l a b o r a t o r y @ MIT  We report on a study of how people look for information within email, files, and the Web. When locating a document or searching for a specific answer, people relied on their contextual knowledge of their information target to help them find it, often associating the target with a specific document. They appeared to prefer to use this contextual information as a guide in navigating locally in small steps to the desired document rather than directly jumping to their target. We found this behavior was especially true for people with unstructured information organization. We discuss the implications of our findings for the design of personal information management tools.
Approximation algorithms for orienteering and discounted-reward TSP

In this paper, we give the first constant-factor approximation algorithm for the rooted orienteering problem, as well as a new problem that we call the Discounted-Reward TSP, motivated by robot navigation. In both problems, we are given a graph with lengths on edges and prizes (rewards) on nodes, and a start node s. In the orienteering problem, the goal is to find a path that maximizes the reward collected, subject to a hard limit on the total length of the path. In the Discounted-Reward TSP, instead of a length limit we are given a discount factor /spl gamma/, and the goal is to maximize total discounted reward collected, where reward for a node reached at time t is discounted by /spl gamma//sup t/. This is similar to the objective considered in Markov decision processes (MDPs) except we only receive a reward the first time a node is visited. We also consider tree and multiple-path variants of these problems and provide approximations for those as well. Although the unrooted orienteering problem, where there is no fixed start node s, has been known to be approximable using algorithms for related problems such as k-TSP (in which the amount of reward to be collected is fixed and the total length is approximately minimized), ours is the first to approximate the rooted question, solving an open problem based on B. Awerbuch et al. (1999) and E.M. Arkin (1998).
Empirical development of an exponential probabilistic model for text retrieval: using textual analysis to build a better model

Much work in information retrieval focuses on using a model of documents and queries to derive retrieval algorithms. Model based development is a useful alternative to heuristic development because in a model the assumptions are explicit and can be examined and refined independent of the particular retrieval algorithm. We explore the explicit assumptions underlying the naïve framework by performing computational analysis of actual corpora and queries to devise a generative document model that closely matches text. Our thesis is that a model so developed will be more accurate than existing models, and thus more useful in retrieval, as well as other applications. We test this by learning from a corpus the best document model. We find the learned model better predicts the existence of text data and has improved performance on certain IR tasks.
Koorde: A Simple Degree-Optimal Distributed Hash Table

Koorde is a new distributed hash table (DHT) based on Chord 15 and the de Bruijn graphs 2. While inheriting the simplicity of Chord, Koorde meets various lower bounds, such as O(log n) hops per lookup request with only 2 neighbors per node (where n is the number of nodes in the DHT), and O(log n/log log n) hops per lookup request with O(log n) neighbors per node.
User interface continuations

Dialog boxes that collect parameters for commands often create ephemeral, unnatural interruptions of a program's normal execution flow, encouraging the user to complete the dialog box as quickly as possible in order for the program to process that command. In this paper we examine the idea of turning the act of collecting parameters from a user into a first class object called a user interface continuation. Programs can create user interface continuations by specifying what information is to be collected from the user and supplying a callback (i.e., a continuation) to be notified with the collected information. A partially completed user interface continuation can be saved as a new command, much as currying and partially evaluating a function with a set of parameters produces a new function. Furthermore, user interface continuations, like other continuation-passing paradigms, can be used to allow program execution to continue uninterrupted while the user determines a command's parameters at his or her leisure.
“ A P 2 P Storage System Based on Erasure Codes

Peer-to-Peer systems, almost unheard of a few years ago, are now becoming one of the most popular Internet applications. The most important use of P2P systems is to store and share files. In a P2P network, nodes may join and leave the system at any time. As a result of the intermittent availability of the nodes, ensuring high availability of the stored data is an interesting and challenging problem. In particular, the tradeoffs between the availability of the files and the redundancy involved in storing the data is not yet well-understood.
6.856 — Randomized Algorithms

(b) From (a) we know that the expected time until some machine is successful is Θ(e). Since the problem is symmetric in all n machines, the successful machine is equally likely to be any of the machines. This is also true for the next successful machine, and so on. So the question is how long it takes for all machines to be successful, if every Θ(e) steps, a random machine is successful. This is just the coupon collectors problem: we expect Θ(n ln n) successful broadcasts before every machine actually sent their first packet. So the expected time for all machines to be successful is Θ(ne ln n).
Analysis of the evolution of peer-to-peer systems

In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system that implements a distributed hash table abstraction, and study the process by which Chord maintains its distributed state as nodes join and leave the system. We argue that traditional performance measures based on run-time are uninformative for a continually running P2P network, and that the rate at which nodes in the network need to participate to maintain system state is a more useful metric. We give a general lower bound on this rate for a network to remain connected, and prove that an appropriately modified version of Chord's maintenance rate is within a logarithmic factor of the optimum rate.
Linear Programming-Based Decoding of Turbo-Like Codes and its Relation to Iterative Approaches

In recent work (Feldman and Karger ), we introduced a new a pproach to decoding turbo-like codes based on linear programming (LP). We gave a precise characterization of the noise patterns that cause decoding error under the binar y symmetric and additive white Gaussian noise channels. We used this characterization to p rove that the word error rate is bounded by an inverse polynomial in the code length. Furth ermore, for any turbo-like code, our algorithm has the ML certificateproperty: whenever it outputs a code word, it is guaranteed to be the maximum-likelihood (ML) code word. In this paper we extend these results and give an iterative de coder whose output is equivalent to that of the LP decoder. We also extend the ML cer tifi ate property to the more efficient iterativetree reweighted max-product message-passing algorithm developed by Wainwright, Jaakkola, and Willsky : we show that whenev er this algorithm converges to a code word, it must be the ML code word. Finally, we demonstrate experimentally that the noise patt erns that cause decoding error in the LP decoder also cause decoding error in the stand ard iterative sum-product and max-product (min-sum) message-passing algorithms. Conse quently, the deterministically constructible interleaver used by the LP decoder to achieve its bounds on error rate is useful in practice not only for the LP decoder, but for these s tandard iterative decoders as
Random sampling in residual graphs

Consider an <i>n</i>-vertex, <i>m</i>-edge, undirected graph with maximum flow value <i>v</i>. We give a new <i>Õ</i>(<i>m+nv</i>)-time maximum flow algorithm based on finding augmenting paths in random samples of the edges of residual graphs. After assigning certain special sampling probabilities to edges in <i>Õ</i>(<i>m</i>) time, our algorithm is very simple: repeatedly find an augmenting path in a random sample of edges from the residual graph.
Haystack : A Platform for Personalized Information Management

Problems and  The personal computer, though acclaimed for its ever increasing capabilities to process data, has yet to become a place convenient enough for the user to store and manage all of his or her various types of information. Currently, the user is restricted to storing only a limited set of information, including e-mail, text documents, pictures, audio files, contacts, and meetings. Without becoming a database administrator, the user struggles to find a place to record useful daily information (e.g. medications taken, shopping lists) and accumulated long-termed data (e.g. blood type, history of illnesses, a list of favorite restaurants, an inventory of insured and uninsured properties). Text editors and spreadsheets allow for content composition, but they lack capabilities for inputting semantics that would facilitate automatic information processing. Using existing software applications, the user cannot query for the favorite restaurant closest to a friend’s house, ask for a list of uninsured items of more than $100 in value, or find out how often he or she buys milk.
Decoding turbo-like codes via linear programming

We introduce a novel algorithm for decoding turbo-like codes based on linear programming. We prove that for the case of repeat-accumulate (RA) codes, under the binary symmetric channel with a certain constant threshold bound on the noise, the error probability of our algorithm is bounded by an inverse polynomial in the code length. Our linear program (LP) minimizes the distance between the received bits and binary variables representing the code bits. Our LP is based on a representation of the code where code words are paths through a graph. Consequently, the LP bears a strong resemblance to the min-cost flow LP. The error bounds are based on an analysis of the probability, over the random noise of the channel, that the optimum solution to the LP is the path corresponding to the original transmitted code word.
Adenine: A Metadata Programming Language

Metadata in the Haystack environment is expressed according to the Resource Description Framework (RDF) (RDF, 1998). In essence, RDF is a format for describing semantic networks or directed graphs with labeled edges. Nodes and edges are named with uniform resource identifiers (URIs), making them globally unique and thus useful in a distributed environment. Node URIs are used to represent objects, such as web pages, people, agents, and documents. A directed edge connecting two nodes expresses a relationship, given by the URI of the edge.
Basic Concepts for Managing Semi-structured Information in Haystack

The Haystack platform (Huynh et al., 2002) is designed to store and manage personal information such as e-mail, documents, contacts, meetings, etc. These types of data are semi-structured in nature and thus are better expressed as semantic networks rather than as tables. We believe that any system whose primary data model is semi-structured has at least four intrinsic needs. First, as the semantic data networks inevitably grow, there is a need to organize them conveniently and flexibly and to navigate them systematically. Second, since there is an enormous amount of structured and unstructured data in existence, the system must also allow data exchange with the outside world to both extend its knowledgebase and to facilitate collaboration with users of other systems. Third, as a consequence of collaboration, managing the cooperation of services among various systems becomes important. Finally, cooperation requires trust management for different sources of information. In Haystack, we provide built-in solutions for all of these four needs for organization, external data integration, service cooperation, and trust management. This paper discusses the various techniques that we use to fulfill these needs.