37 citations · 101 across the 43 of their papers we have counts for
Showing 2022 · cs.CCShow all
3 papers · 2 filters
cs.CC2022
Certification with an NP Oracle
Guy Blanc, Caleb Koch, Jane Lange +2
In the certification problem, the algorithm is given a function with certificate complexity and an input , and the goal is to find a certificate of size $\le \text…
cs.CC2022
Superpolynomial Lower Bounds for Decision Tree Learning and Testing
Caleb Koch, Carmen Strassle, Li-Yang Tan
We establish new hardness results for decision tree optimization problems, adding to a line of work that dates back to Hyafil and Rivest in 1976. We prove, under randomized ETH, su…
cs.CC2022
The composition complexity of majority
Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan
We study the complexity of computing majority as a composition of local functions: \[ \text{Maj}_n = h(g_1,\ldots,g_m), \] where each is an arbitrary…