We study the relationship between Web users and service providers, taking a sociotechnical approach and focusing particularly (but not exclusively) on privacy and security of personal data. Much conventional Web-security practice seeks to protect benevolent parties, both individuals and organizations, against purely malevolent adversaries in an effort to prevent catastrophic events such as data breaches, ransomware attacks, and denial of service. By contrast, we highlight the dynamics among the parties that much conventional security technology seeks to protect. We regard most interactions between users and providers as implicit negotiations that, like the interactions between buyers and sellers in a marketplace, have both adversarial and cooperative aspects. Our goal is to rebalance these negotiations in order to give more power to users; toward that end we advocate the adoption of two techniques, one technical and one organizational. Technically, we introduce the Platform for Untrusted Resource Evaluation (PURE), a content-labeling framework that empowers users to make informed decisions about service providers, reduces the ability of providers to induce behaviors that benefit them more than users, and requires minimal time and effort to use. On the organizational side, we concur with Gordon-Tapiero et al. [19] that a collective approach is necessary to rebalance the power dynamics between users and providers; in particular, we suggest that the data co-op, an organizational form suggested by Ligett and Nissim [25] and Pentland and Hardjono [28], is a natural setting in which to deploy PURE and similar tools.

We consider the task of interorganizational data sharing, in which data owners, data clients, and data subjects have different and sometimes competing privacy concerns. One real-world scenario in which this problem arises concerns law-enforcement use of phone-call metadata: The data owner is a phone company, the data clients are law-enforcement agencies, and the data subjects are individuals who make phone calls. A key challenge in this type of scenario is that each organization uses its own set of proprietary intraorganizational attributes to describe the shared data; such attributes cannot be shared with other organizations. Moreover, data-access policies are determined by multiple parties and may be specified using attributes that are not directly comparable with the ones used by the owner to specify the data. We propose a system architecture and a suite of protocols that facilitate dynamic and efficient interorganizational data sharing, while allowing each party to use its own set of proprietary attributes to describe the shared data and preserving the confidentiality of both data records and proprietary intraorganizational attributes. We introduce the novel technique of Attribute-Based Encryption with Oblivious Attribute Translation (OTABE) , which plays a crucial role in our solution. This extension of attribute-based encryption uses semi-trusted proxies to enable dynamic and oblivious translation between proprietary attributes that belong to different organizations; it supports hidden access policies, direct revocation, and fine-grained, data-centric keys and queries. We prove that our OTABE-based framework is secure in the standard model and provide two real-world use cases.

Organizational networks are vulnerable to trafficanalysis attacks that enable adversaries to infer sensitive information fromnetwork traffic—even if encryption is used. Typical anonymous communication networks are tailored to the Internet and are poorly suited for organizational networks.We present PriFi, an anonymous communication protocol for LANs, which protects users against eavesdroppers and provides high-performance traffic-analysis resistance. PriFi builds onDining Cryptographers networks (DC-nets), but reduces the high communication latency of prior designs via a new client/relay/server architecture, in which a client’s packets remain on their usual network path without additional hops, and in which a set of remote servers assist the anonymization process without adding latency. PriFi also solves the challenge of equivocation attacks, which are not addressed by related work, by encrypting traffic based on communication history. Our evaluation shows that PriFi introduces modest latency overhead (≈ 100ms for 100 clients) and is compatible with delay-sensitive applications such as Voice-over-IP.

Increasing use of social media in campaigns raises the question of whether one can predict the voting behavior of social-network users who do not disclose their political preferences in their online profiles. Prior work on this task only considered users who generate politically oriented content or voluntarily disclose their political preferences online. We avoid this bias by using a novel Bayesian-network model that combines demographic, behavioral, and social features; we apply this novel approach to the 2016 U.S. Presidential election. Our model is highly extensible and facilitates the use of incomplete datasets. Furthermore, our work is the first to apply a semi-supervised approach for this task: Using the EM algorithm, we combine labeled survey data with unlabeled Facebook data, thus obtaining larger datasets as well as addressing self-selection bias.

