5 citations · 5 across the 5 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.CC2010
Local-Testability and Self-Correctability of q-ary Sparse Linear Codes
Widad Machmouchi
We prove that q-ary sparse codes with small bias are self-correctable and locally testable. We generalize a result of Kaufman and Sudan that proves the local testability and correc…
cs.CC2010★ 5 cited
The Quantum Query Complexity of AC0
Paul Beame, Widad Machmouchi
We show that any quantum algorithm deciding whether an input function from to is 2-to-1 or almost 2-to-1 requires queries to . The same lower bound holds…