895559
Co-Training and Expansion: Towards Bridging Theory and Practice
Co-training is a method for combining labeled and unlabeled data when examples can be thought of as containing two distinct sets of features. It has had a number of practical successes, yet previous theoretical analyses have needed very strong assumptions on the data that are unlikely to be satisfied in practice. 
 
In this paper, we propose a much weaker "expansion" assumption on the underlying data distribution, that we prove is sufficient for iterative co-training to succeed given appropriately strong PAC-learning algorithms on each feature set, and that to some extent is necessary as well. This expansion assumption in fact motivates the iterative nature of the original co-training algorithm, unlike stronger assumptions (such as independence given the label) that allow a simpler one-shot co-training to succeed. We also heuristically analyze the effect on performance of noise in the data. Predicted behavior is qualitatively matched in synthetic experiments on expander graphs.
5253044
Towards the classical communication complexity of entanglement distillation protocols with incomplete information
Entanglement is an essential resource for quantum communication and quantum computation, similar to shared random bits in the classical world. Entanglement distillation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity of these protocols is the minimal amount of classical information that needs to be exchanged for the conversion. In this paper, we focus on the communication complexity of protocols that operate with incomplete information, i.e., where the inputs are mixed states and/or prepared adversarially. We consider three models of imperfect entanglement, namely, the bounded measurement model, the depolarization model, and the fidelity model. We describe these models as well as the motivations for studying them. For the bounded measurement model and the depolarization model, we prove tight and almost-tight bounds on the output quality of non-interactive protocols. For the fidelity model, we prove a lower bound that matches the upper bound given by Ambainis et al., and thus completely characterizes communication complexity of entanglement distillation protocols for this model. Our result also suggests the optimality of the BB84 protocol in terms of communication complexity. We emphasize that although some of the results appear intuitively straightforward, their proofs are not. In fact, two novel techniques are developed for proving these results. We believe that these techniques are of independent interests, too.
454393
Private Keyword-Based Push and Pull with Applications to Anonymous Communication
We propose a new keyword-based Private Information Retrieval (PIR) model that allows private modification of the database from which information is requested. In our model, the database is distributed over n servers, any one of which can act as a transparent interface for clients. We present protocols that support operations for accessing data, focusing on privately appending labelled records to the database (push) and privately retrieving the next unseen record appended under a given label (pull). The communication complexity between the client and servers is independent of the number of records in the database (or more generally, the number of previous push and pull operations) and of the number of servers. Our scheme also supports access control oblivious to the database servers by implicitly including a public key in each push, so that only the party holding the private key can retrieve the record via pull. To our knowledge, this is the first system that achieves the following properties: private database modification, private retrieval of multiple records with the same keyword, and oblivious access control. We also provide a number of extensions to our protocols and, as a demonstrative application, an unlinkable anonymous communication service using them.
61091746
Resource Fairness and Composability of Cryptographic Protocols
We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to similar previously proposed definitions, our definition follows the standard simulation paradigm and enjoys strong composability properties. In particular, our definition is similar to the security definition in the universal composability (UC) framework, but works in a model that allows any party to request additional resources from the environment to deal with dishonest parties that may prematurely abort. 
 
In this model we specify the ideally fair functionality as allowing parties to “invest resources” in return for outputs, but in such an event offering all other parties a fair deal. (The formulation of fair dealings is kept independent of any particular functionality, by defining it using a “wrapper.”) Thus, by relaxing the notion of fairness, we avoid a well-known impossibility result for fair multi-party computation with corrupted majority; in particular, our definition admits constructions that tolerate arbitrary number of corruptions. We also show that, as in the UC framework, protocols in our framework may be arbitrarily and concurrently composed. 
 
