1 citations · 2 across the 5 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.CC2020★ 1 cited
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality
Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar
Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoret…
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
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
Valentine Kabanets, Sajin Koroth, Zhenjian Lu +2
The class consists of Boolean functions computable by size- de Morgan formulas whose leaves are any Boolean functions from a class .…