Source author record

Marcel Celaya

Marcel Celaya appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Computational Complexity math.OC

Catalog footprint

What is connected

3works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

preprint2020arXiv

Distance-sparsity transference for vertices of corner polyhedra

We obtain a transference bound for vertices of corner polyhedra that connects two well-established areas of research: proximity and sparsity of solutions to integer programs. In the knapsack scenario, it gives an exponential (in the size of support of a solution) improvement on previously known proximity estimates. In addition, for general integer linear programs we obtain a resembling result that connects the minimum absolute nonzero entry of an optimal solution with the size of its support.

preprint2013arXiv

Morphic Words and Nested Recurrence Relations

We explore a family of nested recurrence relations with arbitrary levels of nesting, which have an interpretation in terms of fixed points of morphisms over a countably infinite alphabet. Recurrences in this family are related to a number of well-known sequences, including Hofstadter's G sequence and the Conolly and Tanny sequences. For a recurrence a(n) in this family with only finitely terms, we provide necessary and sufficient conditions for the limit a(n)/n to exist.

preprint2012arXiv

An Undecidable Nested Recurrence Relation

Roughly speaking, a recurrence relation is nested if it contains a subexpression of the form ... A(...A(...)...). Many nested recurrence relations occur in the literature, and determining their behavior seems to be quite difficult and highly dependent on their initial conditions. A nested recurrence relation A(n) is said to be undecidable if the following problem is undecidable: given a finite set of initial conditions for A(n), is the recurrence relation calculable? Here calculable means that for every n >= 0, either A(n) is an initial condition or the calculation of A(n) involves only invocations of A on arguments in {0,1,...,n-1}. We show that the recurrence relation A(n) = A(n-4-A(A(n-4)))+4A(A(n-4)) +A(2A(n-4-A(n-2))+A(n-2)). is undecidable by showing how it can be used, together with carefully chosen initial conditions, to simulate Post 2-tag systems, a known Turing complete problem.