Showing cs.CCShow all
3 papers · 1 filter
cs.CC2024
On Pigeonhole Principles and Ramsey in TFNP
Siddhartha Jain, Jiawei Li, Robert Robere +1
We show that the TFNP problem RAMSEY is not black-box reducible to PIGEON, refuting a conjecture of Goldberg and Papadimitriou in the black-box setting. We prove this by giving red…
cs.CC2023
On the Rational Degree of Boolean Functions and Applications
Vishnu Iyer, Siddhartha Jain, Robin Kothari +5
We study a natural complexity measure of Boolean functions known as the rational degree. Denoted , it is the minimal degree of a rational function that is equal t…
cs.CC2021
Unambiguous DNFs and Alon-Saks-Seymour
Kaspars Balodis, Shalev Ben-David, Mika Göös +2
We exhibit an unambiguous k-DNF formula that requires CNF width , which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the…