The range avoidance problem (denoted by Avoid) asks to find a string outside of the range
of a given circuit C:{0, 1} n→{0, 1} m, where m> n. Although at least half of the strings of …

Reverse mathematics is a program in mathematical logic that seeks to determine which
axioms are necessary to prove a given theorem. In this work, we systematically explore the …

While there has been progress in establishing the unprovability of complexity statements in
lower fragments of bounded arithmetic, understanding the limits of Jerabek's theory APC 1 …

We prove the first unconditional consistency result for superpolynomial circuit lower bounds
with a relatively strong theory of bounded arithmetic. Namely, we show that the theory ‍V20 is …

A jump operator J in proof complexity is a function such that for any proof system P,J(P) is a
proof system that P cannot simulate. Some candidate jump operators were proposed by …

This paper studies the* refuter* problems, a family of decision-tree $\mathsf {TFNP} $
problems capturing the metamathematical difficulty of proving proof complexity lower …

We investigate randomized LEARN-uniformity, which captures the power of randomness
and equivalence queries (EQ) in the construction of Boolean circuits for an explicit problem …

Abstract A map g:{0, 1} ⁿ→{0, 1}^ m (m> n) is a hard proof complexity generator for a proof
system P iff for every string b∈{0, 1}^ m⧵ Rng (g), formula τ_b (g) naturally expressing b∉ …

Proof complexity (tacitly propositional) has a number of facets linking it with mathematical
logic, computational complexity theory, automated proof search and SAT algorithms and …

We show that there is a constant $ k $ such that Buss's intuitionistic theory $\mathsf {IS}^ 1_2
$ does not prove that SAT requires co-nondeterministic circuits of size at least $ n^ k $. To …