5 citations · 9 across the 7 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2019★ 1 cited
A Lower Bound for Relaxed Locally Decodable Codes
Tom Gur, Oded Lachish
A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codew…
cs.CC2016
Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs
Oded Lachish, Igor Razgon
In this paper we establish an exponential lower bound on the size of syntactic non-deterministic read -times branching programs for computing a class of mo…
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…