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...
An Approximate L p-Difference Algorithm for Massive Data Streams (2008)
Jessica H. Fong, Martin Strauss
Several recent papers have shown how to approximate the difference ∑i |ai −bi | or ∑|ai −bi | 2 between two functions, when the function values ai and bi are given in a data stream, and their...
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...
A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem (2007)
Harry Buhrman Cwi, Harry Buhrman, Dieter Van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
We introduce resource-bounded betting games, and propose a generalization of Lutz's resourcebounded measure in which the choice of next string to bet on is fully adaptive. Lutz's...
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...
Bias Invariance of Small Upper Spans (2007)
The resource-bounded measures of certain classes of languages are shown to be invariant under certain changes in the underlying probability measure. Specifically, for any real number ffi ? 0, any...
A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem (2007)
Harry Buhrman, Dieter Van Melkebeek, Kenneth W., Kenneth W. Regan, D. Sivakumar, Martin Strauss
We introduce resource-bounded betting games, and propose a generalization of Lutz's resourcebounded measure in which the choice of next string to bet on is fully adaptive. Lutz's...
Jin-yi Cai, D. Sivakumar, Martin Strauss
Resource-bounded measure theory [7] is a study of complexity classes via an adaptation of the probabilistic method. The central hypothesis in this theory is the assertion that NP does not have...
Martin Strauss, Prof Wolfgang Wahlster, Prof Wolfgang Wahlster, Martin Strauss, Martin Strauss
Realtime generation of multimodal affective sports commentary for embodied agents submitted by
Plug Conveying in a Horizontal Tube (2005)
Strauss, Martin, McNamara, Sean, Herrmann, Hans J.
Plug conveying along a horizontal tube has been investigated through simulation, using a discrete element simulation approach for the granulate particles and a pressure field approach for the gas....
Stuttgart, Univ., Diss., 2005.
Zou, Jing, Gilbert, Anna, Strauss, Martin, Daubechies, Ingrid
We analyze a sublinear RAlSFA (Randomized Algorithm for Sparse Fourier Analysis) that finds a near-optimal B-term Sparse Representation R for a given discrete signal S of length N, in time and space...
Plug Conveying in a Vertical Tube (2004)
Strauss, Martin, McNamara, Sean, Herrmann, Hans J., Niederreiter, Gerhard, Sommer, Karl
Plug conveying along a vertical tube has been investigated through simulation, using a discrete element simulation approach for the granulate particles and a pressure field approach for the gas. The...
Transport Coefficients for Stochastic Rotation Dynamics in Three Dimensions (2003)
Tuzel, Erkan, Strauss, Martin, Ihle, Thomas, Kroll, Daniel M.
Explicit expressions for the transport coefficients of a recently introduced stochastic model for simulating fluctuating fluid dynamics are derived in three dimensions by means of Green-Kubo...
Maintenance of multidimensional histograms (2003)
S. Muthukrishnan, Martin Strauss
1 Introduction Let Aj an N * N dynamic array1 at time j. Input is a series of updates. The jth input is (i, k, cj), which updates Aj-1 to be Aj, where
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...
An Approximate L p Difference Algorithm for Massive Data Streams (2001)
Jessica H. Fong, Martin Strauss
Several recent papers have shown how to approximate the difference ∑ i |a i-b i | or ∑|a i-b i | 2 between two functions, when the function values a i and b i are given in a data stream, and...
A generalization of resource-bounded measure, with application to the BPP vs. EXP problem (2000)
Harry Buhrman, Dieter Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
We introduce resource-bounded betting games, and propose a generalization of Lutz’s resource-bounded measure in which the choice of next string to bet on is fully adaptive. Lutz’s martingales are...
A generalization of resource-bounded measure, with application to the BPP vs. EXP problem (2000)
Harry Buhrman, Dieter Van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
1
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....
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....
1 A Generalization of Resource-Bounded Measure, With (2000)
Dieter Melkebeeky, Kenneth W. Reganz, D. Sivakumarx, Martin Strauss
siamltex
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...
An Approximate L p -Difference Algorithm for Massive Data Streams (1999)
Jessica H. Fong, Martin Strauss
Several recent papers have shown how to approximate the difference P i ja i \Gamma b i j or P ja i \Gamma b i j 2 between two functions, when the function values a i and b i are given in a data...
Just the Fax-Differentiating Voice and Fax Phone Lines Using Call Billing Data (1999)
Haim Kaplan, Martin Strauss, Mario Szegedy
this paper we are particularly concerned with classifying lines as either voice or fax, we point out that the techniques we use may apply in other classification problems as well. The ability to...
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...
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...
Atomic Proxy Cryptography (1998)
This paper introduces atomic proxy cryptography, in which an atomic proxy function, in conjunction with a public proxy key, converts ciphertext (messages in a public key encryption scheme or...
A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract) (1998)
Harry Buhrman, Dieter Van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
) Harry Buhrman 1 , Dieter van Melkebeek 2 , Kenneth W. Regan 3 , D. Sivakumar 4 , and Martin Strauss 5 1 CWI, Kruislaan 413, 1098SJ Amsterdam, The Netherlands. E-mail: buhrman@cwi.nl. Partly...
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...
Atomic Proxy Cryptography (1998)
This paper introduces atomic proxy cryptography, in which an atomic proxy function, in conjunction with a public proxy key, converts ciphertext (messages in a public key encryption scheme or...
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...
A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem (1998)
Harry Buhrman, Dieter Van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss
We introduce resource-bounded betting games, and propose a generalization of Lutz's resourcebounded measure in which the choice of next string to bet on is fully adaptive. Lutz's...
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...
Divertible protocols and atomic proxy cryptography (1998)
Matt Blaze, Gerrit Bleumer, Martin Strauss
Abstract. First, we introduce the notion of divertibility as a protocol property as opposed to the existing notion as a language property (see Okamoto, Ohta [OO90]). We give a definition of protocol...
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...
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...
Measure on P: Strength of the Notion (1997)
We give a notion of measure at P in a paradigm that differs somewhat from the standard theory. Our new notion overcomes some limitations of earlier formulations, specifically, concerning closure of...
[Mikrofiche-Ausg.].
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...
Measure on P: Strength of the Notion (1996)
We give a notion of measure on P that overcomes some limitations of earlier formulations. In the process, we investigate the significance for resource-bounded measure of the choice of the...
Measure on P: Robustness of the Notion (1995)
In [AS], we defined a notion of measure on the complexity class P (in the spirit of the work of Lutz [L92] that provides a notion of measure on complexity classes at least as large as E, and the work...
Measure on P: Robustness of the Notion (1995)
In [AS], we defined a notion of measure on the complexity class P (in the spirit of the work of Lutz [L92] that provides a notion of measure on complexity classes at least as large as E, and the work...
Measure on small complexity classes, with applications for BPP (1994)
We present a notion of resource-bounded measure for P and other subexponential-time classes. This gen-emlization is based on Lutz’s notion of measure, but overcomes the limitations that cause...
Measure on Small Complexity Classes, with Applications for BPP (1994)
We present a notion of resource-bounded measure for P and other subexponential-time classes. This generalization is based on Lutz's notion of measure, but overcomes the limitations that cause...
Measure on Small Complexity Classes, with Applications for BPP (1994)
The main contributions of this work are: 1. We present a notion of resource-bounded measure for P and other subexponential-time classes. This is a generalization of Lutz's notion of measure, but...
Towards a Measure for P (1994)
We investigate the issues and obstacles involved in extending Lutz's notion of measure to provide a measure for P. We provide one natural definition that, under a plausible but unproven...
Measure on Small Complexity Classes, with Applications for BPP (1994)
We present a notion of resource-bounded measure for P and other subexponential-time classes. This generalization is based on Lutz's notion of measure, but overcomes the limitations that cause...
Measure on Small Complexity Classes, with Applications for BPP (1994)
We present a notion of resource-boundedmeasure for P and other subexponential-time classes. This generalization is based on Lutz's notion of measure, but overcomes the limitations that cause...
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...
Constant Depth Circuits and the Lutz Hypothesis
Jin-yi Cai, D. Sivakumar, Martin Strauss
The central hypothesis in the theory of resource-bounded measure [6] is the assertion that NP does not have measure 0 in Exponential Time. This is a quantitative strengthening of the assertion that...
Normal Numbers and Sources for BPP
In [10], Lutz proposed a notion of source, a nonrandom sequence that can substitute in a certain way for the random bits used by boundederror probabilistic machines. He showed that almost every...