collaborators

4 papers

math.LO2026

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…

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.LO2026

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…

math.LO2024

Limits of structures and Total NP Search Problems

Ondřej Ježil

For an infinite class of finite graphs of unbounded size, we define a limit object, to be called a , relative to some computationally restricted class of funct…