35 citations · 115 across the 15 of their papers we have counts for
15 papers
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…
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…
Models of as exponential integer parts
Emil Jeřábek
We prove that (additive) ordered group reducts of nonstandard models of the bounded arithmetical theory are recursively saturated in a rich language with predicate…
Iterated multiplication in
Emil Jeřábek
We show that , the basic theory of bounded arithmetic corresponding to the complexity class , proves the axiom expressing the totality of iterated mult…
On the proof complexity of logics of bounded branching
Emil Jeřábek
We investigate the proof complexity of extended Frege (EF) systems for basic transitive modal logics (K4, S4, GL, ...) augmented with the bounded branching axioms .…
On the complexity of the clone membership problem
Emil Jeřábek
We investigate the complexity of the Boolean clone membership problem (CMP): given a set of Boolean functions and a Boolean function , determine if is in the clone gener…
Division by zero
Emil Jeřábek
For any sufficiently strong theory of arithmetic, the set of Diophantine equations provably unsolvable in the theory is algorithmically undecidable, as a consequence of the MRDP th…
Proof complexity of intuitionistic implicational formulas
Emil Jeřábek
We study implicational formulas in the context of proof complexity of intuitionistic propositional logic (IPC). On the one hand, we give an efficient transformation of tautologies…
A note on the substructural hierarchy
Emil Jeřábek
We prove that all axiomatic extensions of the full Lambek calculus with exchange can be axiomatized by formulas on the level of the substructural hierarchy.
Cluster expansion and the boxdot conjecture
Emil Jeřábek
The boxdot conjecture asserts that every normal modal logic that faithfully interprets T by the well-known boxdot translation is in fact included in T. We confirm that the conjectu…
Rules with parameters in modal logic I
Emil Jeřábek
We study admissibility of inference rules and unification with parameters in transitive modal logics (extensions of K4), in particular we generalize various results on parameter-fr…
Integer factoring and modular square roots
Emil Jeřábek
Buresh-Oppenheim proved that the NP search problem to find nontrivial factors of integers of a special form belongs to Papadimitriou's class PPA, and is probabilistically reducible…
Sequence encoding without induction
Emil Jeřábek
We show that the universally axiomatized, induction-free theory PA^- is a sequential theory in the sense of Pudlák [5], in contrast to the closely related Robinson's arithmetic.
Root finding with threshold circuits
Emil Jeřábek
We show that for any constant d, complex roots of degree d univariate rational (or Gaussian rational) polynomials---given by a list of coefficients in binary---can be computed to a…
The ubiquity of conservative translations
Emil Jeřábek
We study the notion of conservative translation between logics introduced by Feitosa and D'Ottaviano. We show that classical propositional logic (CPC) is universal in the sense tha…