Showing cs.CCShow all
2 papers · 1 filter
cs.CC2020
Dynamic Complexity of Expansion
Samir Datta, Anuj Tawari, Yadu Vasudev
Dynamic Complexity was introduced by Immerman and Patnaik \cite{PatnaikImmerman97} (see also \cite{DongST95}). It has seen a resurgence of interest in the recent past, see \cite{Da…
cs.CC2015
Trading query complexity for sample-based testing and multi-testing scalability
Eldar Fischer, Oded Lachish, Yadu Vasudev
We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich an…