Computational Challenges in (2009)
Joan Feigenbaum, David C. Parkes, David M. Pennock
review articles doi:10.1145/1435417.1435435 Economic and social sciences will drive Internet protocols and services into the future.
Approximate Privacy: Foundations and Quantification (2009)
Feigenbaum, Joan, Jaggard, Aaron D., Schapira, Michael
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...
Delegation Logic: A Logic-based Approach to Distributed Authorization (2009)
Ninghui Li, Joan Feigenbaum, Alan Siegel
To my parents and my wife iii Acknowledgment First and foremost, I must thank Joan Feigenbaum, my advisor, for her guidance, patience, and encouragement over these years. If I became a better writer...
Flexibility as an instrument in digital rights management (2009)
Dirk Bergemann, Thomas Eisenbach, Joan Feigenbaum, Scott Shenker
We consider the optimal design of ‡exible use in a digital-rights-management policy. The basic model considers a single distributor of digital goods and a continuum of consumers. Each consumer can...
Secure Multiparty Computation of Approximations (Extended Abstract) (2009)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J, Rebecca N. Wright
1 Introduction There are an increasing number and variety of real-world applications that collect a massive amount of data and wish to make use of it. For example, massive data sets arise in physical...
Sharing the Cost of Multicast Transmissions 1 (2008)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in...
Towards a Theory of Networked Computation 1 (2008)
Joan Feigenbaum, Michael Mitzenmacher
The increasing prominence of the Internet, the Web, and large data networks in general has profoundly affected social and commercial activity. It has also wrought one of the most profound shifts in...
Graph Distances in the Data-Stream Model (2008)
Feigenbaum, Joan, Kannan, Sampth, Mcgregor, Andrew, Suri, Siddarth, Zhang, Jian
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...
Doc. Math. J. DMV 1 Games, Complexity Classes, and Approximation Algorithms Abstract. (2008)
We survey recent results about game-theoretic characterizations of computational complexity classes. We also show how these results are used to prove that certain natural optimization functions are...
Secure Multiparty Computation of Approximations (Extended Abstract) (2008)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J, Rebecca N. Wright
1 Introduction There are an increasing number and variety of real-world applications that collect a massive amount of data and wish to make use of it. For example, massive data sets arise in physical...
Autonomous Routing Domains Don’t (2008)
Autonomous System (AS): A collection of IP subnets and routers
Sharing the Cost of Multicast Transmissions 1 (2008)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in...
Computing Diameter in the Streaming and (2008)
Sliding-window Models, Joan Feigenbaum, Sampath Kannan, Jian Zhang
Abstract We investigate the diameter problem in the streaming and slidingwindow models. We show that, for a stream of n points or a sliding window of size n, any exact algorithm for diameter requires...
ABSTRACT Distributed Algorithmic Mechanism Design: Recent Results and Future Directions ∗ (2008)
Joan Feigenbaum, Scott Shenker
Distributed Algorithmic Mechanism Design (DAMD) combines theoretical computer science’s traditional focus on computational tractability with its more recent interest in incentive compatibility and...
ABSTRACT Distributed Algorithmic Mechanism Design: Recent Results and Future Directions ∗ (2008)
Joan Feigenbaum, Scott Shenker
Distributed Algorithmic Mechanism Design (DAMD) combines theoretical computer science’s traditional focus on computational tractability with its more recent interest in incentive compatibility and...
ABSTRACT Distributed Algorithmic Mechanism Design: Recent Results and Future Directions ∗ (2008)
Joan Feigenbaum, Scott Shenker
Distributed Algorithmic Mechanism Design (DAMD) combines theoretical computer science’s traditional focus on computational tractability with its more recent interest in incentive compatibility and...
Joan Feigenbaum, Aaron Johnson, Paul Syverson
We perform a probabilistic analysis of onion routing. The analysis is presented in a black-box model of anonymous communication that abstracts the essential properties of onion routing in the...
Abstract REFEREE: Trust Management for Web Applications (2008)
Yang-hua Chu, Joan Feigenbaum, Brian Lamacchia, Paul Resnick, Martin Strauss
Digital signatures provide a mechanism for guaranteeing integrity and authenticity of Web content but not more general notions of security or trust. Web-aware applications must permit users to state...
Joan Feigenbaum, Benny Pinkas, Felipe Saint Jean, Raphael S. Ryger
We describe the design and implementation of a system for conducting surveys while hiding the information provided by the respondents. We use the CRA Taulbee Survey of faculty salaries in computer...
Joan Feigenbaum, Martin J. Strauss, Rebecca N. Wright
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct...
Towards a Theory of Data Entanglement ⋆ (Extended Abstract) (2008)
James Aspnes, Joan Feigenbaum, R Yampolskiy, Sheng Zhong
Abstract. We give a formal model for systems that store data in entangled form. We propose a new notion of entanglement, called all-ornothing integrity (AONI) that binds the users ’ data in a way...
Joan Feigenbaum, Aaron Johnson, Paul Syverson
We perform a probabilistic analysis of onion routing. The analysis is presented in a black-box model of anonymous communication that abstracts the essential properties of onion routing in the...
Felipe Saint-jean, Aaron Johnson, Joan Feigenbaum, Dan Boneh
Web search is currently a source of growing concern about personal privacy. It is an essential and central part of most users ’ activity online and therefore one through which a significant amount...
Mechanism Design for Policy Routing Received: Accepted: (2008)
Joan Feigenbaum, Rahul Sami, Scott Shenker, J. Feigenbaum, R. Sami, S. Shenker
Abstract 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...
ABSTRACT Distributed Algorithmic Mechanism Design: Recent Results and Future Directions ∗ (2008)
Joan Feigenbaum, Scott Shenker
Distributed Algorithmic Mechanism Design (DAMD) combines theoretical computer science’s traditional focus on computational tractability with its more recent interest in incentive compatibility and...
Towards a Theory of Data Entanglement ⋆,⋆⋆ Abstract (2008)
James Aspnes, Joan Feigenbaum, R Yampolskiy, Sheng Zhong
We give a formal model for systems that store data in entangled form. We propose a new notion of entanglement, called all-or-nothing integrity (AONI) that binds the users ’ data in a way that makes...
AFormal Treatment of Remotely Keyed Encryption? (2008)
Matt Blaze, Joan Feigenbaum, Moni Naor
Abstract. Remotely keyed encryption schemes (RKESs), introduced by Blaze [6], support high-bandwidth cryptographic applications (such as encrypted video conferences) in which long-lived secrets (such...
Overview of the AT&T Labs Trust-Management Project (2008)
This paper presents some of the findings and open questions that our group has produced thus far. Reasoned controversy may be stimulated by some of the following design choices:
b) Flow-contention graph A (2007)
Let G be an undirected graph on n nodes, and let k be an integer that divides n. Ak-equipartition π of G is a partition of V (G) into k equal-sized pieces V1,..., Vk. A pair Vi, Vj of distinct sets...
A Formal Treatment of Remotely Keyed Encryption (2007)
Exte Nd Ed, Matt Blaze, Joan Feigenbaum, Moni Naor
) ? Matt Blaze, 1 Joan Feigenbaum, 1 Moni Naor 2 1 AT&T Labs -- Research 180 Park Avenue Florham Park, NJ 07932 USA fmab,jfg@research.att.com 2 Dept. Applied Math. and Computer Science Weizmann...
Difference Algorithm For, Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
Overview of the ATT Labs Trust-Management Project (2007)
This paper presents some of the findings and open questions that our group has produced thus far. Reasoned controversy may be stimulated by some of the following design choices:
A Formal Framework for Evaluating Heuristic Programs (2007)
Lenore Cowen, Joan Feigenbaum, Sampath Kannan
This paper provides a family of definitions that formalize the notion of a timer and some preliminary results that demonstrate the utility of these definitions.
A Formal Treatment of Remotely Keyed Encryption (2007)
Extend Ed, Matt Blaze, Joan Feigenbaum, Moni Naor
) ? Matt Blaze, 1 Joan Feigenbaum, 1 Moni Naor 2 1 AT&T Labs -- Research 180 Park Avenue Florham Park, NJ 07932 USA fmab,jfg@research.att.com 2 Dept. Applied Math. and Computer Science Weizmann...
Master-Key Cryptosystems (2007)
By Matt, Matt Blaze, Joan Feigenbaum, F. T. Leighton
We initiate the study of a new class of secret-key cryptosystems, called master-key cryptosystems, in which an authorized third party possesses a "master key" that allows efficient recovery...
Difference Algorithm For, Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
Logic-Based Knowledge, Ninghui Li, Benjamin N. Grosof, Joan Feigenbaum
: 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...
A Formal Framework for Evaluating Heuristic Programs (2007)
By Lenore, Lenore Cowen, Joan Feigenbaum, Sampath Kannan
We address the question of how one evaluates the usefulness of a heuristic program on a particular input. If theoretical tools do not allow us to decide for every instance whether a particular...
Two Remarks on Self-Correctability versus Random-Self-Reducibility (2007)
Joan Feigenbaum, Lance Fortnow, Ashish Naik
We examine the relationship between two types of probabilistic self-reductions that play crucial roles in the theory of interactive proof systems, program-checking, and program-testing:...
Aaron Archer, Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We investigate multicast cost sharing from both computational and economic perspectives. Recent work in economics leads to the consideration of two mechanisms: marginal cost (MC), which is ecient and...
Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, Scott Shenker
Summary. The routing of traffic between Internet domains, or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper,...
Incentives and Internet computation (2007)
Sergio Rajsbaum, Joan Feigenbaum, Scott Shenker
The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases,...
Aaron Archer, Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
Multicast routing is a technique for transmitting a packet from a single source to multiple receivers without wasting network bandwidth. To achieve transmission e#ciency, multicast routing constructs...
Joan Feigenbaum, Sampath Kannan, Jian Zhang
Abstract. We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of n points or a sliding window of size n, any exact algorithm for diameter...
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Rebecca N. Wright
Abstract. Approximation algorithms can sometimes provide e#cient solutions when no e#cient exact computation is known. In particular, approximations are often useful in a distributed setting where...
LIMITED DISTRIBUTION NOTICE (2007)
Ninghui Li, Benjamin N. Grosof, Joan Feigenbaum
This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its...
Secure Multiparty Computation of Approximations (Extended Abstract) (2007)
Joan Feigenbaum, Tal Malkin, Kobbi Nissim, Martin J, Rebecca N. Wright
Abstract. Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting...
Joan Feigenbaum, Michael J. Freedman, Tomas Sander, Adam Shostack
Internet-based commerce provides great opportunities for merchants, consumers, and business a#liates, but it may seriously threaten users ' privacy. Some of the paths to loss of privacy are...
Ninghui Li, Benjamin N. Grosof, Joan Feigenbaum
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...
Joan Feigenbaum, John Ioannidis, Angelos D. Keromytis
Abstract. Existing authorization mechanisms fail to provide powerful and robust tools for handling security at the scale necessary for today's Internet. These mechanisms are coming under...
Abstract: It is our thesis that a significant amount of the existing securityresearch literature makes unrealistic assumptions about computing environments and about users ’ goals. We propose some...
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We investigate multicast cost sharing from both computational and economic points of view. Recent work in economics (Moulin and Shenker, 2001) leads naturally to the consideration of two mechanisms:...
Joan Feigenbaum, Sampath Kannan, Moshe Y. Vardi, Mahesh Viswanathan
To analyze the complexity of decision problems on graphs, one normally assumes that the input size is polynomial in the number of vertices. Galperin and Wigderson [GW83] and, later, Papadimitriou and...
gives additional details, including sample output of the implementation. (2007)
Ninghui Li, Benjamin Grosof, Joan Feigenbaum
We address the goal of making Delegation Logic (DL) into a practically implementable and tractable trustmanagement system. DL [22] is a logic-based knowledge representation (i.e., language) for...
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J, Rebecca N. Wright
Abstract. Approximation algorithms can sometimes provide e#cient solutions when no e#cient exact computation is known. In particular, approximations are often useful in a distributed setting where...
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J, Rebecca N. Wright
Abstract. Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting...
Instance-Hiding Proof Systems (2007)
Donald Beaver, Joan Feigenbaum, Rafail Ostrovsky, Victor Shoup
We define the notion of an instance-hiding proof system (ihps) for a function f; informally, an ihps is a protocol in which a polynomial-time verifier interacts with one or more all-powerful provers...
Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, Scott Shenker
The routing of trac between Internet domains or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper, we address the...
Joan Feigenbaum, Joan Feigenbaum, Siddharth Suri, Siddharth Suri, Sampath Kannan, Sampath Kannan, ...
We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order....
Joan Feigenbaum, David M. Pennock, Lance Fortnow, Rahul Sami
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...
Information Accountability (2007)
Weitzner, Daniel J., Abelson, Harold, Berners-Lee, Tim, Feigenbaum, Joan, Hendler, James, Sussman, Gerald Jay
Ease of information flow is both the boon and the bane of large-scale, decentralized systems like the World Wide Web. For all the benefits and opportunities brought by the information revolution,...
Information Accountability (2007)
Weitzner, Daniel J., Abelson, Harold, Berners-Lee, Tim, Feigenbaum, Joan, Hendler, James, Sussman, Gerald Jay
Ease of information flow is both the boon and the bane of large-scale, decentralized systems like the World Wide Web. For all the benefits and opportunities brought by the information revolution,...
Information Accountability (2007)
Weitzner, Daniel J., Abelson, Harold, Berners-Lee, Tim, Feigenbaum, Joan, Hendler, James, Sussman, Gerald Jay
Ease of information flow is both the boon and the bane of large-scale, decentralized systems like the World Wide Web. For all the benefits and opportunities brought by the information revolution,...
Learning-Based Anomaly Detection in BGP Updates (2007)
Zhang, Jian, Rexford, Jennifer, Feigenbaum, Joan
We propose an instance-learning based framework for detecting BGP routing anomalies. By using a vector of quantified features to represent BGP updates, our framework can capture more complex features...
Incentive-Compatible Interdomain Routing (2007)
Feigenbaum, Joan, Ramachandran, Vijay, Schapira, Michael
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). Using BGP, autonomous...
A model of onion routing with provable anonymity (2007)
Joan Feigenbaum, Aaron Johnson, Paul Syverson
Abstract. Onion routing is a scheme for anonymous communication that is designed for practical use. Until now, however, it has had no formal model and therefore no rigorous analysis of its anonymity...
Incentive-compatible interdomain routing (2006)
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,...
Joan Feigenbaum, Michael Mitzenmacher
The increasing prominence of the Internet, the Web, and large data-networks in general has profoundly affected social and commercial activity. It has also wrought one of the most profound shifts in...
Joan Feigenbaum, Vijay Ramachandran, Michael Schapira, Joan Feigenbaum, Michael Schapira, Vijay Ramachandran
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,...
On Graph Problems in a Semi-Streaming Model (2005)
Feigenbaum, Joan, Kannan, Sampath, McGregor, Andrew, Suri, Siddharth, Zhang, Jian
We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose...
Graph distances in the streaming model: the value of space (2005)
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Siddharth Suri, Jian Zhang
We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order....
Subjective-cost policy routing (2005)
Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, Rahul Sami
Abstract. We study a model of interdomain routing in which autonomous systems’ (ASes’) routing policies are based on subjective cost assessments of alternative routes. The routes are constrained...
Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, Scott Shenker
Summary. The routing of traffic between Internet domains, or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper,...
On graph problems in a semi-streaming model (2004)
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Jian Zhang
Abstract. We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive...
On graph problems in a semi-streaming model (2004)
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Jian Zhang
Abstract. We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of ecient algorithms for solving problems on massive...
Towards an Economic Analysis of Trusted Systems (2004)
Dirk Bergemann, Scott Shenker, Joan Feigenbaum, Jonathan Smith
this paper was completed while he was at the Univ. of Pennsylvania
Towards a Theory of Data Entanglement (2004)
Joan Feigenbaum, Aleksandr Yampolskiy, Sheng Zhong, James Aspnes, James Aspnes, Joan Feigenbaum Aleks, ...
We propose a formal model for data entanglement as used in storage systems like Dagster [25] and Tangler [26]. These systems split data into blocks in such a way that a single block becomes a part of...
Towards a Theory of Data Entanglement (2004)
Exte Nd Ed, James Aspnes, Joan Feigenbaum, R Yampolskiy, Sheng Zhong
We give a formal model for systems that store data in entangled form. We propose a new notion of entanglement, called all-or-nothing integrity (AONI) that binds the users' data in a way that...
James Aspnes, Joan Feigenbaum, Aleksandr Yampolskiy, Sheng Zhong
aleksandr.yampolskiy@yale.edu. Supported by NSF.
Computation in a Distributed Information Market (2004)
Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami
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...
Towards a Theory of Data Entanglement (2004)
James Aspnes, Joan Feigenbaum, Aleksandr Yampolskiy, Sheng Zhong
We propose a formal model for data entanglement as used in storage systems like Dagster [25] and Tangler [26]. These systems split data into blocks in such a way that a single block becomes a part of...
Delegation Logic: A logic-based approach to distributed authorization (2003)
Ninghui Li, Benjamin N. Grosof, Joan Feigenbaum
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...
Computation in a distributed information market (2003)
Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami
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...
Computation in a distributed information market (2003)
Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami
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...
Delegation Logic: A logic-based approach to distributed authorization (2003)
Ninghui Li, Joan Feigenbaum, Alan Siegel, C Ninghui Li, Fangzhe Chang, Hseu-ming Chen, ...
To my parents and my wife iii Acknowledgment First and foremost, I must thank Joan Feigenbaum, my advisor, for her guidance, pa-tience, and encouragement over these years. If I became a better writer...
Abstract Distributed Algorithmic Mechanism Design (2003)
Dissertation Director, Joan Feigenbaum, Rahul Sami, Rahul Sami
Distributed algorithmic mechanism design (DAMD) is an approach to designing dis-tributed systems that takes into account both the distributed-computational environment and the incentives of...
Mechanism Design for Policy Routing (2003)
Joan Feigenbaum, Rahul Sami, Scott Shenker
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...
Delegation Logic: A logic-based approach to distributed authorization (2003)
Ninghui Li, Ninghui Li, Benjamin N. Grosof, Benjamin N. Grosof, Joan Feigenbaum, Joan Feigenbaum
For more information, please visit our website at
Delegation Logic: A logic-based approach to distributed authorization (2003)
Ninghui Li, Benjamin N. Grosof, Joan Feigenbaum
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...
Hardness results for multicast cost sharing (2002)
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We continue the study of multicast cost sharing from the viewpoints of both computational complexity and economic mechanism design. We provide fundamental lower bounds on the network complexity of...
Computing Diameter in the Streaming and Sliding-Window Models (2002)
Joan Feigenbaum, Sampath Kannan, Jian Zhang
We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of n points or a sliding window of size n, any exact algorithm for diameter requires Ω(n)...
Computing Diameter in the Streaming and Sliding-Window Models (2002)
Joan Feigenbaum, Sampath Kannan, Jian Zhang
We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of n points or a sliding window of size n, any exact algorithm for diameter requires Ω(n)...
Hardness results for multicast cost sharing (2002)
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We continue the study of multicast cost sharing from the viewpoints of both computational complexity and economic mechanism design. We provide fundamental lower bounds on the network complexity of...
An Approximate L¹-Difference Algorithm for Massive Data Streams (2002)
Joan Feigenbaum, Sampath Kannan, Martin J. Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, includingobservational sciences, product marketing, and the monitoring and operations of large systems. In network...
Economic Barriers to the Deployement of Existing Privacy (2002)
Joan Feigenbaum, Michael J. Freedman, Tomas S, Adam Shostack
Despite the fact that many of the impressive techniques in the cryptographic researchliterature have been extensively and rigorously analyzed, and some have even been commercially developed, few are...
Agents’ privacy in distributed algorithmic mechanisms. Position Paper (2002)
Joan Feigenbaum, Noam Nisan, Vijay Ramachandran, Rahul Sami, Scott Shenker
In traditional theoretical computer science (TCS), computational agents are typically assumed either to be obedient (i.e., to follow the prescribed algorithm) or to be adversaries who “play against...
Economic Barriers to the Deployement of Existing Privacy (2002)
Joan Feigenbaum, Michael J. Freedman, Tomas S, Adam Shostack
Internet-based commerce provides great opportunities for merchants, consumers, and business aliates, but it may seriously threaten users ' privacy. Some of the paths to loss of privacy are quite...
Distributed Algorithmic Mechanism Design: Recent Results and Future Directions (2002)
Joan Feigenbaum, Scott Shenker
Distributed Algorithmic Mechanism Design (DAMD) combines theoretical computer science's traditional focus on computational tractability with its more recent interest in incentive compatibility...
Hardness results for multicast cost sharing (2002)
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We continue the study of multicast cost sharing from the viewpoints of both computational complexity and economic mechanism design. We provide fundamental lower bounds on the network complexity of...
A BGP-based Mechanism for Lowest-Cost Routing (2002)
Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, Scott Shenker
The routing of tra#c between Internet domains or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper, we address...
Hardness Results for Multicast Cost Sharing (Extended Abstract (2002)
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
Abstract. We continue the study of multicast cost sharing from the viewpoints of both computational complexity and economic mechanism design. We provide fundamental lower bounds on the network...
Hardness Results for Multicast Cost Sharing (Extended Abstract) (2002)
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
Joan Feigenbaum Arvind Krishnamurthy Rahul Sami + Yale University, Computer Science Dept., New Haven, CT 06520-8285.
A BGP-based Mechanism for Lowest-Cost Routing (2002)
Joan Feigenbaum, Rahul Sami, Christos Papadimitriou, Scott Shenker
The routing of traffic between Internet domains or Autonomous Systems (ASs), a task known as interdomain routing, is currently handled by the Border Gateway Protocol (BGP). In this paper, we address...
Economic Barriers to the Deployement of Existing Privacy (2002)
Joan Feigenbaum, Michael J. Freedman, Tomas S, Adam Shostack
Despite the fact that many of the impressive techniques in the cryptographic research literature have been extensively and rigorously analyzed, and some have even been commercially developed, few are...
Privacy-enabled Management, Customer Data, Günter Karjoth, Matthias Schunter, Michael Waidner, Dan Boneh, ...
is published quarterly and is distributed to all TC members. Its scope includes the design, implementation, modelling, theory and application of database systems and their technology. Letters,...
Approximation and collusion in multicast cost sharing (2001)
Aaron Archer, Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We investigate multicast cost sharing from both computational and economic perspectives. Recent work in economics leads to the consideration of two mechanisms: marginal cost (MC), which is efficient...
Sharing the Cost of Multicast Transmissions (2001)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in...
Privacy Engineering for Digital Rights Management Systems (2001)
Joan Feigenbaum, Michael J. Freedman, Tomas S, Adam Shostack
Internet-based distribution of mass-market content provides great opportunities for producers, distributors, and consumers, but it may seriously threaten users’ privacy. Some of the paths to loss...
Secure multiparty computation of approximations (2001)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim
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...
Nonmonotonicity, user interfaces, and risk assessment in certificate revocation (2001)
Abstract. We consider certificate revocation from three high-level perspectives: temporal nonmonotonicity, user interfaces, and risk management. We argue that flawed understanding of these three...
Privacy Engineering for Digital Rights Management Systems (2001)
Joan Feigenbaum, Michael J. Freedman, Tomas S, Adam Shostack
Strategyproof sharing of submodular costs: Budget balance versus efficiency (2001)
Scott Shenker, Jel D, Bhaskar Dutta, Joan Feigenbaum, Wolfgang Pesendorfer
A service is produced for a set of agents. The service is binary, each agent either receives service or not, and the total cost of service is a submodular function of the set receiving service. We...
Nonmonotonicity, user interfaces, and risk assessment in certificate revocation (2001)
Abstract. We consider certificate revocation from three high-level perspectives: temporal nonmonotonicity, user interfaces, and risk management. We argue that flawed understanding of these three...
Strategyproof sharing of submodular costs: Budget balance versus efficiency (2001)
Scott Shenker, Bhaskar Dutta, Joan Feigenbaum, Wolfgang Pesendorfer
A service is produced for a set of agents. The service is binary, each agent either receives service or not, and the total cost of service is a submodular function of the set receiving service. We...
Secure multiparty computation of approximations (2001)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, Rebecca N. Wright
Abstract. Approximation algorithms can sometimes be used to obtain efficient solutions where no efficient exact computation is known. In particular, approximations are often useful in a distributed...
Approximation and collusion in multicast cost sharing (2001)
Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, Scott Shenker
We investigate multicast cost sharing from both computational and economic points of view. Recent work in economics [MS97] leads naturally to the consideration of two mechanisms: marginal cost (MC),...
Sharing the Cost of Multicast Transmissions (2001)
Joan Feigenbaum, Christos Papadimitriou, Scott Shenker
We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in...
Sharing the Cost of Multicast Transmissions (2001)
Joan Feigenbaum, Christos H. Papadimitriou
Abstract We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most...
Secure multiparty computation of approximations (2001)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim
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...
A nonmonotonic delegation logic with prioritized conflict handling. Unpublished manuscript (2000)
Ninghui Li, Benjamin N. Grosof, Joan Feigenbaum
We extend previous work on Delegation Logic (DL) [11, 12], a tractable and practically implementable logic-based language for authorization in large-scale, open, distributed systems. We expressively...
Testing and spot-checking of data streams (2000)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
We consider the tasks of testing and spot-checking for data streams. These testers and spotcheckers are potentially useful in real-time or near real-time applications that process huge datasets....
Sharing the Cost of Multicast Transmissions (2000)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
this paper, we focus on the communication burden of algorithms for implementing the MC and SH cost-sharing mechanisms. We prove a lower bound suggesting that any cost-sharing algorithm implementing...
Testing and Spot-Checking of Data Streams (2000)
Joan Feigenbaum Att, Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
We consider the tasks of testing and spot-checking for data streams. These testers and spotcheckers are potentially useful in real-time or near real-time applications that process huge datasets....
Testing and Spot-Checking of Data Streams (2000)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
We consider the tasks of testing and spot-checking for data streams. These testers and spotcheckers are potentially useful in real-time or near real-time applications that process huge datasets....
Dynamic Graph Algorithms (2000)
Joan Feigenbaum, Sampath Kannan
INTRODUCTION Dynamic graph algorithms are algorithms that maintain properties of a (possibly edgeweighted) graph while the graph is changing. These algorithms are potentially useful in a number of...
Sharing the Cost of Multicast Transmissions (2000)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
this paper, we focus on the communication burden of algorithms for implementing the MC and SH cost-sharing mechanisms. We prove a lower bound suggesting that any cost-sharing algorithm implementing...
: www.idealibrary.com on Sharing the Cost of Multicast Transmissions 1 (1999)
Joan Feigenbaum, Christos H. Papadimitriou, Scott Shenker
We investigate cost-sharing algorithms for multicast transmission. Economic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in...
KeyNote: Trust Management for Public-Key (1999)
Matt Blaze, Joan Feigenbaum, Angelos D. Keromytis
Abstract. This paper discusses the rationale for designing a simple trust-management system for public-key infrastructures, called KeyNote. The motivating principles are expressiveness, simplicity,...
An approximate L 1 -dierence algorithm for massive data streams (1999)
Joan Feigenbaum, Sampath Kannan, Martin J. Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
A Logic-Based Knowledge Representation for Authorization with Delegation (1999)
Ninghui Li, Joan Feigenbaum, Benjamin N. Grosof
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...
An Approximate L¹-Difference Algorithm for Massive Data Streams (1999)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
Complexity of Problems on Graphs Represented as OBDDs (1999)
To analyze the complexity of decision problems on graphs, one normally assumes that the input size is polynomial in the number of vertices. Galperin and Wigderson [GW83] and, later, Papadimitriou and...
An Approximate L 1 -Difference Algorithm for Massive Data Streams (1999)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
Testing and Spot-Checking of Data Streams (1999)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
We consider the tasks of testing and spot-checking for data streams. These testers and spotcheckers are potentially useful in real-time or near real-time applications that process huge datasets....
Streaming Algorithms for Distributed, Massive Data Sets (1999)
Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
A Logic-based Knowledge Representation for Authorization with Delegation (1999)
Ninghui Li, Joan Feigenbaum, Benjamin N. Grosof
) Ninghui Li Computer Science New York University 251 Mercer Street New York, NY 10012, USA ninghui@cs.nyu.edu Joan Feigenbaum AT&T Labs -- Research Room C203 180 Park Avenue Florham Park, NJ...
The role of trust management in distributed systems security (1999)
Matt Blaze, Joan Feigenbaum, John Ioannidis, Angelos D. Keromytis
Abstract. Existing authorization mechanisms fail to provide powerful and robust tools for handling security at the scale necessary for today’s Internet. These mechanisms are coming under increasing...
A Formal Treatment of Remotely Keyed Encryption (1998)
Abstract. Remotely keyed encryption schemes (RKESs), introduced by Blaze [6], support high-bandwidth cryptographic applications (such as encrypted video conferences) in which long-lived secrets (such...
Towards an Infrastructure for Authorization, Position Paper presented at the 3rd (1998)
In recent years, there has been a great deal of debate about whether a large-scale "publickey infrastructure " is needed for electronic commerce and, if so, whether the technical...
Towards an Infrastructure for Authorization, Position Paper presented at the 3rd (1998)
In recent years, there has been a great deal of debate about whether a large-scale "publickey infrastructure " is needed for electronic commerce and, if so, whether the technical...
Compliance Checking in the PolicyMaker Trust Management System (1998)
Matt Blaze Joan, Joan Feigenbaum, Martin Strauss
Emerging electronic commerce services that use public-key cryptography on a mass-market scale require sophisticated mechanisms for managing trust. For example, any service that receives a signed...
Games, Complexity Classes, and Approximation Algorithms (1998)
. We survey recent results about game-theoretic characterizations of computational complexity classes. We also show how these results are used to prove that certain natural optimization functions are...
A Formal Treatment of Remotely Keyed Encryption (1998)
Matt Blaze Joan, Joan Feigenbaum, Moni Naor
. Remotely keyed encryption schemes (RKESs), introduced by Blaze [6], support high-bandwidth cryptographic applications (such as encrypted video conferences) in which long-lived secrets (such as...
KeyNote: Trust Management for Public-Key Infrastructures (1998)
Matt Blaze, Joan Feigenbaum, Angelos Keromytis
. This paper discusses the rationale for designing a simple trust-management system for public-key infrastructures, called KeyNote. The motivating principles are expressiveness, simplicity, and...
Compliance Checking in the PolicyMaker Trust Management System (1998)
Matt Blaze, Joan Feigenbaum, Martin Strauss
. Emerging electronic commerce services that use public-key cryptography on a mass-market scale require sophisticated mechanisms for managing trust. For example, any service that receives a signed...
Compliance Checking in the PolicyMaker Trust Management System (1998)
Matt Blaze, Joan Feigenbaum, Martin Strauss
. Emerging electronic commerce services that use public-key cryptography on a mass-market scale require sophisticated mechanisms for managing trust. For example, any service that receives a signed...
KeyNote: Trust Management for Public-Key Infrastructures (1998)
Matt Blaze, Joan Feigenbaum, Angelos D. Keromytis
. This paper discusses the rationale for designing a simple trust-management system for public-key infrastructures, called KeyNote. The motivating principles are expressiveness, simplicity, and...
Compliance Checking in the PolicyMaker Trust Management System (1998)
Matt Blaze, Joan Feigenbaum, Martin Strauss
Emerging electronic commerce services that use public-key cryptography on a mass-market scale require sophisticated mechanisms for managing trust. For example, any service that receives a signed...
On Coherence, Random-Self-Reducibility, and Self-Correction (1998)
Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish Naik
. We study three types of self-reducibility that are motivated by the theory of program verification. A set A is random-self-reducible if one can determine whether an input x is in A by making random...
Compliance Checking in the PolicyMaker Trust Management System (1998)
Matt Blaze, Joan Feigenbaum, Martin Strauss
Abstract. Emerging electronic commerce services that use public-key cryptography on a mass-market scale require sophisticated mechanisms for managing trust. For example, any service that receives a...
The popularity of the Java programming language and the concomittant media attention given to the \security holes " that have been found in the Java runtime system have brought the problem...
An Information-Theoretic Treatment of Random-Self-Reducibility (1997)
Joan Feigenbaum, Martin Strauss
We initiate the study of random-self-reducibility from an information-theoretic point of view. Specifically, we formally define the notion of a random-self-reduction that, with respect to a given...
Trust Management and Proof-Carrying Code in Secure Mobile-Code Applications (1997)
Position Paper, Joan Feigenbaum, Peter Lee
Introduction The popularity of the Java programming language and the concomittant media attention given to the "security holes" that have been found in the Java runtime system have brought...
Random Debaters and the Hardness of Approximating Stochastic Functions (1997)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
. 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...
On Coherence, Random-Self-Reducibility, and Self-Correction (1997)
Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish Naik
. We study three types of self-reducibility that are motivated by the theory of program verification. A set A is random-self-reducible if one can determine whether an input x is in A by making random...
Trust Management and Proof-Carrying Code in Secure Mobile-Code Applications (1997)
Introduction The popularity of the Java programming language and the concomittant media attention given to the "security holes" that have been found in the Java runtime system have brought...
An Information-Theoretic Treatment of Random-Self-Reducibility (Extended Abstract) (1997)
Joan Feigenbaum, Martin Strauss
We initiate the study of random-self-reducibility from an information-theoretic point of view. Specifically, we formally define the notion of a random-self-reduction that, with respect to a given...
An Information-Theoretic Treatment of Random-Self-Reducibility (1997)
Joan Feigenbaum, Martin Strauss
We initiate the study of random-self-reducibility from an information-theoretic point of view. Specifically, we formally define the notion of a random-self-reduction that, with respect to a given...
Kolmogorov Techniques in Computational Complexity Theory (1997)
Sophie Laplante, Joan Feigenbaum, Lance Fortnow
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii CHAPTER 1. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 iHow Hard is this Problem?j . . . ....
Managing Trust in Medical Information Systems (1996)
Matt Blaze, Joan Feigenbaum, Jack Lacy
The development of large-scale health information networks necessitates the use of cryptography to guarantee privacy, authenticity, and integrity of personal medical records. This use of cryptography...
An Information-Theoretic Treatment of Random-Self-Reducibility (1996)
Joan Feigenbaum, Martin Strauss
We initiate the study of random-self-reducibility from an information-theoretic point of view. Specifically, we formally define the notion of a random-self-reduction that, with respect to a given...
Decentralized Trust Management (1996)
Matt Blaze, Joan Feigenbaum, Jack Lacy
We identify the trust management problem as a distinct and important component of security in network services. Aspects of the trust management problem include formulating security policies and...
Master-Key Cryptosystems (1996)
By Matt, Matt Blaze, Joan Feigenbaum, F. T. Leighton
We initiate the study of a new class of secret-key cryptosystems, called master-key cryptosystems, in which an authorized third party possesses a "master key" that allows efficient recovery...
DIMACS Technical Report 96-15 June, 1996 (1996)
Workshop Summary, Robert Brayton, Allen Emerson, Joan Feigenbaum
The correctness of computer hardware and software is an area of growing theoretical interest and practical importance. It is now widely acknowledged that effective reasoning about program correctness...
On Coherence, Random-Self-Reducibility, and Self-Correction (1996)
Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik
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...
Decentralized Trust Management (1996)
Matt Blaze, Joan Feigenbaum, Jack Lacy
We identify the trust management problem as a distinct and important component of security in network services. Aspects of the trust management problem include formulating security policies and...
The use of coding theory in computational complexity (1995)
The interplay of coding theory and computational complexity theory is a rich source of results and problems. This article surveys three of the major themes in this area: ffl the use of codes to...
The Use of Coding Theory in Computational Complexity (1995)
Joan Feigenbaum Att, Joan Feigenbaum
The interplay of coding theory and computational complexity theory is a rich source of results and problems. This article surveys three of the major themes in this area: ffl the use of codes to...
Random Debaters and the Hardness of Approximating Stochastic Functions (1995)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
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...
A Formal Framework for Evaluating Heuristic Programs (1995)
By Lenore, Lenore Cowen, Joan Feigenbaum, Sampath Kannan
We address the question of how one evaluates the usefulness of a heuristic program on a particular input. If theoretical tools do not allow us to decide for every instance whether a particular...
On Coherence, Random-Self-Reducibility, and Self-Correction (1995)
Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik
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...
A Game-Theoretic Classification of Interactive Complexity Classes (1995)
Extend Ed, Joan Feigenbaum, Daphne Koller, Peter Shor
) Joan Feigenbaum AT&T Bell Labs, 2C-473 600 Mountain Avenue Murray Hill, NJ 07974-0636 jf@research.att.com Daphne Koller UC Berkeley Computer Science Division Berkeley, CA 94720...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1995)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
We initiate an investigation of probabilistically checkable debate systems (PCDS's), a natural generalization of probabilistically checkable proof systems. A PCDS for a language L consists of a...
A Game-Theoretic Classification of Interactive Complexity Classes (1995)
Extend Ed, Joan Feigenbaum, Daphne Koller, Peter Shor
) Joan Feigenbaum AT&T Bell Labs, 2C-473 600 Mountain Avenue Murray Hill, NJ 07974-0636 jf@research.att.com Daphne Koller UC Berkeley Computer Science Division Berkeley, CA 94720...
A Game-Theoretic Classification of Interactive Complexity Classes (1995)
Joan Feigenbaum, Daphne Koller, Peter Shor
Game-theoretic characterizations of complexity classes have often proved useful in understanding the power and limitations of these classes. One well-known example tells us that PSPACE can be...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1995)
Pankaj Agarwal, Joan Feigenbaum, Carsten Lund, Andrew Goldberg, Ketan Mulmuley, ...
We initiate an investigation of probabilistically checkable debate systems (PCDS), a natural generalization of probabilistically checkable proof systems (PCPS). A PCDS for a language L consists of a...
The Use of Coding Theory in Computational Complexity (1995)
The interplay of coding theory and computational complexity theory is a rich source of results and problems. This article surveys three of the major themes in this area: ffl the use of codes to...
The power of adaptiveness and additional queries in random-self-reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
1 We look at relationships between adaptive and nonadaptive random-self-reductions. We also look at what happens to random-self-reductions if we restrict the number of queries they are allowed to...
Random Debaters and the Hardness of Approximating Stochastic Functions (1994)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
. 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...
The Power Of Adaptiveness And Additional Queries In Random-Self-Reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
. We study random-self-reductions from a structural complexity -theoretic point of view. Specifically, we look at relationships between adaptive and nonadaptive random-self-reductions. We also look...
The Power Of Adaptiveness And Additional Queries In Random-Self-Reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
. We study random-self-reductions from a structural complexity -theoretic point of view. Specifically, we look at relationships between adaptive and nonadaptive random-self-reductions. We also look...
The Power of Adaptiveness and Additional Queries in Random-Self-Reductions (1994)
Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel Spielman
. We study random-self-reductions from a structural complexity -theoretic point of view. Specifically, we look at relationships between adaptive and nonadaptive random-self-reductions. We also look...
Two Remarks on Self-Correctability versus Random-Self-Reducibility (1994)
Joan Feigenbaum, Lance Fortnow, Ashish V. Naik
We examine the relationship between two types of probabilistic self-reductions that play crucial roles in the theory of interactive proof systems, program-checking, and programtesting:...
Lance Fortnow, Joan Feigenbaum
. In this paper, we generalize the previous formal definitions of random-self-reducibility. We show that, even under our very general definition, sets that are complete for any level of the...
Locally Random Reductions in Interactive Complexity Theory (1993)
We survey definitions, known results, and open questions in the area of locally random reductions and explore the ramifications of these reductions in complexity theory. This paper is based on a...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1993)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
We initiate an investigation of probabilistically checkable debate systems (PCDS's), a natural generalization of probabilistically checkable proof systems. A PCDS for a language L consists of a...
Instance-Hiding Proof Systems (1993)
Donald Beaver, Joan Feigenbaum, Rafail Ostrovsky, Victor Shoup
We define the notion of an instance-hiding proof system (ihps) for a function f ; informally, an ihps is a protocol in which a polynomial-time verifier interacts with one or more all-powerful provers...
Universal Traversal Sequences (1993)
Joan Feigenbaum, Nick Reingold
this article we discuss a purely combinatorial problem, the construction of short universal traversal sequences, and its relationship to questions about logspace computation. We state the problem...
On The Random-Self-Reducibility Of Complete Sets (1993)
. In this paper, we generalize the previous formal definitions of random-self-reducibility. We show that, even under our very general definition, sets that are complete for any level of the...
Random Debaters and the Hardness of Approximating Stochastic Functions (1993)
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter Shor
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...
On being incoherent without being very hard (1992)
Richard Beigel, Joan Feigenbaum
Abstract. Trakhtenbrot calls a set A autoreducible if A is Turingreducible to A via an oracle Turing machine that never queries the oracle about the input string. Yao considers sets that are...
On Being Incoherent Without Being Very Hard (1992)
Richard Beigel, Joan Feigenbaum
. Trakhtenbrot calls a set A autoreducible if A is Turingreducible to A via an oracle Turing machine that never queries the oracle about the input string. Yao considers sets that are autoreducible...
Cryptographic protection of databases and software (1991)
Joan Feigenbaum, Mark Y. Liberman, Rebecca N. Wright
We describe experimental work on cryptographic protection of databases and software. The database in our experiment is a natural language dictionary of over 4000 Spanish verbs. Our tentative...
On The Random-Self-Reducibility Of Complete Sets (1991)
Joan Feigenbaum, Lance Fortnow
. In this paper, we generalize the previous formal definitions of random-self-reducibility. We show that, even under our very general definition, sets that are complete for any level of the...
Open Questions, Talk Abstracts, and Summary of Discussions (1991)
Joan Feigenbaum, Michael Merritt
s, and Summary of Discussions Joan Feigenbaum and Michael Merritt AT&T Bell Laboratories Murray Hill, NJ 07974 The DIMACS Workshop on Distributed Computing and Cryptography was held at the Nassau...
Languages that are Easier than their Proofs (1991)
Richard Beigel, Mihir Bellare, Joan Feigenbaum, Shafi Goldwasser
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...
Secure circuit evaluation - A protocol based on hiding information from an oracle (1990)
: We present a simple protocol for two-player secure circuit evaluation. The protocol enables players C and D to cooperate in the computation of f(x) while D conceals her data x from C and C conceals...
Hiding Instances in Zero-Knowledge Proof Systems (1990)
Extend Ed, Donald Beaver, Joan Feigenbaum, Victor Shoup
CRYPTO-1990 Proceedings) Donald Beaver Joan Feigenbaum y Victor Shoup z Abstract Informally speaking, an instance-hiding proof system for the function f is a protocol in which a polynomial-time...
A Protocol Based on Hiding Information From an Oracle (1990)
Mart'in Abadi, Joan Feigenbaum
: We present a simple protocol for two-player secure circuit evaluation. The protocol enables players C and D to cooperate in the computation of f(x) while D conceals her data x from C and C conceals...
Lower Bounds on Random-Self-Reducibility (Extended Abstract) (1990)
Joan Feigenbaum, Sampath Kannan, Noam Nisan
Structures-1990 Proceedings) Joan Feigenbaum Sampath Kannan y Noam Nisan z Abstract: Informally speaking, a function f is random-self-reducible if, for any x, the computation of f(x) can be reduced...
Locally Random Reductions in Interactive Complexity Theory (1990)
We survey definitions, known results, and open questions in the area of locally random reductions and explore the ramifications of these reductions in complexity theory. 1 Introduction We consider...
Jian Zhang, Jian Zhang, Jennifer Rexford, Jennifer Rexford, Joan Feigenbaum, Joan Feigenbaum
We propose an instance-learning based framework for detecting BGP routing anomalies. By using a vector of quantified features to represent BGP updates, our framework can capture more complex features...
On Hiding Information from an Oracle (1989)
Martín Abadi, Joan Feigenbaum, Joe Kilian
: We consider the problem of computing with encrypted data. Player A wishes to know the value f(x) for some x but lacks the power to compute it. Player B has the power to compute f and is willing to...
On Hiding Information from an Oracle (1989)
Mart'in Abadi, Joan Feigenbaum, Joe Kilian
: We consider the problem of computing with encrypted data. Player A wishes to know the value f(x) for some x but lacks the power to compute it. Player B has the power to compute f and is willing to...
Product Graphs :--some algorithmic and combinatorial results /--by Joan Feigenbaum. (1986)
Thesis (Ph. D.)--Stanford University, 1986.
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Siddharth Suri, Jian Zhang
Abstract. 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...
Flexibility as an Instrument in Digital Rights Management
Dirk Bergemann, Thomas Eisenbach, Joan Feigenbaum, Scott Shenker
We consider the optimal design of flexible use in a digital-rights-management policy. The basic model considers a single distributor of digital goods and a continuum of consumers. Each consumer can...
Security and privacy in the information economy
Feigenbaum, Joan, Rudich, Steven, Blaze, Matt, McCurley, Kevin
Security and privacy in the information economy
Feigenbaum, Joan, Rudich, Steven, Blaze, Matt, McCurley, Kevin
Approximation and collusion in multicast cost sharing
Archer, Aaron, Feigenbaum, Joan, Krishnamurthy, Arvind, Sami, Rahul, Shenker, Scott
The Role of Trust Management in Distributed Systems Security
Matt Blaze Joan, Joan Feigenbaum, John Ioannidis, Angelos D. Keromytis
. Existing authorization mechanisms fail to provide powerful and robust tools for handling security at the scale necessary for today's Internet. These mechanisms are coming under increasing...
REFEREE: Trust Management for Web Applications
Yang-Hua Chu, Joan Feigenbaum, Brian Lamacchia, Paul Resnick, Martin Strauss
Digital signatures provide a mechanism for guaranteeing integrity and authenticity of Web content but not more general notions of security or trust. Web-aware applications must permit users to state...
The Role of Trust Management in Distributed Systems Security
Matt Blaze, Joan Feigenbaum, John Ioannidis, Angelos D. Keromytis
. Existing authorization mechanisms fail to provide powerful and robust tools for handling security at the scale necessary for today's Internet. These mechanisms are coming under increasing...
The Role of Trust Management in Distributed Systems Security
Matt Blaze, Joan Feigenbaum, John Ioannidis, Angelos D. Keromytis
Existing authorization mechanisms fail to provide powerful and robust tools for handling security at the scale necessary for today's Internet. These mechanisms are coming under increasing strain...
Economic and social sciences will drive Internet protocols and services into the future.