Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Josef M. Breutzmann

dblp:14/2868 · DBLP profile ↗
← Back
3ranked-venue papers
3as first author
0since 2021 · last 2001
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 first-author

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational complexity · 100%

Topics — the 1 heaviest of 2, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational complexity › structural complexity
resource-bounded measure
0.011999
Equivalence of Measures of Complexity Classes · SIAM J. Comput. 1999

Methods — techniques the papers use, named apart from their topics

truth-table reduction · 0.0martingale construction · 0.0bias reduction · 0.0
YearPublicationVenuePosition
2001 Baire Category and Nowhere Differentiability for Feasible Real Functions
Josef M. Breutzmann, David W. Juedes, Jack H. Lutz
ISAAC1
1999 Equivalence of Measures of Complexity Classes
abstract
The resource-bounded measures of complexity classes are shown to be robust with respect to certain changes in the underlying probability measure. Specifically, for any real number $\delta > 0$, any uniformly polynomial-time computable sequence $\mv{\beta} = (\beta_0, \beta_1, \beta_2, \ldots )$ of real numbers (biases) $\beta_i \in [\delta, 1-\delta]$, and for any complexity class ${\bf \cal C}$ (such as P, NP, BPP, P/Poly, PH, PSPACE, etc.) that is closed under positive, polynomial-time, truth-table reductions with queries of at most linear length, it is shown that the following two conditions are equivalent.(1) ${\bf \cal C}$ has p-measure 0 (respectively, measure 0 in E, measure 0 in E 2 ) relative to the coin-toss probability measure given by the sequence ${\mv{\beta}}$.(2) ${\bf \cal C}$ has p-measure 0 (respectively, measure 0 in E, measure 0 in E 2 ) relative to the uniform probability measure.The proof introduces three techniques that may be useful in other contexts, namely, (i) the transformation of an efficient martingale forone probability measure into an efficient martingale for a "nearby" probability measure; (ii) the construction of a positive bias reduction, a truth-table reduction that encodes a positive, efficient, approximate simulation of one bias sequence by another; and (iii) the use of such a reduction to dilate an efficient martingale for the simulated probability measure into an efficient martingale for the simulating probability measure.
Josef M. Breutzmann, Jack H. Lutz
SIAM J. Comput.1
1997 Equivalence of Measures of Complexity Classes
Josef M. Breutzmann, Jack H. Lutz
STACS1