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

Rodney G. Downey

Rodney G. Downey contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.LOComputational Complexitymath.COComputational GeometryData Structures and AlgorithmsDiscrete MathematicsFormal Languages and Automata Theorymath.DSmath.GT

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
9topics
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)

preprint2016arXiv

Multiple Recurrence and Algorithmic Randomness

This work contributes to the programme of studying effective versions of "almost everywhere" theorems in analysis and ergodic theory via algorithmic randomness. We determine the level of randomness needed for a point in a Cantor space $ \{0,1\}^{\NN}$ with the uniform measure and the usual shift so that effective versions of the multiple recurrence theorem of Furstenberg holds for iterations starting at the point. We consider recurrence into closed sets that possess various degrees of effectiveness: clopen, $\PPI$ with computable measure, and $\PPI$. The notions of Kurtz, Schnorr, and \ML\ randomness, respectively, turn out to be sufficient. We obtain similar results for multiple recurrence with respect to the $k$ commuting shift operators on $\{0,1\}^{\NN^{\normalsize k}}$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Myhill-Nerode methods for hypergraphs

We give an analog of the Myhill-Nerode methods from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems: * We provide an algorithm for testing whether a hypergraph has cutwidth at most k that runs in linear time for constant k. In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by k. * We show that it is not expressible in monadic second-order logic whether a hypergraph has bounded (fractional, generalized) hypertree width. The proof leads us to conjecture that, in terms of parameterized complexity theory, these problems are W[1]-hard parameterized by the incidence treewidth (the treewidth of the incidence graph). Thus, in the form of the Myhill-Nerode theorem for hypergraphs, we obtain a method to derive linear-time algorithms and to obtain indicators for intractability for hypergraph problems parameterized by incidence treewidth. In an appendix, we point out an error and a fix to the proof of the Myhill-Nerode theorem for graphs in Downey and Fellow's book on parameterized complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Courcelle's theorem for triangulations

In graph theory, Courcelle's theorem essentially states that, if an algorithmic problem can be formulated in monadic second-order logic, then it can be solved in linear time for graphs of bounded treewidth. We prove such a metatheorem for a general class of triangulations of arbitrary fixed dimension d, including all triangulated d-manifolds: if an algorithmic problem can be expressed in monadic second-order logic, then it can be solved in linear time for triangulations whose dual graphs have bounded treewidth. We apply our results to 3-manifold topology, a setting with many difficult computational problems but very few parameterised complexity results, and where treewidth has practical relevance as a parameter. Using our metatheorem, we recover and generalise earlier fixed-parameter tractability results on taut angle structures and discrete Morse theory respectively, and prove a new fixed-parameter tractability result for computing the powerful but complex Turaev-Viro invariants on 3-manifolds.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Asymptotic Density and Computably Enumerable Sets

We study connections between classical asymptotic density and c.e. sets. We prove that a c.e. Turing degree d is not low if and only if d contains a c.e. set A of density 1 which has no computable subsets of density 1, giving a natural characterization of non-low c.e. degrees. In contrast, we prove that every nonzero c.e. degree contains a set which is generically computable but not coarsely computable. There is a very close connection between the computational complexity of a set and the computational complexity of its density as a real number where we measure complexity of real numbers as the position of their left Dedekind cuts in the Arithmetic Hierarchy. We characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study "computable at density r" where r is an arbitrary real number in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity and cohesiveness.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Confronting Intractability via Parameters

One approach to confronting computational hardness is to try to understand the contribution of various parameters to the running time of algorithms and the complexity of computational tasks. Almost no computational tasks in real life are specified by their size alone. It is not hard to imagine that some parameters contribute more intractability than others and it seems reasonable to develop a theory of computational complexity which seeks to exploit this fact. Such a theory should be able to address the needs of practicioners in algorithmics. The last twenty years have seen the development of such a theory. This theory has a large number of successes in terms of a rich collection of algorithmic techniques both practical and theoretical, and a fine-grained intractability theory. Whilst the theory has been widely used in a number of areas of applications including computational biology, linguistics, VLSI design, learning theory and many others, knowledge of the area is highly varied. We hope that this article will show both the basic theory and point at the wide array of techniques available. Naturally the treatment is condensed, and the reader who wants more should go to the texts, Downey and Fellows, Flum and Grohe, Niedermeier, and the upcoming undergraduate text Downey and Fellows.

0 citations0 reviewsNo code linkedOpen access