BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Douglas Cenzer

Douglas Cenzer contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.LOLogic in Computer Science

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2021arXiv

Randomness extraction in computability theory

In this article, we study a notion of the extraction rate of Turing functionals that translate between notions of randomness with respect to different underlying probability measures. We analyze several classes of extraction procedures: a first class that generalizes von Neumann's trick for extracting unbiased randomness from the tosses of a biased coin, a second class based on work of generating biased randomness from unbiased randomness by Knuth and Yao, and a third class independently developed by Levin and Kautz that generalizes the data compression technique of arithmetic coding. For the first two classes of extraction procedures, we identify a level of algorithmic randomness for an input that guarantees that we attain the extraction rate along that input, while for the third class, we calculate the rate attained along sufficiently random input sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Computability and Categoricity of Weakly Ultrahomogeneous Structures

This paper investigates the effective categoricity of ultrahomogeneous structures. It is shown that any computable ultrahomogeneous structure is $Δ^0_2$ categorical. A structure A is said to be weakly ultrahomogeneous if there is a finite (exceptional) set of elements $a_1,\dots,a_n$ such that A becomes ultrahomogeneous when constants representing these elements are added to the language. Characterizations are obtained for weakly ultrahomogeneous linear orderings, equivalence structures, injection structures and trees, and these are compared with characterizations of the computably categorical and $Δ^0_2$ categorical structures. Index sets are used to determine the complexity of the notions of ultrahomegenous and weakly ultrahomogeneous for various families of structures.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The random members of a $Π^0_1$ class

We examine several notions of randomness for elements in a given $Π^0_1$ class $\mathcal{P}$. Such an effectively closed subset $\mathcal{P}$ of $2^ω$ may be viewed as the set of infinite paths through the tree $T_{\mathcal{P}}$ of extendible nodes of $\mathcal{P}$, i.e., those finite strings that extend to a member of $\mathcal{P}$, so one approach to defining a random member of $\mathcal{P}$ is to randomly produce a path through $T_{\mathcal{P}}$ using a sufficiently random oracle for advice. In addition, this notion of randomness for elements of $\mathcal{P}$ may be induced by a map from $2^ω$ onto $\mathcal{P}$ that is computable relative to $T_{\mathcal{P}}$, and the notion even has a characterization in term of Kolmogorov complexity. Another approach is to define a relative measure on $\mathcal{P}$ by conditionalizing the Lebesgue measure on $\mathcal{P}$, which becomes interesting if $\mathcal{P}$ has Lebesgue measure 0. Lastly, one can alternatively define a notion of incompressibility for members of $\mathcal{P}$ in terms of the amount of branching at levels of $T_{\mathcal{P}}$. We explore some notions of homogeneity for $Π^0_1$ classes, inspired by work of van Lambalgen. A key finding is that in a specific class of sufficiently homogeneous $Π^0_1$ classes $\mathcal{P}$, each of these approaches coincides. We conclude with a discussion of random members of $Π^0_1$ classes of positive measure.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Algorithmically random functions and effective capacities

We continue the investigation of algorithmically random functions and closed sets, and in particular the connection with the notion of capacity. We study notions of random continuous functions given in terms of a family of computable measures called symmetric Bernoulli measures. We isolate one particular class of random functions that we refer to as online random functions $F$, where the value of $y(n)$ for $y = F(x)$ may be computed from the values of $x(0),\dots,x(n)$. We show that random online functions are neither onto nor one-to-one. We give a necessary condition on the members of the ranges of online random functions in terms of initial segment complexity and the associated computable capacity. Lastly, we introduce the notion of online \emph{partial} Martin-Löf random function on $2^ω$ and give a family of online partial random functions the ranges of which are precisely the random closed sets introduced by Barmpalias, Brodhead, Cenzer, Dashti, and Weber.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sub-computable Boundedness Randomness

This paper defines a new notion of bounded computable randomness for certain classes of sub-computable functions which lack a universal machine. In particular, we define such versions of randomness for primitive recursive functions and for PSPACE functions. These new notions are robust in that there are equivalent formulations in terms of (1) Martin-Löf tests, (2) Kolmogorov complexity, and (3) martingales. We show these notions can be equivalently defined with prefix-free Kolmogorov complexity. We prove that one direction of van Lambalgen's theorem holds for relative computability, but the other direction fails. We discuss statistical properties of these notions of randomness.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Algorithmic Randomness and Capacity of Closed Sets

We investigate the connection between measure, capacity and algorithmic randomness for the space of closed sets. For any computable measure m, a computable capacity T may be defined by letting T(Q) be the measure of the family of closed sets K which have nonempty intersection with Q. We prove an effective version of Choquet's capacity theorem by showing that every computable capacity may be obtained from a computable measure in this way. We establish conditions on the measure m that characterize when the capacity of an m-random closed set equals zero. This includes new results in classical probability theory as well as results for algorithmic randomness. For certain computable measures, we construct effectively closed sets with positive capacity and with Lebesgue measure zero. We show that for computable measures, a real q is upper semi-computable if and only if there is an effectively closed set with capacity q.

0 citations0 reviewsNo code linkedOpen access