From the 1 of 3 linked papers with an AI index.
3 papers
cs.CC2026
A proof complexity perspective on effectively zero-knowledge proofs
Jan Krajicek
The paper reformulates effectively zero-knowledge proofs in logical terms, provides simple proofs of their existence and indistinguishability, and shows how proof‑complexity genera…
math.LO2026
Extended Frege proofs, circuits and rewriting
Jan Krajicek
Inspired by a statement about Extended Frege proof systems by Jain and Jin (FOCS 2022) we prove that: - there is a p-time binary relation between circuits that implies th…
cs.CC2026
Failure of the strong feasible disjunction property
Jan Krajicek
A propositional proof system has the strong feasible disjunction property iff there is a constant such that whenever admits a size proof of …