3 papers
cs.CC2026
Parallelism and Adaptivity in Student-Teacher Witnessing
Ondřej Ježil, Dimitrios Tsintsilidas
Student-Teacher Games are a model of computation in which a computationally restricted Student attempts to produce a string satisfying a refutable property, while an all-powerful T…
math.LO2025
Prime Factorization in Models of PV
Ondřej Ježil
Assuming that no family of polynomial-size Boolean circuits can factorize a constant fraction of all products of two -bit primes, we show that the bounded arithmetic theory $\te…
math.LO2025
Feasibility of Primality in Bounded Arithmetic
Raheleh Jalali, Ondřej Ježil
We prove the correctness of the AKS algorithm \cite{AKS} within the bounded arithmetic theory or, equivalently, the first-order consequences of the theory exp…