Abstract Motivated by the effectiveness of correlation attacks against Tor, the censorship arms race, and observations of malicious relays in Tor, we propose that Tor users capture their trust in network elements using probability distributions over the sets of elements observed by network adversaries. We present a modular system that allows users to efficiently and conveniently create such distributions and use them to improve their security. To illustrate this system, we present two novel types of adversaries. First, we study a powerful, pervasive adversary that can compromise an unknown number of Autonomous System organizations, Internet Exchange Point organizations, and Tor relay families. Second, we initiate the study of how an adversary might use Mutual Legal Assistance Treaties (MLATs) to enact surveillance. As part of this, we identify submarine cables as a potential subject of trust and incorporate data about these into our MLAT analysis by using them as a proxy for adversary power. Finally, we present preliminary experimental results that show the potential for our trust framework to be used by Tor clients and services to improve security.

Two-party secure-function evaluation (SFE) has become significantly more feasible, even on resource-constrained devices, because of advances in server-aided computation systems. However, there are still bottlenecks, particularly in the input-validation stage of a computation. Moreover, SFE research has not yet devoted sufficient attention to the important problem of retaining state after a computation has been performed so that expensive processing does not have to be repeated if a similar computation is done again. This paper presents PartialGC, an SFE system that allows the reuse of encrypted values generated during a garbled-circuit computation. We show that using PartialGC can reduce computation time by as much as 96% and bandwidth by as much as 98% in comparison with previous outsourcing schemes for secure computation. We demonstrate the feasibility of our approach with two sets of experiments, one in which the garbled circuit is evaluated on a mobile device and one in which it is evaluated on a server. We also use PartialGC to build a privacy-preserving ``friend-finder'' application for Android. The reuse of previous inputs to allow stateful evaluation represents a new way of looking at SFE and further reduces computational barriers.

The proliferation of online sensitive data about individuals and organizations makes concern about the privacy of these data a top priority. There have been many formulations of privacy and, unfortunately, many negative results about the feasibility of maintaining privacy of sensitive data in realistic networked environments. We formulate communication-complexity-based definitions, both worst case and average case, of a problem’s privacy-approximation ratio . We use our definitions to investigate the extent to which approximate privacy is achievable in a number of standard problems: the 2 nd -price Vickrey auction, Yao’s millionaires problem, the public-good problem, and the set-theoretic disjointness and intersection problems. For both the 2 nd -price Vickrey auction and the millionaires problem, we show that not only is perfect privacy impossible or infeasibly costly to achieve, but even close approximations of perfect privacy suffer from the same lower bounds. By contrast, if the inputs are drawn uniformly at random from { 0,…, 2 k -1}, then, for both problems, simple and natural communication protocols have privacy-approximation ratios that are linear in k (i.e., logarithmic in the size of the input space). We also demonstrate tradeoffs between privacy and communication in a family of auction protocols. We show that the privacy-approximation ratio provided by any protocol for the disjointness and intersection problems is necessarily exponential (in k ). We also use these ratios to argue that one protocol for each of these problems is significantly fairer than the others we consider (in the sense of relative effects on the privacy of the different players).

Interdomain routing involves coordination among mutually distrustful parties, leading to the requirements that BGP provide policy autonomy, flexibility, and privacy. BGP provides these properties via the distributed execution of policy-based decisions during the iterative route computation process. This approach has poor convergence properties, makes planning and failover difficult, and is extremely difficult to change. To rectify these and other problems, we propose a radically different approach to interdomain-route computation, based on secure multi-party computation (SMPC). Our approach provides stronger privacy guarantees than BGP and enables the deployment of new policy paradigms. We report on an initial exploration of this idea and outline future directions for research.

In this talk, I will address three aspects of user privacy in advertiser-supported, online services. First, I present the design of a novel browser plug-in that enables anonymous search. Next, I consider economic aspects of user privacy from the point of view of the operator of an advertiser-supported website. Finally, I present recent work on "accountability" in online activity, where the goal is to hold website operators responsible for appropriate handling of users' sensitive information rather than to prevent users from ever providing information that might be misused.

