3 papers
cs.CC2026
A proof complexity perspective on effectively zero-knowledge proofs
Jan Krajicek
Ilango (FOCS 2025) invented effectively zero-knowledge proofs, a new variant of zero-knowledge. We reformulate it in the language of logic and give simple proofs (under the same as…
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 w…