2 citations · 2 across the 3 of their papers we have counts for
3 papers
math.LO2017
Finitistic Properties of High Complexity
Dmytro Taranovsky
We use fast-growing finite and infinite sequences of natural numbers and more complicated constructs to define models of hypercomputation and interpret non-arithmetic predicates, w…
cs.CC2012
Space-Efficient Circuit Evaluation
Dmytro Taranovsky
We prove that uniform circuits of size n can be evaluated in space O(n/log n). Thus, Space(O(n)) is not in uniform Size(o(n*log n)). For uniformity, we only require that the circui…
math.LO2006★ 2 cited
Constructive Mathematical Truth
Dmytro Taranovsky
We define constructive truth for arithmetic and for intuitionistic analysis, and investigate its properties. We also prove that the set of constructively true (first order) arithme…