Many modern network designs incorporate "failover" paths into routers' forwarding tables. We initiate the theoretical study of such resilient routing tables.

We perform a probabilistic analysis of onion routing. The analysis is presented in a black-box model of anonymous communication in the Universally Composable (UC) framework that abstracts the essential properties of onion routing in the presence of an active adversary who controls a portion of the network and knows all a priori distributions on user choices of destination. Our results quantify how much the adversary can gain in identifying users by exploiting knowledge of their probabilistic behavior. In particular, we show that, in the limit as the network gets large, a user u 's anonymity is worst either when the other users always choose the destination u is least likely to visit or when the other users always choose the destination u chooses. This worst-case anonymity with an adversary that controls a fraction b of the routers is shown to be comparable to the best-case anonymity against an adversary that controls a fraction √ b .

We propose a focus on accountability as a mechanism for ensuring security in information systems. To that end, we present a formal definition of it accountability in information systems. Our definition is more general and potentially more widely applicable than the accountability notions that have previously appeared in the security literature. In particular, we treat in a unified manner scenarios in which accountability is enforced automatically and those in which enforcement must be mediated by an authority; similarly, our formalism includes scenarios in which the parties who are held accountable can remain anonymous and those in which they must be identified by the authorities to whom they are accountable. Essential elements of our formalism include event traces and it utility functions and the use of these to define punishment and related notions.

Increasing use of computers and networks in business, government, recreation, and almost all aspects of daily life has led to a proliferation of online sensitive data about individuals and organizations. Consequently, concern about the privacy of these data has become a top priority, particularly those data that are created and used in electronic commerce. Despite many careful formulations and extensive study, there are still open questions about the feasibility of maintaining meaningful privacy in realistic networked environments. We formulate communication-complexity-based definitions, both worst-case and average-case, of a problem's privacy-approximation ratio. We use our definitions to investigate the extent to which approximate privacy is achievable in many well studied contexts: the 2ndprice Vickrey auction [20], the millionaires problem of Yao [22], the provisioning of a public good, and also set disjointness and set intersection. We present both positive and negative results and many interesting directions for future research.

We explore problems related to computing graph distances in the data-stream model. The goal is to design algorithms that can process the edges of a graph in an arbitrary order given only a limited amount of working memory. We are motivated by both the practical challenge of processing massive graphs such as the web graph and the desire for a better theoretical understanding of the data-stream model. In particular, we are interested in the trade-offs between model parameters such as per-data-item processing time, total space, and the number of passes that may be taken over the stream. These trade-offs are more apparent when considering graph problems than they were in previous streaming work that solved problems of a statistical nature. Our results include the following: (1) Spanner construction: There exists a single-pass, $\tilde{O}(tn^{1+1/t})$-space, $\tilde{O}(t^2n^{1/t})$-time-per-edge algorithm that constructs a $(2t+1)$-spanner. For $t=\Omega(\log n/{\log\log n})$, the algorithm satisfies the semistreaming space restriction of $O(n\operatorname{polylog}n)$ and has per-edge processing time $O(\operatorname{polylog}n)$. This resolves an open question from [J. Feigenbaum et al., Theoret. Comput. Sci., 348 (2005), pp. 207–216]. (2) Breadth-first-search (BFS) trees: For any even constant k, we show that any algorithm that computes the first k layers of a BFS tree from a prescribed node with probability at least $2/3$ requires either greater than $k/2$ passes or $\tilde{\Omega}(n^{1+1/k})$ space. Since constructing BFS trees is an important subroutine in many traditional graph algorithms, this demonstrates the need for new algorithmic techniques when processing graphs in the data-stream model. (3) Graph-distance lower bounds: Any t-approximation of the distance between two nodes requires $\Omega(n^{1+1/t})$ space. We also prove lower bounds for determining the length of the shortest cycle and other graph properties. (4) Techniques for decreasing per-edge processing: We discuss two general techniques for speeding up the per-edge computation time of streaming algorithms while increasing the space by only a small factor.

