3 citations · 4 across the 8 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Parity Tests under Ties: A One-Test Lifting Theorem
Ron Kupfer
In the unrestricted polynomial decision-tree model, only the number of polynomial sign tests is charged. A parity test asks for the sign of a product of pairwise differences. Such…
cs.DS2022
Finding a Hidden Edge
Ron Kupfer, Noam Nisan
We consider the problem of finding an edge in a hidden undirected graph with vertices, in a model where we only allowed queries that ask whether or not a subset of…