35 citations · 115 across the 15 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.CC2023
A note on the complexity of addition
Emil Jeřábek
We show that the sum of a sequence of integers can be computed in linear time on a Turing machine. In particular, the most obvious algorithm for this problem, which appears to requ…
cs.LO2023★ 1 cited
A simplified lower bound for implicational logic
Emil Jeřábek
We present a streamlined and simplified exponential lower bound on the length of proofs in intuitionistic implicational logic, adapted to Gordeev and Haeusler's dag-like natural de…