We consider the problem of finding highly correlated pairs in a large data set. That is, given a threshold not too small, we wish to report all the pairs of items (or binary attributes) whose (Pearson) correlation coefficients are greater than the threshold. Correlation analysis is an important step in many statistical and knowledge-discovery tasks. Normally, the number of highly correlated pairs is quite small compared to the total number of pairs. Identifying highly correlated pairs in a naive way by computing the correlation coefficients for all the pairs is wasteful. With massive data sets, where the total number of pairs may exceed the main-memory capacity, the computational cost of the naive method is prohibitive. In their KDD'04 paper [15], Hui Xiong et al. address this problem by proposing the TAPER algorithm. The algorithm goes through the data set in two passes. It uses the first pass to generate a set of candidate pairs whose correlation coefficients are then computed directly in the second pass. The efficiency of the algorithm depends greatly on the selectivity (pruning power) of its candidate-generating stage.In this work, we adopt the general framework of the TAPER algorithm but propose a different candidate-generation method. For a pair of items, TAPER's candidate-generation method considers only the frequencies (supports) of individual items. Our method also considers the frequency (support) of the pair but does not explicitly count this frequency (support). We give a simple randomized algorithm whose false-negative probability is negligible. The space and time complexities of generating the candidate set in our algorithm are asymptotically the same as TAPER's. We conduct experiments on synthesized and real data. The results show that our algorithm produces a greatly reduced candidate set - one that can be several orders of magnitude smaller than that generated by TAPER. Because of this, our algorithm uses much less memory and can be faster. The former is critical for dealing with massive data.

The routing of traffic between Internet domains, or Autonomous Systems (ASes), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP) [17]. Using BGP, autonomous systems can apply semantically rich routing policies to choose interdomain routes in a distributed fashion. This expressiveness in routing-policy choice supports domains' autonomy in network operations and in business decisions, but it comes at a price: The interaction of locally defined routing policies can lead to unexpected global anomalies, including route oscillations or overall protocol divergence (see, e.g., [20]). Networking researchers have addressed this problem by devising constraints on policies that guarantee BGP convergence without unduly limiting expressiveness and autonomy (see, e.g., [7, 8]).In addition to taking this engineering or "protocol-design" approach, researchers have approached interdomain routing from an economic or "mechanism-design" point of view. It is known that lowest-cost-path (LCP) routing can be implemented in a truthful, BGP-compatible manner [3] but that several other natural classes of routing policies cannot [2, 5]. In this paper, we present a natural class of interdomain-routing policies that is more realistic than LCP routing and admits incentive-compatible, BGP-compatible implementation. We also present several positive steps toward a general theory of incentive-compatible interdomain routing.

Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the inputs are held by different parties and may be extremely large. Furthermore, for some applications, the parties want to compute a function of their inputs securely without revealing more information than necessary. In this work, we study the question of simultaneously addressing the above efficiency and security concerns via what we call secure approximations. We start by extending standard definitions of secure (exact) computation to the setting of secure approximations. Our definitions guarantee that no additional information is revealed by the approximation beyond what follows from the output of the function being approximated. We then study the complexity of specific secure approximation problems. In particular, we obtain a sublinear-communication protocol for securely approximating the Hamming distance and a polynomial-time protocol for securely approximating the permanent and related #P-hard problems.

The Border Gateway Protocol (BGP) for interdomain routing is designed to allow autonomous systems (ASes) to express policy preferences over alternative routes. We model these preferences as arising from an AS's underlying utility for each route and study the problem of finding a set of routes that maximizes the overall welfare (i.e., the sum of all ASes' utilities for their selected routes).We show that, if the utility functions are unrestricted, this problem is NP-hard even to approximate closely. We then study a natural class of restricted utilities that we call next-hop preferences. We present a strategyproof, polynomial-time computable mechanism for welfare-maximizing routing over this restricted domain. However, we show that, in contrast to earlier work on lowest-cost routing mechanism design, this mechanism appears to be incompatible with BGP and hence difficult to implement in the context of the current Internet. Our contributions include a new complexity measure for Internet algorithms, the dynamic stability, which may be useful in other problem domains.

