Scott Garrabrant

most citedPattern avoidance is not P-recursive

14 citations · 23 across the 3 of their papers we have counts for

collaborators

3 papers

cs.LO2017★ 7 cited

A Formal Approach to the Problem of Logical Non-Omniscience

Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch +2

We present the logical induction criterion for computable algorithms that assign probabilities to every logical statement in a given formal language, and refine those probabilities…

math.CO2015★ 14 cited

Pattern avoidance is not P-recursive

Scott Garrabrant, Igor Pak

Let $F \subset S_{k}$ be a finite set of permutations and let $C_{n} (F)$ denote the number of permutations $σ$ in $S_{n}$ avoiding the set of patterns $F$ . The Noonan-Zeilberger conjectu…

math.CO2015★ 2 cited

Words in Linear Groups, Random Walks, Automata and P-Recursiveness

Scott Garrabrant, Igor Pak

Fix a finite set $S \subset G L (k, Z)$ . Denote by $a_{n}$ the number of products of matrices in $S$ of length $n$ that are equal to 1. We show that the sequence ${a_{n}}$ is…