61441845
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.
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.
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.
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.
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.
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).
6906500
Web Appearance Disambiguation of Personal Names Based on Network Motif
Searching for information about a particular person is a common activity on search engines. However, current search engines do not provide any special function for search a person. Previous research has solved the problem by using additional background knowledge, such as a friend list, to cluster the searched Web pages. However, it is still difficult to retrieve and choose suitable background knowledge. In this paper, we propose a Web appearance disambiguation (WAD) system to solve the problem by only using the hyperlink structures between Web pages. The key idea of the WAD system is to find out smaller node motifs as evidences of close relationship between pages for clustering searched Web pages. Our experimental results show that, under no background knowledge, the performance of the WAD system achieves 70% for the F-measure
37157806
An interactive WWW search engine for user-defined collections
Given the dynamic nature and the quantity of information on the WWW, many individual users and organizations compile and use focused WWW resource lists related to a particular topic or subject domain. The IRISWeb system extends this concept such that any user-defined set of WWW pages (a virtual collection) can be retrieved, indexed, and searched using a powerful full-text search engine with a relevance-feedback interface. This capability adds full-text searching to highly customized subsets of the WWW. Here we describe the IRISWeb software and an experiment that highlights its potential.
712798
IRIS at TREC-7
In our TREC-5 ad-hoc experiment, we tested two relevance feedback models, an adaptive linear model and a probabilistic model, using massive feedback query expansion (Sumner & Shaw, 1997). For our TREC-6 interactive experiment, we developed an interactive retrieval system called IRIS (Information Retrieval Interactive System), which implemented modified versions of the feedback models with a three-valued scale of relevance and reduced feedback query expansion (Sumner, Yang, Akers & Shaw, 1998). The goal of the IRIS design was to provide users with ample opportunities to interact with the system throughout the search process. For example, users could supplement the initial query by choosing from a list of statistically significant, two-word collocations, or add and delete query terms as well as change their weights at each search iteration. Unfortunately, it was difficult to tell how much effect each IRIS feature had on the retrieval outcome due to such factors as strong searcher effect and major differences between the experimental and control systems. In our TREC-7 interactive experiment, we attempted to isolate the effect of a given system feature by making the experimental and control systems identical, save for the feature we were studying. In one interactive experiment, the difference between the experimental and control systems was the display and modification capability of term weights. In another experiment, the difference was relevance feedback by passage versus document. For the TREC-7 ad-hoc task, we wanted to examine the effectiveness of relevance feedback using a subcollection in order to lay the groundwork for future participation in the Very Large Corpus experiment. Though the pre-test results showed the retrieval effectiveness of a subcollection approach to be competitive with a whole collection approach, we were not able to execute the subcollection retrieval in the actual ad-hoc experiment due to hardware problems. Instead, our ad-hoc experiment consisted of a simple initial retrieval run and a pseudo-relevance feedback run using the top 5 documents as relevant and the 100 document as non-relevant. Though the precision was high in the top few documents, the ad-hoc results were below average by TREC measures as expected. In the interactive experiment, the passage feedback results were better than the document feedback results, and the results of the simple interface system that did not display query term weights were better than that of the more complex interface system that displayed query term weights and allowed users to change these weights. Overall interactive results were about average among participants.
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.