According to economic theory supported by empirical and laboratory evidence, the equilibrium price of a financial security reflects all of the information regarding the security's value. We investigate the computational process on the path toward equilibrium, where information distributed among traders is revealed step-by-step over time and incorporated into the market price. We develop a simplified model of an information market, along with trading strategies, in order to formalize the computational properties of the process. We show that securities whose payoffs cannot be expressed as weighted threshold functions of distributed input bits are not guaranteed to converge to the proper equilibrium predicted by economic theory. On the other hand, securities whose payoffs are threshold functions are guaranteed to converge, for all prior probability distributions. Moreover, these threshold securities converge in at most $n$ rounds, where $n$ is the number of bits of distributed information. We also prove a lower bound, showing a type of threshold security that requires at least $n/2$ rounds to converge in the worst case.

No abstract available.

We address the problem of authorization in large-scale, open, distributed systems. Authorization decisions are needed in electronic commerce, mobile-code execution, remote resource sharing, privacy protection, and many other applications. We adopt the trust-management approach, in which "authorization" is viewed as a " proof-of-compliance " problem: Does a set of credentials prove that a request complies with a policy?We develop a logic-based language, called Delegation Logic (DL), to represent policies, credentials, and requests in distributed authorization. In this paper, we describe D1LP, the monotonic version of DL. D1LP extends the logic-programming (LP) language Datalog with expressive delegation constructs that feature delegation depth and a wide variety of complex principals (including, but not limited to, k-out-of-n thresholds). Our approach to defining and implementing D1LP is based on tractably compiling D1LP programs into ordinary logic programs (OLPs). This compilation approach enables D1LP to be implemented modularly on top of existing technologies for OLP, for example, Prolog.As a trust-management language, D1LP provides a concept of proof-of-compliance that is founded on well-understood principles of logic programming and knowledge representation. D1LP also provides a logical framework for studying delegation.

The routing of traffic between... this paper, we address the problem of interdomain routing from a mechanism-design point of view. The application of mechanism-design principles to the study of routing is the subject of earlier work by Nisan and Ronen [15] and Hershberger and Suri [11]. In this paper, we formulate and solve a version of the routing-mechanism design problem that is different from the previously studied version in three ways that make it more accurately reflective of real-world interdomain routing: (1) we treat the nodes as strategic agents, rather than the links; (2) our mechanism computes lowest-cost routes for all source-destination pairs and payments for transit nodes on all of the routes (rather than computing routes and payments for only one source-destination pair at a time, as is done in [15,11]); (3) we show how to compute our mechanism with a distributed algorithm that is a straightforward extension to BGP and causes only modest increases in routingtable size and convergence time (in contrast with the centralized algorithms used in [15,11]). This approach of using an existing protocol as a substrate for distributed computation may prove useful in future development of Internet algorithms generally, not only for routing or pricing problems. Our design and analysis of a strategyproof, BGP-based routing mechanism provides a new, promising direction in distributed algorithmic mechanism design, which has heretofore been focused mainly on multicast cost sharing.

Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and the monitoring and operations of large systems. In network operations, raw data typically arrive in streams, and decisions must be made by algorithms that make one pass over each stream, throw much of the raw data away, and produce "synopses" or "sketches" for further processing. Moreover, network-generated massive data sets are often distributed: Several different, physically separated network elements may receive or generate data streams that, together, comprise one logical data set; to be of use in operations, the streams must be analyzed locally and their synopses sent to a central operations facility. The enormous scale, distributed nature, and one-pass processing requirement on the data sets of interest must be addressed with new algorithmic techniques. We present one fundamental new technique here: a space-efficient, one-pass algorithm for approximating the L 1 -difference $\sum_i|a_i-b_i|$ between two functions, when the function values a i and b i are given as data streams, and their order is chosen by an adversary. Our main technical innovation, which may be of interest outside the realm of massive data stream algorithmics, is a method of constructing families $\{V_j(s)\}$ of limited-independence random variables that are range-summable, by which we mean that $\sum_{j=0}^{c-1} V_j(s)$ is computable in time polylog(c) for all seeds s. Our L 1 -difference algorithm can be viewed as a "sketching" algorithm, in the sense of [Broder et al., J. Comput. System Sci., 60 (2000), pp. 630--659], and our technique performs better than that of Broder et al. when used to approximate the symmetric difference of two sets with small symmetric difference.

