2 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
Lower Bounds for Approximate Sign Rank
Riju Bindua, Hamed Hatami, Hasti Karimi +1
We prove new upper and lower bounds on -approximate sign-rank, a relaxation of sign-rank introduced by Chornomaz, Moran, and Waknine (STOC 2025). We show that every $m \times n…