3 papers
cs.CC2026
Provable Reductions in TFNP
Noah Fleming, Stefan Grosser, Toniann Pitassi +1
We introduce a new family of propositional proof systems, denoted <EF, R>, for an arbitrary TFNP search problem . Informally, a refutation of a CNF formula in <EF, R> is giv…
cs.CC2026
Separations above TFNP from Sherali-Adams Lower Bounds
Noah Fleming, Anna Gal, Deniz Imrek +1
Unlike in TFNP, for which there is an abundance of problems capturing natural existence principles which are incomparable (in the black-box setting), Kleinberg et al. [KKMP21] obse…
cs.CC2025
Total Search Problems in
Noah Fleming, Stefan Grosser, Siddhartha Jain +4
We initiate a systematic study of , the class of total search problems solvable by polynomial time randomized algorithms. contains a variety o…