Article Share on Approximation and collusion in multicast cost sharing (extended abstract) Authors: J. Feigenbaum Yale University, New Haven, CT Yale University, New Haven, CTView Profile , A. Krishnamurthy Yale University, New Haven, CT Yale University, New Haven, CTView Profile , R. Sami Yale University, New Haven, CT Yale University, New Haven, CTView Profile , S. Shenker ACIRI/ICSI, Berkeley, CA ACIRI/ICSI, Berkeley, CAView Profile Authors Info & Claims EC '01: Proceedings of the 3rd ACM conference on Electronic CommerceOctober 2001 Pages 253–255https://doi.org/10.1145/501158.501190Online:14 October 2001Publication History 9citation174DownloadsMetricsTotal Citations9Total Downloads174Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We address the goal of making Delegation Logic (DL) into a practically implementable and tractable trust management system. DL (N. Li et al., 1999) is a logic based knowledge representation (i.e., language) for authorization in large scale, open, distributed systems. DL inferencing is computationally intractable and highly impractical to implement. We introduce a new version of Delegation Logic that remedies these difficulties. To achieve this, we impose a syntactic restriction and redefine the semantics somewhat. We show that, for this revised version of DL, inferencing is computationally tractable under the same commonly met restrictions for which Ordinary Logic Programs (OLP) inferencing is tractable (e.g., Datalog and bounded number of logical variables per rule). We give an implementation architecture for this version of DL; it uses a delegation compiler from DL to OLP and can modularly exploit a variety of existing OLP inference engines. As proof of concept, we have implemented a large expressive subset of this version of DL, using this architecture.

Article Free Access Share on Sharing the cost of muliticast transmissions (preliminary version) Authors: Joan Feigenbaum AT&T Labs - Research, 180 Park Ave., C203, Florham Park, NJ AT&T Labs - Research, 180 Park Ave., C203, Florham Park, NJView Profile , Christos Papadimitriou Computer Science Dept., U. C. Berkeley, Berkeley, CA Computer Science Dept., U. C. Berkeley, Berkeley, CAView Profile , Scott Shenker ACIRI/ICSI, 1947 Center Street, Suite 600, Berkeley, CA ACIRI/ICSI, 1947 Center Street, Suite 600, Berkeley, CAView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 218–227https://doi.org/10.1145/335305.335332Published:01 May 2000Publication History 49citation541DownloadsMetricsTotal Citations49Total Downloads541Last 12 Months25Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We introduce Delegation Logic (DL), a logic-based knowledge representation (i.e., language) that deals with authorization in large-scale, open distributed systems. Of central importance in any system for deciding whether requests should be authorized in such a system are delegation of authority, negation of authority, and conflicts between authorities. DL's approach to these issues and to the interplay among them borrows from previous work on delegation and trust management in the computer security literature and previous work on negation and conflict handling in the logic programming and nonmonotonic reasoning literature, but it departs from previous work in some crucial ways. We present the syntax and semantics of DL and explain our novel design choices. We focus on delegation, including explicit treatment of delegation depth and delegation to complex principles. Compared to previous logic-based approaches to authorization, DL provides a novel combination of features: it is based on logic programs, expresses delegation depth explicitly, and supports a wide variety of complex principles (including but not limited to k-out-of-n thresholds). Compared to previous approaches to trust management, DL provides another novel feature: a concept of proof-of-compliance that is not entirely ad-hoc and that is based on model theoretic semantics (just as usual logic programs have a model-theoretic semantics).

