3 citations · 4 across the 4 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.CC2020
Automating Cutting Planes is NP-Hard}
Mika Göös, Sajin Koroth, Ian Mertz +1
We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula , 1) It is NP-hard to find a CP refutation of in time polynomial in the length of th…
cs.CC2020★ 1 cited
The Power of Many Samples in Query Complexity
Andrew Bassilakis, Andrew Drucker, Mika Göös +3
The randomized query complexity of a boolean function is famously characterized (via Yao's minimax) by the least number of queries needed to dis…