Turning to constructions, we define a “commit-prove-fair-open” functionality and design an efficient resource-fair protocol that securely realizes it, using a new variant of a cryptographic primitive known as “time-lines.” With (the fairly wrapped version of) this functionality we show that some of the existing secure multi-party computation protocols can be easily transformed into resource-fair protocols while preserving their security.
1745284
On Simulation-Sound Trapdoor Commitments
We study the recently introduced notion of a simulation-sound trapdoor commitment (SSTC) scheme. In this paper, we present a new, simpler definition for an SSTC scheme that admits more efficient constructions and can be used in a larger set of applications. Specifically, we show how to construct SSTC schemes from any one-way functions, and how to construct very efficient SSTC schemes based on specific number-theoretic assumptions. We also show how to construct simulation-sound, non-malleable, and universally-composable zero-knowledge protocols using SSTC schemes, yielding, for instance, the most efficient universally-composable zero-knowledge protocols known. Finally, we explore the relation between SSTC schemes and non-malleable commitment schemes by presenting a sequence of implication and separation results, which in particular imply that SSTC schemes are non-malleable.
5335881
On statistical query sampling and NMR quantum computing
We introduce a "statistical query sampling" model, in which the goal of an algorithm is to produce an element in a hidden set S/spl sube/{0,1}/sup n/ with reasonable probability. The algorithm gains information about S through oracle calls (statistical queries), where the algorithm submits a query function g(/spl middot/) and receives an approximation to Pr/sub x/spl isin/S/[g(x)=1]. We show how this model is related to NMR quantum computing, in which only statistical properties of an ensemble of quantum systems can be measured, and in particular to the question of whether one can translate standard quantum algorithms to the NMR setting without putting all of their classical postprocessing into the quantum system. Using Fourier analysis techniques developed in the related context of statistical query learning, we prove a number of lower bounds (both information-theoretic and cryptographic) on the ability of algorithms to produce an x/spl isin/S, even when the set S is fairly simple. These lower bounds point out a difficulty in efficiently applying NMR quantum computing to algorithms such as Shor's and Simon's algorithm that involve significant classical postprocessing. We also explicitly relate the notion of statistical query sampling to that of statistical query learning.
6388420
Proof: A DHT-Based Peer-to-Peer Search Engine
In this paper we focus on building a large scale keyword search service over structured peer-to-peer (P2P) networks. Current state-of-the-art keyword search approaches for structured P2P systems are based on inverted list intersection. However, the biggest challenge in those approaches is that when the indices are distributed over peers, a simple query may cause a large amount of data to be transmitted over the network. We propose a new P2P keyword search scheme, called "Proof", to reduce network traffic for queries. The key idea is storing a content summary for each Web page in the inverted list, so that a query can be processed by only transmitting a small size of candidate results. Our simulation results showed that, compared with previous DHT-based P2P systems, Proof can dramatically reduce network traffic and computation time. It provides 100% precision and 90.09% recall of search results, at an acceptable cost of storage overhead, even when the number of peers and documents increases continually
40685825
Value Range Queries on Earth Science Data via Histogram Clustering
Remote sensing data as well as ground-based and model output data about the Earth system can be very large in volume. On the other hand, in order to use the data efficiently, scientists need to search for data based on not only metadata but also actual data values. To answer value range queries by scanning very large volumes of data is obviously unrealistic. This article studies a clustering technique on histograms of data values on predefined cells to index the cells. Through this index system, the so-called statistical range queries can be answered quickly and approximately together with an accuracy assessment. Examples of using this technique for Earth science data sets are given in this article.
16162932
AntSearch: An Ant Search Algorithm in Unstructured Peer-to-Peer Networks
The most prevalent peer-to-peer (P2P) application till today is file sharing, and unstructured P2P networks can support inherent heterogeneity of peers, are highly resilient to peers’ failures, and incur low overhead at peer arrivals and departures. Dynamic querying (DQ) is a new flooding technique which could estimate a proper time-to-live (TTL) value for a query flooding by estimating the popularity of the searched files, and retrieve sufficient results under controlled flooding range for reducing network traffic. Recent researches show that a large amount of peers in the P2P file sharing system are the free-riders, and queries are seldom hit by those peers. The free-riders problem causes a large amount of redundant messages in the DQ-like search algorithm. In this paper, we proposed a new search algorithm, called "AntSearch", to solve the problem. In AntSearch, each peer maintains its hit rate of previous queries, and records a list of pheromone values of its immediate neighbors. Based on the pheromone values, a query is only flooded to those peers which are not likely to be the free-riders. Our simulation results show that, compared with DQ and its enhanced algorithm DQ+, the AntSearch algorithm averagely reduces 50% network traffic at almost the same search latency as DQ+, while retrieving sufficient results for a query with a given required number of results.
10296067
IRIS at TREC-8
We tested two relevance feedback models, an adaptive linear model and a probabilistic model, using massive feedback query expansion in TREC-5 (Sumner & Shaw, 1997), experimented with a three-valued scale of relevance and reduced feedback query expansion in TREC-6 (Sumner, Yang, Akers & Shaw, 1998), and examined the effectiveness of relevance feedback using a subcollection and the effect of system features in an interactive retrieval system called IRIS (Information Retrieval Interactive System) in TREC-7 (Yang, Maglaughlin, Mehol & Sumner, 1999). In TREC-8, we continued our exploration of relevance feedback approaches. Based on the result of our TREC-7 interactive experiment, which suggested relevance feedback using user-selected passages to be an effective alternative to conventional document feedback, our TREC-8 interactive experiment compared a passage feedback system and a document feedback system that were identical in all aspects except for the feedback mechanism. For the TREC-8 ad-hoc task, we merged results of pseudo-relevance feedback to subcollections as in TREC-7. Our results were consistent with that of TREC-7. The results of passage feedback, whose system log showed high level of searcher intervention, was superior to the document feedback results. As in TREC-7, our ad-hoc results showed high precision in top few documents, but performed poorly overall compared to results using the collection as a whole.
21367461
A feasible method to find areas with constraints using hierarchical depth-first clustering
Addresses a reliable, feasible method to find geographical areas with constraints using hierarchical depth-first clustering. The method involves multi-level hierarchical clustering with a depth-first strategy, depending on whether the area of each cluster satisfies the given constraints. The attributes used in the hierarchical clustering are the coordinates of the grid data points. The constraints are an average value range and the minimum size of an area with a small proportion of missing data points. Convex-hull and point-in-polygon algorithms are involved in examining the constraint satisfaction. The method is implemented for an Earth science data set for vegetation studies - the Normalized Difference Vegetation Index (NVDI).