We give a space-efficient, one-pass algorithm for approximating the L/sup 1/ difference /spl Sigma//sub i/|a/sub i/-b/sub i/| between two functions, when the function values a/sub i/ and b/sub i/ are given as data streams, and their order is chosen by an adversary. Our main technical innovation is a method of constructing families {V/sub j/} of limited independence random variables that are range summable by which we mean that /spl Sigma//sub j=0//sup c-1/ V/sub j/(s) is computable in time polylog(c), for all seeds s. These random variable families may be of interest outside our current application domain, i.e., massive data streams generated by communication networks. Our L/sup 1/-difference algorithm can be viewed as a "sketching" algorithm, in the sense of (A. Broder et al., 1998), and our algorithm performs better than that of Broder et al., when used to approximate the symmetric difference of two sets with small symmetric difference.

A probabilistically checkable debate system (PCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between Player 1, who claims that the input x is in L, and Player 0, who claims that the input x is not in L. It is known that there is a PCDS for L in which V flips O(log n) coins and reads O(1) bits of the debate if and only if L is in PSPACE [A. Condon, J. Feigenbaum, C. Lund, and P. Shor, Chicago J. Theoret. Comput. Sci., 1995, No. 4]. In this paper, we restrict attention to RPCDSs, which are PCDSs in which Player 0 follows a very simple strategy: On each turn, Player 0 chooses uniformly at random from the set of legal moves. We prove the following result. Theorem. L has an RPCDS in which the verifier flips O(log n) coins and reads O(1) bits of the debate if and only if L is in PSPACE. This new characterization of PSPACE is used to show that certain stochastic PSPACE-hard functions are as hard to approximate closely as they are to compute exactly. Examples of such functions include optimization versions of Dynamic Graph Reliability, Stochastic Satisfiability, Mah-Jongg, Stochastic Generalized Geography, and other "games against nature" of the type introduced in [C. Papadimitriou, J. Comput. System Sci., 31 (1985), pp. 288--301].

We address two questions about self-reducibility-the power of adaptiveness in examiners that take advice and the relationship between random-self-reducibility and self-correctability. We first show that adaptive examiners are more powerful than nonadaptive examiners, even if the nonadaptive ones are nonuniform. Blum et al. (1993) showed that every random-self-reducible function is self-correctable. However, whether self-correctability implies random-self-reducibility is unknown. We show that, under a reasonable complexity hypothesis, there exists a self-correctable function that is not random-self-reducible. For P-sampleable distributions, however, we show that constructing a self-correctable function that is not random-self-reducible is as hard as proving that P/spl ne/PP.

Article Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions Share on Authors: Anne Condon View Profile , Joan Feigenbaum View Profile , Carsten Lund View Profile , Peter Shor View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 305–314https://doi.org/10.1145/167088.167190Online:01 June 1993Publication History 21citation326DownloadsMetricsTotal Citations21Total Downloads326Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper generalizes the previous formal definitions of random-self-reducibility. It is shown that, even under a very general definition, sets that are complete for any level of the polynomial hierarchy are not nonadaptively random-self-reducible, unless the hierarchy collapses. In particular, NP-complete sets are not nonadaptively random-self-reducible, unless the hierarchy collapses at the third level. By contrast, we show that sets complete for the classes PP and ${\text{MOD}}_m {\text{P}}$ are random-self-reducible.

Pratt [Internat. J. Parallel Programming, 15 (1986), pp. 33–7.1] introduced POMSETs (partially ordered multisets) to describe and analyze concurrent systems. A POMSET P gives a set of temporal constraints that any correct execution of a given oncurrent system must satisfy. Let $L ( P )$ (the language ofP) denote the set of all system executions that satisfy the constraints given by P. This paper shows the following for finite POMSETs P, Q, and system execution x: • The POMSET language membership problem (given x and P, is $x \in L( P )$?) is NP-complete. • The POMSET language containment problem (given P and Q, is $L ( P ) \subseteq L ( Q )$?) is $\prod _2^p $-complete. • The POMSET language equality problem (given P and Q, is $L( P ) = L ( Q )$?) is at least as hard as the graph-isomorphism problem. • The POMSET language size problem (given P, how many x are in $L( P )$?) is span-P-complete.

A basic question about NP is whether or not search reduces in polynomial time to decision. We indicate that the answer is negative: under a complexity assumption (that deterministic and nondeterministic doubleexponential time are unequal) we construct a language in NP for which search does not reduce to decision. These ideas extend in a natural way to interactive proofs and program checking. Under similar assumptions we present languages in NP for which it is harder to prove membership interactively than it is to decide this membership. Similarly we present languages where checking is harder than computing membership. Each of the following properties --- checkability, random-self-reducibility, reduction from search to decision, and interactive proofs in which the prover's power is limited to deciding membership in the language itself --- implies coherence, one of the weakest forms of self-reducibility. Under assumptions about triple-exponential time, we construct incoherent sets in NP....

Cartesian-factorable extensions and subgraphs of prime graphs are investigated. It is shown that minimal factorable extensions and maximal factorable subgraphs are not unique and that finding them is NP-hard even, in the case of minimal factorable extensions, if the prime graph in question is required to be a tree. Tight bounds on the density of a prime graph’s minimal factorable extension are derived. A dynamic programming algorithm is given for finding factorable extensions of certain types of trees.

We consider the problem of computing with encrypted data. Player A wishes to know the value ƒ(x) for some x but lacks the power to compute it. Player B has the power to compute ƒ and is willing to send ƒ(y) to A if she sends him y, for any y. Informally, an encryption scheme for the problem ƒ is a method by which A, using her inferior resources, can transform the cleartext instance x into an encrypted instance y, obtain ƒ(y) from B, and infer ƒ(x) from ƒ(y) in such a way that B cannot infer x from y. When such an encryption scheme exists, we say that ƒ is encryptable.

The cartesian product of directed, simple graphs D 1 = ( V 1 , A 1 ) and D 2 = ( V 2 , A 2 ) is a digraph D with V ( D ) = V 1 × V 2 and A ( D ) = {( ν 1 , ν 2 ) → ( w 1 , w 2 ): ν 1 = w 1 and ν 2 → w 2 ϵA 2 or ν 2 = w 2 and ν 1 → w 1 ϵA 1 }. In this paper, we prove that directed graphs have unique prime factorizations under cartesian multiplication and that we can find the prime factorizations of weakly connected digraphs in polynomial time. This work extends recent work by Feigenbaum, Hershberger, Schäffer, and Winkler on cartesian factoring of undirected graphs.

We consider composition, a graph multiplication operator defined by Harary and Sabidussi, from a complexity theoretic point of view. If G and H are undirected graphs without self-loops, then the composite graph $G[H]$ has vertex set $V(G) \times V(H)$ and edge set $\{ (g_1 ,h_1 ) \text{---} (g_2 ,h_2 ):g_1 \text{---} g_2 \in E(G){\text{ or }}g_1 = g_2 {\text{ and }}h_1 \text{---} h_2 \in E(H)\} $. We show that the complexity of testing whether an arbitrary graph can be written nontrivially as the composition of two smaller graphs is the same, to within polynomial factors, as the complexity of testing whether two graphs are isomorphic.

System/U is a universal relation database system under development at Standford University which uses the language C on UNIX. The system is intended to test the use of the universal view, in which the entire database is seen as one relation. This paper describes the theory behind System/U, in particular the theory of maximal objects and the connection between a set of attributes. We also describe the implementation of the DDL (Data Description Language) and the DML (Data Manipulation Language), and discuss in detail how the DDL finds maximal objects and how the DML determines the connection between the attributes that appear in a query.